第六章 树和二叉树数据结构,
线性结构 (线性表,栈,队列等 )
非线性结构,至少存在一个数据元素有不止一个直接前驱或后继 (树,图等 )
6.1 树的定义和基本概念
6.2 二叉树
6.2.1 树的定义和基本术语
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换第六章 树和二叉树
6.4.3树和森林的遍历
6.6 赫夫曼树及其应用
6.6.1 最优二叉树（赫夫曼树）
6.6.2 赫夫曼编码第六章 树和二叉树树型结构 是一类重要的 非线性结构 。 树型结构 是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。
第六章 树和二叉树
§ 6.1 树的定义树 (tree)是 n个数据元素的有限集 (记为
T)，对任意一棵树 T有：
⒈ 存在唯一一个称为 根 (root) 的数据元素；
⒉ 当 n＞ 1时，其它数据元素可分为 m(m＞ 0)
个互不相交的有限集 T1,T2,…,Tm，其中每个集合 Ti(i=1,2,…,m)本身又是一棵树，并称树 Ti是根的 子树 (subtree).
第六章 树和二叉树树的表示法
1,分支图表示法
2,嵌套集合表示法
A
B C
D
A
B C
D 3,广义表表示法
(A(B(D),C))
第六章 树和二叉树树的基本术语
1,树的结点,包含一个 DE和指向其子树的所有分支 ;
2,结点的度,一个结点拥有的子树的个数,度为零的结点称为 叶结点 或 终端结点 。度不为零的结点称为分支结点 或 非终端结点 。除根结点外，树的其它分支结点称为树的 内部结点 。
3,树的度,树中所有结点的度的最大值 Max(D(I))
含义,树中最大分支数为树的度 ;
4,结点的层次及树的深度,根为第一层,根的孩子为第二层,若某结点为第 k层,则其孩子为 k+1层,
树中结点的最大层次称为树的深度或高度第六章 树和二叉树
5.森林,是 m(m>=0)棵互不相的树的集合森林与树概念相近,相互很容易转换,
6.孩子,一个结点的 子树的根 称为该结点的 孩子 。相应的，该结点称为孩子的 双亲 。仿此不难理解 祖先结点,子孙结点,兄弟结点 的称呼。
7.有序树、无序树,如果树中各结点的子树从左到右看成是有序且不能交换则此树称为 有序树,否则称为 无序树 。
树的抽象数据类型定义：见教材 P.118-119。
第六章 树和二叉树
§ 6.2 树的基本运算
⒈ 初始化操作 InitTree(&T)：创建一棵空树。
⒉ 求根函数 Root(T)：求树 T的根；
⒊ 求双亲函数 Parent(T,cur_e)：在树 T中求 x的双亲。
⒋ 判树空函数 TreeEmpty(T)：若树 T为空树，则返回
TRUE，否则返回 FALSE。
⒌ 求兄弟函数：
在 T中求 x的左兄弟 LeftChild(T,cur_e)
在树 T中求 x的右兄弟 RightChild(T,cur_e)。
第六章 树和二叉树
⒍ 建树函数 CreateTree(&T,definition)：按
definitio构造树 T。
⒎ 插入子树操作 InsertChild(&T,&P,i,c)：插入
c为 T P所指结点的第 i棵子树。
⒏ 删除子树操作 DeleteChild(&T,&P,i)：删除 T
中 P所指结点的第 i棵子树。
⒐ 遍历树操作 TraverseTree(T,visit())：按某种顺序按 visit()访问树 T中各个结点。
⒑ 置空树操作 ClearTree(&T)：将树 T置为空树。
第六章 树和二叉树
§ 6.3 二叉树概念及性质一,二叉树概念二叉树是结点数为 0或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树，
它的特点是：
⑴每个结点最多只有两棵子树，即不存结点度大于 2的结点；
⑵子树有左右之分，不能颠倒。
6.3 二叉树二,二叉树性质性质 1,在二叉树的第 i层上至多有 2i-1个结点 (i≥1) 。
性质 2,深度为 k的二叉树至多有 2k-1个结点 (k≥) 。
（深度一定，二叉树的最大结点数也确定）
性质 3,二叉树中,终端结点数 n0与度为 2的结点数 n2
有如下关系,n0=n2+1
证明,设二叉树中度为 1的结点数为 n1，二叉树中总结点数为 N，因为二叉树中所有结点均小于或等于 2，所以有：
N＝ n0＋ n1＋ n2 (6-1)
再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设
B为二叉树中的分支总数，
则有,N＝ B＋ 1。
由于这些分支都是由度为 1和 2的结点射出的，所有有：
B＝ n1+2*n2
N＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
由式（ 6－ 1）和（ 6－ 2）得到：
n0+n1+n2=n1+2*n2+1
n0＝ n2＋ 1 命题得证下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。
6.3 二叉树
6.3 二叉树完全二叉树,深度为 k，结点数为 n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从 1到 n的结点一一对应时，称为完全二叉树。
4 5
2
1
3
6.3 二叉树完全二叉树的特点,
（ 1）每个结点 i的左子树的深度 Lhi-其结点 i的右子树的深度 Rhi等于 0或 1，即叶结点只可能出现在层次最大或次最大的两层上。
（ 2）完全二叉树结点数 n满足 2k-1-1＜ n≤2 k-1
（ 3）满二叉树一定是完全二叉树，反之不成立。
4 5
2
1
3
6.3 二叉树
LH2=0
RH2=1
1
32
4
6
5
32
4
1 LH1=3
RH1=1
LH1 -
RH1=2
非完全二叉树 非完全二叉树
LH2-RH2=0-1=-1
6.3 二叉树性质 4,结点数为 n的完全二叉树，其深度为
└ log2n┘ + 1
证明：
符号 【 x】 表示不大于 x的最大整数。
假设此二叉树的深度为 k，则根据性质 2及完全二叉树的定义得到,2k-1－ 1<n<=2k-1 或
2k-1<=n<2k
取对数得到,k－ 1<log2n<k 因为 k是整数。所以有,k＝ 【 log2n】 ＋ 1。
6.3 二叉树性质 5,在按层序编号的 n个结点的完全二叉树中，
任意一结点 i(1≤i≤n) 有：
⑴ i=1时，结点 i是树的根；否则 (i>1)，结点 i的双亲为结点 └ i/2┘ 。
⑵ 2i＞ n时，结点 i无左孩子，为叶结点；否则，
结点 i的左孩子为结点 2i。
⑶ 2i+1＞ n时，结点 i无右孩子；否则，结点 i的右孩子为结点 2i+1。
[I/2]
i I+1
2i 2i+1 2(I+1) 2i+3
I+1
2(I+1) 2i+3
i
2i 2i+1
图 6.11 完全二叉树中结点 i和 i+1
(a)i和 i+1结点在同一层 (b)i和 i+1结点不在同一层如图 6.11所示为完全二叉树上结点及其左右好在结点之间的关系。
i/2]
i+1
i+1)
i
i+1)
在此过程中，可以从（ 2）和（ 3）推出（ 1），所以先证明（ 2）和（ 3）。
对于 i＝ 1，由完全二叉树的定义，其左孩子是结点 2，若 2>n，即不存在结点 2，此是，结点 i无孩子。
结点 i的由孩子也只能是结点 3，若结点 3不存在，即
3>n，此时结点 i无右孩子。
对于 i>1，可分为两种情况：
（ 1）设第 j（ 1<=j<=[log2n])层的第一个结点的编号为 i，由二叉树的性质 2和定义知 i＝ 2j-1
结点 i的左孩子必定为的 j＋ 1层的第一个结点，其编号为 2j＝ 2× 2j-1＝ 2i。如果 2i>n，则无左孩子：
其右孩子必定为第 j＋ 1层的第二个结点，编号为 2i＋ 1。
若 2i+1>n，则无右孩子。
（ 2）假设第 j（ 1<=j<=[log2n])层上的某个结点编号为 i（ 2e(j-1)<=i<=2ej-1),且 2i＋ 1<n，其左孩子为
2i，右孩子为 2i＋ 1，则编号为 i＋ 1的结点时编号为 i
的结点的右兄弟或堂兄弟。若它有左孩子，则其编号必定为 2i＋ 2＝ 2× （ i＋ 1）：若它有右孩子，则其编号必定为 2i＋ 3＝ 2× （ i＋ 1）＋ 1。
当 i＝ 1时，就是根，因此无双亲，当 i>1时，如果 i为左孩子，即 2× （ i/2)=i,则 i/2是 i的双亲；如果 i为右孩子,i＝ 2p+1,i的双亲应为 p,p＝（ i－ 1） /2=[i/2],
证毕。
线性结构 (线性表,栈,队列等 )
非线性结构,至少存在一个数据元素有不止一个直接前驱或后继 (树,图等 )
6.1 树的定义和基本概念
6.2 二叉树
6.2.1 树的定义和基本术语
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 遍历二叉树
6.3.1 遍历二叉树
6.3.2 线索二叉树
6.4 树和森林
6.4.1 树的存储结构
6.4.2 森林与二叉树的转换第六章 树和二叉树
6.4.3树和森林的遍历
6.6 赫夫曼树及其应用
6.6.1 最优二叉树（赫夫曼树）
6.6.2 赫夫曼编码第六章 树和二叉树树型结构 是一类重要的 非线性结构 。 树型结构 是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界国是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。
第六章 树和二叉树
§ 6.1 树的定义树 (tree)是 n个数据元素的有限集 (记为
T)，对任意一棵树 T有：
⒈ 存在唯一一个称为 根 (root) 的数据元素；
⒉ 当 n＞ 1时，其它数据元素可分为 m(m＞ 0)
个互不相交的有限集 T1,T2,…,Tm，其中每个集合 Ti(i=1,2,…,m)本身又是一棵树，并称树 Ti是根的 子树 (subtree).
第六章 树和二叉树树的表示法
1,分支图表示法
2,嵌套集合表示法
A
B C
D
A
B C
D 3,广义表表示法
(A(B(D),C))
第六章 树和二叉树树的基本术语
1,树的结点,包含一个 DE和指向其子树的所有分支 ;
2,结点的度,一个结点拥有的子树的个数,度为零的结点称为 叶结点 或 终端结点 。度不为零的结点称为分支结点 或 非终端结点 。除根结点外，树的其它分支结点称为树的 内部结点 。
3,树的度,树中所有结点的度的最大值 Max(D(I))
含义,树中最大分支数为树的度 ;
4,结点的层次及树的深度,根为第一层,根的孩子为第二层,若某结点为第 k层,则其孩子为 k+1层,
树中结点的最大层次称为树的深度或高度第六章 树和二叉树
5.森林,是 m(m>=0)棵互不相的树的集合森林与树概念相近,相互很容易转换,
6.孩子,一个结点的 子树的根 称为该结点的 孩子 。相应的，该结点称为孩子的 双亲 。仿此不难理解 祖先结点,子孙结点,兄弟结点 的称呼。
7.有序树、无序树,如果树中各结点的子树从左到右看成是有序且不能交换则此树称为 有序树,否则称为 无序树 。
树的抽象数据类型定义：见教材 P.118-119。
第六章 树和二叉树
§ 6.2 树的基本运算
⒈ 初始化操作 InitTree(&T)：创建一棵空树。
⒉ 求根函数 Root(T)：求树 T的根；
⒊ 求双亲函数 Parent(T,cur_e)：在树 T中求 x的双亲。
⒋ 判树空函数 TreeEmpty(T)：若树 T为空树，则返回
TRUE，否则返回 FALSE。
⒌ 求兄弟函数：
在 T中求 x的左兄弟 LeftChild(T,cur_e)
在树 T中求 x的右兄弟 RightChild(T,cur_e)。
第六章 树和二叉树
⒍ 建树函数 CreateTree(&T,definition)：按
definitio构造树 T。
⒎ 插入子树操作 InsertChild(&T,&P,i,c)：插入
c为 T P所指结点的第 i棵子树。
⒏ 删除子树操作 DeleteChild(&T,&P,i)：删除 T
中 P所指结点的第 i棵子树。
⒐ 遍历树操作 TraverseTree(T,visit())：按某种顺序按 visit()访问树 T中各个结点。
⒑ 置空树操作 ClearTree(&T)：将树 T置为空树。
第六章 树和二叉树
§ 6.3 二叉树概念及性质一,二叉树概念二叉树是结点数为 0或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树，
它的特点是：
⑴每个结点最多只有两棵子树，即不存结点度大于 2的结点；
⑵子树有左右之分，不能颠倒。
6.3 二叉树二,二叉树性质性质 1,在二叉树的第 i层上至多有 2i-1个结点 (i≥1) 。
性质 2,深度为 k的二叉树至多有 2k-1个结点 (k≥) 。
（深度一定，二叉树的最大结点数也确定）
性质 3,二叉树中,终端结点数 n0与度为 2的结点数 n2
有如下关系,n0=n2+1
证明,设二叉树中度为 1的结点数为 n1，二叉树中总结点数为 N，因为二叉树中所有结点均小于或等于 2，所以有：
N＝ n0＋ n1＋ n2 (6-1)
再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设
B为二叉树中的分支总数，
则有,N＝ B＋ 1。
由于这些分支都是由度为 1和 2的结点射出的，所有有：
B＝ n1+2*n2
N＝ B＋ 1＝ n1＋ 2× n2＋ 1 （ 6－ 2)
由式（ 6－ 1）和（ 6－ 2）得到：
n0+n1+n2=n1+2*n2+1
n0＝ n2＋ 1 命题得证下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。
6.3 二叉树
6.3 二叉树完全二叉树,深度为 k，结点数为 n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从 1到 n的结点一一对应时，称为完全二叉树。
4 5
2
1
3
6.3 二叉树完全二叉树的特点,
（ 1）每个结点 i的左子树的深度 Lhi-其结点 i的右子树的深度 Rhi等于 0或 1，即叶结点只可能出现在层次最大或次最大的两层上。
（ 2）完全二叉树结点数 n满足 2k-1-1＜ n≤2 k-1
（ 3）满二叉树一定是完全二叉树，反之不成立。
4 5
2
1
3
6.3 二叉树
LH2=0
RH2=1
1
32
4
6
5
32
4
1 LH1=3
RH1=1
LH1 -
RH1=2
非完全二叉树 非完全二叉树
LH2-RH2=0-1=-1
6.3 二叉树性质 4,结点数为 n的完全二叉树，其深度为
└ log2n┘ + 1
证明：
符号 【 x】 表示不大于 x的最大整数。
假设此二叉树的深度为 k，则根据性质 2及完全二叉树的定义得到,2k-1－ 1<n<=2k-1 或
2k-1<=n<2k
取对数得到,k－ 1<log2n<k 因为 k是整数。所以有,k＝ 【 log2n】 ＋ 1。
6.3 二叉树性质 5,在按层序编号的 n个结点的完全二叉树中，
任意一结点 i(1≤i≤n) 有：
⑴ i=1时，结点 i是树的根；否则 (i>1)，结点 i的双亲为结点 └ i/2┘ 。
⑵ 2i＞ n时，结点 i无左孩子，为叶结点；否则，
结点 i的左孩子为结点 2i。
⑶ 2i+1＞ n时，结点 i无右孩子；否则，结点 i的右孩子为结点 2i+1。
[I/2]
i I+1
2i 2i+1 2(I+1) 2i+3
I+1
2(I+1) 2i+3
i
2i 2i+1
图 6.11 完全二叉树中结点 i和 i+1
(a)i和 i+1结点在同一层 (b)i和 i+1结点不在同一层如图 6.11所示为完全二叉树上结点及其左右好在结点之间的关系。
i/2]
i+1
i+1)
i
i+1)
在此过程中，可以从（ 2）和（ 3）推出（ 1），所以先证明（ 2）和（ 3）。
对于 i＝ 1，由完全二叉树的定义，其左孩子是结点 2，若 2>n，即不存在结点 2，此是，结点 i无孩子。
结点 i的由孩子也只能是结点 3，若结点 3不存在，即
3>n，此时结点 i无右孩子。
对于 i>1，可分为两种情况：
（ 1）设第 j（ 1<=j<=[log2n])层的第一个结点的编号为 i，由二叉树的性质 2和定义知 i＝ 2j-1
结点 i的左孩子必定为的 j＋ 1层的第一个结点，其编号为 2j＝ 2× 2j-1＝ 2i。如果 2i>n，则无左孩子：
其右孩子必定为第 j＋ 1层的第二个结点，编号为 2i＋ 1。
若 2i+1>n，则无右孩子。
（ 2）假设第 j（ 1<=j<=[log2n])层上的某个结点编号为 i（ 2e(j-1)<=i<=2ej-1),且 2i＋ 1<n，其左孩子为
2i，右孩子为 2i＋ 1，则编号为 i＋ 1的结点时编号为 i
的结点的右兄弟或堂兄弟。若它有左孩子，则其编号必定为 2i＋ 2＝ 2× （ i＋ 1）：若它有右孩子，则其编号必定为 2i＋ 3＝ 2× （ i＋ 1）＋ 1。
当 i＝ 1时，就是根，因此无双亲，当 i>1时，如果 i为左孩子，即 2× （ i/2)=i,则 i/2是 i的双亲；如果 i为右孩子,i＝ 2p+1,i的双亲应为 p,p＝（ i－ 1） /2=[i/2],
证毕。
