第十二讲二叉树

⼆叉树详解树是⼀种⽐较重要的数据结构，尤其是⼆叉树。

⼆叉树是⼀种特殊的树，在⼆叉树中每个节点最多有两个⼦节点，⼀般称为左⼦节点和右⼦节点（或左孩⼦和右孩⼦），并且⼆叉树的⼦树有左右之分，其次序不能任意颠倒。

本篇博客将详细为⼤家解析⼆叉树。

⾸先介绍两个概念：满⼆叉树：在⼀棵⼆叉树中，如果所有分⽀结点都有左孩⼦和右孩⼦结点，并且叶⼦结点都集中在⼆叉树的最下层，这样的树叫做满⼆叉树如：完全⼆叉树：若⼆叉树中最多只有最下⾯两层的结点的度数可以⼩于2，并且最下⾯⼀层的叶⼦结点都是依次排列在该层最左边的位置上，则称为完全⼆叉树如：区别：满⼆叉树是完全⼆叉树的特例，因为满⼆叉树已经满了，⽽完全并不代表满。

所以形态你也应该想象出来了吧，满指的是出了叶⼦节点外每个节点都有两个孩⼦，⽽完全的含义则是最后⼀层没有满，并没有满。

⼆叉树的链式存储结构是⼀类重要的数据结构，定义结果为：Cpp代码1. //定义树的结构2. struct node3. {4. node * lchild;5. node * rchild;6. string data;7. //初始化8. node()9. {10. lchild=rchild=NULL;11. }12. };⼆叉树的建⽴⾸先我们⽤户输⼊⽣成⼀棵⼆叉树，要⽣的的⼆叉树如下图所⽰：#代表空结点。

下⾯我们根据上⾯图中所⽰的⼆叉树，利⽤先序依次输⼊ABDG###E#H##C#F##(即先序遍历）⽣成⼆叉树的代码如下：Cpp代码1. //⼆叉树⽣成--先序遍历输⼊要⽣成的⼆叉树数据，#代表空结点2. void CreateTree(node * & root)3. {4. char data;5. cin>>data;6. if(data!='#')7. {8. root=new node;9. root->data=data;10.11. CreateTree(root->lchild);12.13. CreateTree(root->rchild);14.15. }16. }⼆叉树节点查找采⽤递归的⽅法在⼆叉树root⾥查找只为aim的结点，若找到此节点则返回其指针，否则返回NULL 查找代码如下：Cpp代码1. //检查⼆叉树是否包含数据aim,有则返回其指针2. node * Findnode(node * & root,string aim)3. {4. node * p;5. if(root==NULL)//空树6. return NULL;7. else if(root->data==aim)8. return root;9. else10. {11. p=Findnode(root->lchild,aim);12. if(p!=NULL)13. return p;14. else15. return Findnode(root->rchild,aim);16. }17. }这⾥解释⼀下递归中的return的意思：return 对当前函数来说是结束了，对调⽤它的⽗函数来说你这个函数执⾏完成了，⽗函数就会接着执⾏下⼀语句。

A
B
CX
E FGH I
J
8
四. 基本名词术语
1. 结点的度：该结点拥有的子树的数目。
2. 树的度：树中结点度的最大值。
3. 叶结点：度为0 的结点. 4. 分支结点: 度非0 的结点. 5. 层次的定义: 根结点为第一层,若某结点在第i 层,
则其孩子结点(若存在)为第i+1层.
A
第1层
B
CX
第2层
12
完全二叉树.
三.i 层最多有2i–1个结点(i1)。
2. 深度为h 的非空二叉树最多有2h -1个结点.
3. 若非空二叉树有n0个叶结点,有n2个度为2的结点,
则
n0=n2+1
4. 具有n个结点的完全二叉树的深度h=log2n+1.
13
二叉树的存储结构
39
例
A
BC D
E F GH I
对树进行先根遍历，获得的先根序列是： ABEFCDGHI
对树进行后根遍历，获得的后根序列是： EFBCGHIDA
40
2.森林的遍历
先序遍历(对森林中的每一棵树进行先根遍历)
1）若森林不空，访问森林中第一棵树的根结点； 2）先序遍历森林中第一棵树的子树森林； 3）先序遍历森林中(除第一棵树外)其余树构成的森林。
(空) 根 根 根
根
左 子 树
右 子 树
左 子 树
右 子 树
11
二. 两种特殊形态的二叉树
1. 满二叉树
若一棵二叉树中的结点, 或者为叶结点， 或者具有两 棵非空子树,并且叶结点都集 中在二叉树的最下面一层.这 样的二叉树为满二叉树.
2.完全二叉树
若一棵二叉树中只有最下 面两层的结点的度可以小于2, 并且最下面一层的结点(叶结 点)都依次排列在该层从左至 右的位置上。这样的二叉树为

