数据结构——二叉树（2025.2.12）

目录

一、树

1.定义

（1）树的构成

（2）度

2.二叉树

（1）定义

（2）二叉树的遍历

（3）遍历特性

二、练习 

1.二叉树

（1）创建二叉树

（2）前序遍历

（3）中序遍历

（4）后序遍历

（5）获取结点个数

（6）获取层数

（7）层序遍历

（8）销毁二叉树

---

一、树

---

1.定义

（1）树的构成

     ①树：树是由n个结点组成的有限集

          若n = 0， 则为空树。

     ②根：树只有一个根结点

          除根外，其他所有结点只有一个前驱结点，但可以有多个后继结点。(一对多)

     ③叶子：叶子结点，即终端结点

          只有前驱结点，没有后继结点。

     ④分支：分支结点，即非终端结点

          既有前驱节点，也有后继的结点。

     ⑤森林：n个互不相交的树的集合。

（2）度

       ①结点度：子节点（后继结点）的个数

       ②树的（广）度：树中各结点度的最大值 

       ③深度：从根节点到最底层节点的层数

2.二叉树

（1）定义

       ①二叉树：任意一个节点的子节点个数不能超过2个(树的度为2)，且子节点的位置不可更改。

       ②满二叉树：在不增加树的层数的前提下，无法再增加一个结点的二叉树
        
                       特性：满二叉树第K层有2^(k-1)个节点
                                  K层满二叉树总共有2^k-1个节点

       ③完全二叉树：只是删除了满二叉树最底层最右边的连续若干个节点，形成了完全二叉树。

                   在满二叉树的基础上，按照从左向右，从上至下的顺序删除若干个连续的结点，构成完全二叉树；
                   在满二叉树的基础上，按照从右至左，从下至上的顺序插入若干个连续的结点 ，构成完全二叉树；

                    满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

                            满二叉树 ==> 完全二叉树
                            完全二叉树 =/=> 满二叉树

（2）二叉树的遍历

• 深度优先遍历算法：

        ①前序遍历：根结点，左子树，右子树        例：ABEHMFDICG

        ②中序遍历：左子树，根结点，右子树        例：HEMBFAICDG

        ③后序遍历：左子树，右子树，根结点        例：HMEFBCIGDA

• 广度优先遍历算法：

        ④层序遍历：从上至下，从左到右，逐层遍历        例：ABDEFIGHMC

（3）遍历特性

        已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；

        已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；

在编程中，我们常在叶子结点后添上“#”，用作识别终止的标志，等价于NULL。

例如：ABEH##M##F##DI#C##G##

在创建二叉树时，常将每个结点设置成三部分，分别装数据与左右后继结点的地址。

二、练习 

---

1.二叉树

（1）创建二叉树

 （2）前序遍历

（3）中序遍历

（4）后序遍历

 （5）获取结点个数

（6）获取层数

 （7）层序遍历

（8）销毁二叉树