第4章 树和二叉树--1
第4章 树和二叉树
4.1 树
1、常见的数据结构？
（1）集合 （2）线性结构
集合的定义是由一组无序且唯一（即不能重 线性结构是一个有序数据元素的集合。
复）的项组成的。不包含任何元素的集合就 常用的线性结构有：线性表，栈，队列，双
叫做空集。 队列，数组，串。
元素 1 元素 2 元素 3 元素 4 元素 5
0 1 2 3 4
（3）树形结构 （4）图形结构
n 个有限节点组成一个具有层次关系的集 图形结构——多个对多个。
合。
2、什么是树？
树：是一种数据结构，它是由 n（n>=0）个有限
节点组成一个具有层次关系的集合。树是一类非线性
结构。这种结构结点之间有分支，并具有层次关系。
它非常类似于自然界中的树。
树的作用：表达家谱顺序、行政组织结构、计算
机文件结构、书的教材章节结构等。
3、树的基本概念
（1）树是 n（n≥0）个结点的有限集。
（2）当 n=0 时称为空树；
（3）当 n>0 时为非空树，在任意一棵非空树中，有且仅有一个称为根的结点，其余的结点
可分为 m(m ≥0)个互不相交的有限集 T1,T2,…,Tm，其中每一个集合又称为一棵树，并且称
为根的子树；同理，每一棵子树又可以分为若干个互不相交的有限集……
总结树的特性：
（1）空树是树的特例;
（2）非空树中至少有一个结点，称为树的根，只有根结点的树称为最小树;
（3）在含有多个结点的树中，除根结点外，其余结点构成若干棵子树，且各子树间互
不相交。
4、树的基本术语
（1）树的结点： 包含一个数据元素及若干个指向其子树的分支 ；
（2）结点的度： 一个结点拥有的子树数目 ；
（3）树的度： 一棵树上所有结点度的最大值 ；
（4）叶子结点（终端结点）： 度为零的结点 ；
（5）分支结点（非终端结点）： 度大于零的结点 ；
（6）路径（从根到结点的）： 由从根到该结点所经分支和结点构成 ；
（7）孩子结点： 结点的子树的根称为该结点的孩子结点 ；
（8）双亲结点： 相应地，该结点称为孩子的双亲结点 ；
（9）兄弟： 具有同一父结点的子结点互称兄弟 ；
（10）堂兄弟： 其双亲在同一层的结点互为堂兄弟 ；
（11）祖先结点： 从根到该结点所经分支上的所有结点 ；
（12）子孙结点： 以某结点为根的子树中任一结点都称为该结点的子孙 ；
（13）结点的层次： 从根结点到该结点所经过的路径长度加 1 ；
（14）树的深度： 树中叶子结点具有的最大层次数 ；
（15）树的宽度： 整棵树中某一层中最多的结点数称为树的宽度 ；
（16）有序树： 如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称
该树为有序树，与之相对的是无序树 ；
（17）第一个孩子： 在有序树中，最左边的子树的根称为第一个孩子 ；
（18）最后一个孩子： 在有序树中，最右边的子树的根称为最后一个孩子 ；
练习：参照右图的树，回答下列问题
（1）该树有哪些结点
ABCDEFGHIJKLM ，
其中的叶子节点有 EKLGHIM ，分支节点有
ABCDFJ 。
（2）结点 A 的度为 3 ，结点 B 的度为 2 ，树的度
为 3 。
（3）请写出 A 节点到 K 节点经过的路径 A->B->F->K 。
（4）H 结点的兄弟结点有 I、J ，堂兄弟结点有 E、F、G 。
（5）F 结点的祖先结点有 B、A ，子孙结点有 K、L 。
（6）该树的深度为 4 ，树的宽度为 6 。
5、树的表示方法
了解树的表示方法。
二叉链表（孩子-兄弟）表示法
在这种存储方式下，每个结点包括三部分的内容：结点值、指向该结点第一个孩子结
点的指针和指向该结点下一个兄弟结点的指针。
4.2 二叉树
1、什么是二叉树？
二叉树是n (n≥0) 个结点的有限集合，这个集合或是空集，或是由一个根结点以及两棵互
不相交的、被称为根的左子树和右子树所组成；左子树和右子树分别又是一棵二叉树。
二叉树的特点：每个结点至多只有两棵子树，且二叉树的子树有左右之分，其次序不能任
意颠倒。
2、满二叉树和完全二叉树
满二叉树：一棵深度为 k 且有 2k -1 个结点 完全二叉树：深度为 k 的，有 n 个结点的二
的二叉树。（特点：每一层上的结点数都是 叉树，当且仅当其每一个结点都与深度为 k
最大结点数） 的满二叉树中编号从 1 至 n 的结点一一对应
（特点： 至多只有最下面两层的结点的度可
以小于 2，且倒二层如果只有一个孩子，那
必是左孩子。）
注意：满二叉树是叶子一个也不少的树，而完全二叉树虽然前 n-1 层是满的，但最底层却
允许在右边缺少连续若干个结点。满二叉树是完全二叉树的一个特例。
一棵深度为 k 的完全二叉树，至少有 2k-1 个结点，最多有 2k-1 个结点。
3、二叉树的性质
① 性质 1：在二叉树的第 i 层上至多有 2i-1 个结点（i≥1）。
问题：在第 i 层上至少有 1 个结点。
② 性质 2：深度为 h 的二叉树至多有 2h-1 个结点（h≥1）。
问题：一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。
问题：一颗深度为 k 的二叉树，至少有 k 个结点。
③ 性质 3：对任何一棵二叉树，如果其叶结点数 n0，度为 2 的结点数为 n2，则一定满
足：n0= n2+1 。
问题：一棵完全二叉树有 5000 个结点，可以计算出其叶结点的个数是 2500 。
④ 性质 4：具有 n 个结点的完全二叉树的深度为 floor(log2n)+1 。
⑤ 性质 5：对于一棵 n 个结点的完全二叉树，对任一个结点（编号为 i）
如果 i=1，则结点 i 为根，无 父结点 ；如果 i>1，则其父结点编号为
floor(i/2) 。
如果 2i>n，则结点 i 无 子节点 ，即结点 i 为 叶结点 ；否则左孩子编号为
2i 。
如果 2i+1>n，则结点 i 无 右孩子 ，否则右孩子编号为 2i+1
4、二叉树的存储
（1）表示方法一：数组表示法
对于完全二叉树，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉
树上的结点元素。
用字符串表示为：string s = "LDPCFM###EH#N";
（3）表示方法三：链式存储；
采用：含有两个指针域的结点结构体及链表的结构进行存储。
5、遍历方案
一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点
上，可以按某种次序执行三个操作:
（1） 访问根结点（D）;
（2） 遍历该结点的左子树（L）;
（3） 遍历该结点的右子树（R）;
遍历方案：
DLR：先序遍历（Preorder Traverse，亦称前序遍历）
———访问根结点、遍历左树、遍历右树。
LDR：中序遍历（Inorder Traverse）
———遍历左树、访问根结点、遍历右树。
LRD：后序遍历（Postorder Traverse）
———遍历左树、遍历右树、访问根结点。
先序遍历的结果为： A B C D E F G H K ；
中序遍历的结果为： B D C A E H G K F ；
后序遍历的结果为： D C B H K G F E A ；