后序遍历 (Postorder Traversal)
后序遍历二叉树算法的框架是 若二叉树为空，则空操作； 否则
后序遍历左子树
(L)； 后序遍历右子树 (R)； 访问根结点 (V)。
遍历结果
abcd-*+ef/-
二叉树递归的后序遍历算法 template <class Type> void BinaryTree <Type>::PostOrder ( ) { PostOrder ( root ); } template <class Type> void BinaryTree<Type>:: PostOrder ( BinTreeNode <Type> *current ) { if ( current != NULL ) { PostOrder ( current→leftChild ); PostOrder ( current→rightChild ); cout << current→data; } }
树的概念 二叉树 (Binary Tree) 二叉树遍历 (Binary Tree Traversal) 二叉树的计数 小结

树的概念
树的定义 树是由 n (n 0) 个结点组成的有限集合。如 果 n = 0，称为空树；如果 n > 0，则 有一个特定的称之为根(root)的结点，它只 有直接后继，但没有直接前驱； 除根以外的其它结点划分为 m (m 0) 个 互不相交的有限集合T0, T1, …, Tm-1，每个集合 又是一棵树，并且称之为根的子树(subTree)。 每棵子树的根结点有且仅有一个直接前驱，但 可以有0个或多个直接后继。
证明：若设度为1的结点有 n1 个，总结点个数 为 n，总边数为 e，则根据二叉树的定义， n = n0 + n1 + n2 e = 2n2 + n1 = n - 1 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1 定义1 满二叉树(Full Binary Tree) 定义2 完全二叉树(Complete Binary Tree) 若设二叉树的高度为h，则共有h+1层。除 第 h 层外，其它各层 (0 h-1) 的结点数都达 到最大个数，第 h 层从右向左连续缺若干结 点，这就是完全二叉树。

⼆叉树⼆叉树 是n（n>=0）个结点的有限集合，该集合或者为空集（空⼆叉树），或者由⼀个根节点和两棵互不相交的、分别称为根节点的左⼦树和右⼦树的⼆叉树组成。

⼆叉树特点： 1）每个结点最多有两颗⼦树，所以⼆叉树中不存在度⼤于2的结点。

2）左⼦树和右⼦树是有顺序的，次序不能任意颠倒。

3）即使树中某结点只有⼀颗⼦树，也要区分是左⼦树还是右⼦树。

⼆叉树具有五种基本形态： 1）空⼆叉树 2）只有⼀个根结点 3）根结点只有左⼦树 4）根结点只有右⼦树 5）根结点既有左⼦树⼜有右⼦树。

三个结点的⼆叉树有5种形态：特殊⼆叉树：1.斜树 顾名思义，斜树⼀定是斜的，但是往哪还是有讲究的。

所有的结点都只有左⼦树的⼆叉树叫做左斜树。

所有的结点都只有右⼦树的⼆叉树叫做右斜树。

斜树有很明显的特点就是每⼀层都只有⼀个结点。

结点的个数与⼆叉树的深度相同。

左斜树 右斜树2.满⼆叉树 在⼀颗⼆叉树中，如果所有分⽀结点都存在左⼦树和右⼦树，并且所有叶⼦都在同⼀层上，这样的⼆叉树称为满⼆叉树。

单是每个结点都存在左右⼦树，不能算是满⼆叉树，还必须要所有的叶⼦都在同⼀层上，这就做到了整棵树的平衡。

因此，满⼆叉树的特点有： 1）叶⼦只能出现在最下⼀层。

出现在其它层就不可能达成平衡。

2）⾮叶⼦结点的度⼀定是2. 3）在同样深度的⼆叉树中，满⼆叉树的结点个数最多，叶⼦数最多。

3.完全⼆叉树 对⼀颗具有n个结点的⼆叉树按层序编号，如果编号为i（1 <= i <= n）的结点与同样深度的满⼆叉树中编号为i的结点在⼆叉树中位置完全相同，则这棵⼆叉树称为完全⼆叉树。

如图⽰：⼆叉树性质：性质1：在⼆叉树的第i层⾄多有2i-1个结点（i >= 1）。

性质2：深度为K的⼆叉树⾄多有2k-1个结点（k >= 1)。

性质3：对任何⼀颗⼆叉树T，如果其终端结点数为n0,度为2的结点树为n2,则n0 = n2 + 1。

性质4：具有n个结点的完全⼆叉树的深度为|log2n| + 1 (|x|表⽰不⼤于x的最⼤整数）。