树和森林的概念二叉 (Binary Tree)二叉树的表示二叉树

}
2021/4/18 北京化工大学信息学院 数据结构 33
求二叉树高度的递归算法
int Height ( BinTreeNode * T ) { if ( T == NULL ) return -1; else { int m = Height ( T->leftChild ); int n = Height ( T->rightChild ) ); return (m > n) ? m+1 : n+1;
中序遍历 (Inorder Traversal)
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；
-
否则 中序遍历左子树 (L)；
+
/
访问根结点 (V)；
a *e f
中序遍历右子树 (R)。
遍历结果
b-
a+b*c-d-e/f
cd
2021/4/18 北京化工大学信息学院 数据结构 20
二叉树递归的中序遍历算法
如果 n = 0，称为空树；如果 n > 0，则 ▪ 有一个特定的称之为根(root)的结点，
它只有直接后继，但没有直接前驱； ▪ 除根以外的其它结点划分为 m (m 0)
个 互不相交的有限集合T0, T1, …, Tm-1，每 个集合又是一棵树，并且称之为根的子树。
2021/4/18 北京化工大学信息学院 数据结构 3
typedef struct node { //树结点定义
TreeData data;
//结点数据域
struct node * leftChild, * rightchild;
//子女指针域
} BinTreeNode;
typedef BinTreeNode * BinTree; //树定义，代表树的根指针

数据结构之⼆叉树（BinaryTree）⽬录导读 ⼆叉树是⼀种很常见的数据结构，但要注意的是，⼆叉树并不是树的特殊情况，⼆叉树与树是两种不⼀样的数据结构。

⽬录 ⼀、⼆叉树的定义 ⼆、⼆叉树为何不是特殊的树 三、⼆叉树的五种基本形态 四、⼆叉树相关术语 五、⼆叉树的主要性质（6个） 六、⼆叉树的存储结构（2种） 七、⼆叉树的遍历算法（4种） ⼋、⼆叉树的基本应⽤：⼆叉排序树、平衡⼆叉树、赫夫曼树及赫夫曼编码⼀、⼆叉树的定义 如果你知道树的定义（有限个结点组成的具有层次关系的集合），那么就很好理解⼆叉树了。

定义：⼆叉树是n(n≥0)个结点的有限集，⼆叉树是每个结点最多有两个⼦树的树结构，它由⼀个根结点及左⼦树和右⼦树组成。

（这⾥的左⼦树和右⼦树也是⼆叉树）。

值得注意的是，⼆叉树和“度⾄多为2的有序树”⼏乎⼀样，但，⼆叉树不是树的特殊情形。

具体分析如下⼆、⼆叉树为何不是特殊的树 1、⼆叉树与⽆序树不同 ⼆叉树的⼦树有左右之分，不能颠倒。

⽆序树的⼦树⽆左右之分。

2、⼆叉树与有序树也不同（关键） 当有序树有两个⼦树时，确实可以看做⼀颗⼆叉树，但当只有⼀个⼦树时，就没有了左右之分，如图所⽰：三、⼆叉树的五种基本状态四、⼆叉树相关术语是满⼆叉树；⽽国际定义为，不存在度为1的结点，即结点的度要么为2要么为0，这样的⼆叉树就称为满⼆叉树。

这两种概念完全不同，既然在国内，我们就默认第⼀种定义就好）。

完全⼆叉树：如果将⼀颗深度为K的⼆叉树按从上到下、从左到右的顺序进⾏编号，如果各结点的编号与深度为K的满⼆叉树相同位置的编号完全对应，那么这就是⼀颗完全⼆叉树。

如图所⽰：五、⼆叉树的主要性质 ⼆叉树的性质是基于它的结构⽽得来的，这些性质不必死记，使⽤到再查询或者⾃⼰根据⼆叉树结构进⾏推理即可。

性质1：⾮空⼆叉树的叶⼦结点数等于双分⽀结点数加1。

证明：设⼆叉树的叶⼦结点数为X，单分⽀结点数为Y，双分⽀结点数为Z。

leftChild data rightChild
二叉链表
leftChild
data rightChild
22
二叉树的链表表示（三叉链表）
每个结点增加一个指向双亲的指针parent，使 得查找双亲也很方便。
leftChild data parent rightChild
三叉链表
data
leftChild
27
BinTreeNode *LeftChild (BinTreeNode *current ) { return (current != NULL )? current->leftChild :NULL; } BinTreeNode *RightChild (BinTreeNode *current ) { return ( current!= NULL) ? current->rightChild : NULL; } int Height( ){return Height(root);} int Size( ){return Size(root);} BinTreeNode *GetRoot ( ) const { return root; } void preOrder( ) {preOrder(root);} //前序遍历 void inOrder( ) {inOrder(root);} //中序遍历 void postOrder( ) {postOrder(root);} //后序遍历 void levelOrder( ) ; // 不需要递归，所以直接对外接 口调用即可。层序遍历 28
b
f
c
d
g
6
e
a
b.嵌套集合表示法： b 根据树的集合定义，写出集合划分。 { a, {b,{e},{f}}, {c}, {d,{g}} } e c d

返回
二叉树的性质
性质1：二叉树第i层上的结点数目最多为2i-1(i≥1)。 性质2：深度为k的二叉树至多有2k-1个结点(k≥1)。 性质3：在任意一棵二叉树中，若终端结点的个数为 n0，度为2的结点数为n2，则n0=n2+1。
返回
满二叉树和完全二叉树
满二叉树和完全二叉树是二叉树的两种特殊情形。 1、满二叉树(FullBinaryTree) 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。 满二叉树的特点： (1)每一层上的结点数都达到最大值。即对给定的高度， 它是具有最多结点数的二叉树。 (2)满二叉树中不存在度数为1的结点，每个分支结点 均有两棵高度相同的子树，且树叶都在最下一层上。
满二叉树和完全二叉树
2、完全二叉树(Complete BinaryTree) 若一棵二叉树至多只有最下面的两层上结点的度 数可以小于2，并且最下一层上的结点都集中在该层 最左边的若干位置上，则此二叉树称为完全二叉树。 具有n个结点，其形状与满二叉树按层编号的前n 个结点的位置顺序一一对应。 完全二叉树的特点： (1)满二叉树是完全二叉树，完全二叉树不一定是满二 叉树。 (2)在满二叉树的最下一层上，从最右边开始连续删去 若干结点后得到的二叉树仍然是一棵完全二叉树。 (3)在完全二叉树中，若某个结点没有左孩子，则它一 定没有右孩子，即该结点必是叶结点。
祖先(Ancestor)和子孙(Descendant) ①路径（path） 注意： 若一个结点序列是路径，则在树的树形图表示中， 该结点序列“自上而下”地通过路径上的每条边。 从树的根结点到树中其余结点均存在一条惟一的 路径 。 A B E K L F C G H M D I J
祖先(Ancestor)和子孙(Descendant) ②祖先(Ancestor)和子孙(Descendant) 若树中结点k到ks存在一条路径，则称k是ks的祖 祖 先(Ancestor)，ks是k的子孙 子孙(Descendant)。 子孙 一个结点的祖先是从根结点到该结点路径上所经 过的所有结点，而一个结点的子孙则是以该结点为根 的子树中的所有结点。 约定： 结点k的祖先和子孙不包含结点k本身。