数据结构树和二叉树

1、第第6 6章章 树和二叉树树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.6 6.6 赫夫曼树及其应用赫夫曼树及其应用6.1 6.1 树的定义和基本术语树的定义和基本术语1.1.树的逻辑定义树的逻辑定义 是由是由n(n 0)n(n 0)个结点组成的有限集合个结点组成的有限集合T T。 在任意一个非空树中：在任意一个非空树中： 有且仅有一个特定的称为根的结点；有且仅有一个特定的称为根的结点； n 1n 1时，其余结点可以分为时，其余结点可以分为m m（m 0m

2、 0）个）个互不相交的有限集互不相交的有限集T T1 1,T,T2 2,T,T3 3 ,T ,Tm m，其中每一个集，其中每一个集合本身又是一棵树，且称为根的子树。合本身又是一棵树，且称为根的子树。 树的结构定义是一个递归的定义，即在树的定树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它说明了树的特性。义中又用到树的概念，它说明了树的特性。如在右图中，如在右图中， 是只有一个根结点的树是只有一个根结点的树 是有是有1313个结点的树个结点的树 其中其中A A是根，其余结点是根，其余结点分成三个分成三个互不相交的互不相交的子集：子集：T T1 1=B=B，E E，F F，K K，L

3、, L, T T2 2=C=C，G, TG, T3 3=D=D，H H，I I，J J，MM； T T1 1,T,T2 2,T,T3 3 都是都是A A的子树，且本身也是一棵树。的子树，且本身也是一棵树。则则同理按此同理按此分析方式分析分析方式分析 T T1 1 ,T ,T2 2,T,T3 3。A AA AB BC CD DE EF FG GH HI IJ JK KL LM M2.2.树的其它表示方法树的其它表示方法嵌套集合：是一些集合的集体，对于其中任何两个集合，嵌套集合：是一些集合的集体，对于其中任何两个集合，或不相交，或一个包含另一个的形式表示。或不相交，或一个包含另一个的形式表示。广义

4、表表示：根作为由子树森林组成的表的名字写在表的广义表表示：根作为由子树森林组成的表的名字写在表的左边。左边。凹入表示：类似书的编目。凹入表示：类似书的编目。GCABDHIJEKFLA* B* E* F* K* L* C* G* D* H* I* J*(A(B(E, F(K,L), C(G), D(H, I, J)ABCDEFGHIJKL3.3.树的基本术语树的基本术语结点：结点：数据元素数据元素+ +若干指向其子树的分支；若干指向其子树的分支；结点的度：结点的度：结点拥有的子树数；结点拥有的子树数；树的度：树的度：树中所有结点的度的最大值；树中所有结点的度的最大值；叶子结点：叶子结点：度为零的

5、结点，或称为终端结点；度为零的结点，或称为终端结点；分支结点：分支结点：度大于零的结点，或称为非终端结点；度大于零的结点，或称为非终端结点；结点的层次：结点的层次：假设根结点的层次为假设根结点的层次为1, 1, 若某结点在若某结点在第第i i层，则其子树的根在第层，则其子树的根在第i+1i+1层；层；A AB BD DE EF FH HI IJ JK KM M树的深度：树的深度：树中叶子结点所在的最大层次；树中叶子结点所在的最大层次；孩子结点：孩子结点：结点的子树的根；相应地该结点称为孩结点的子树的根；相应地该结点称为孩子的子的双亲结点双亲结点；兄弟结点：兄弟结点：同一个双亲的孩子之间称为兄弟

6、结点；同一个双亲的孩子之间称为兄弟结点；祖先：祖先：从根到该结点所经分支上的所有结点；从根到该结点所经分支上的所有结点；子孙：子孙：子树中任一结点；子树中任一结点；A AB BD DE EF FH HI IJ JK KM M3.3.树的基本术语树的基本术语有序树、无序树有序树、无序树 子树之间是否存在次序关系？子树之间是否存在次序关系？ 将树中结点的各子树看成从左至右是有次序的将树中结点的各子树看成从左至右是有次序的( (即不能互换即不能互换) ) 称称有序树有序树，否则称，否则称无序树无序树；森林：森林：是是m m（m0m0）棵互不相交的树的集合。）棵互不相交的树的集合。 任何一棵非空树是一

7、个二元组任何一棵非空树是一个二元组 Tree = Tree = （rootroot，F F） 其中：其中：rootroot被称为根结点，被称为根结点，F F被称为被称为子树森林；子树森林；A AB BD DE EF FH HI IJ JK KM M3.3.树的基本术语树的基本术语4.4.树结构和线性结构的比较树结构和线性结构的比较 第一个数据元素（无前驱）第一个数据元素（无前驱） 最后一个数据元素（无后继）最后一个数据元素（无后继） 其它元素（一个前驱、一个后继）其它元素（一个前驱、一个后继） 根结点（无前驱）根结点（无前驱） 多个叶子结点（无后继）多个叶子结点（无后继） 其它结点（一个前驱、

8、多个后继）其它结点（一个前驱、多个后继）线线性性结结构构树结构树结构5.5.树的抽象类型定义树的抽象类型定义ADT List ADT List 数据对象数据对象D D：是具有相同特性的数据元素的集合：是具有相同特性的数据元素的集合数据关系数据关系R R：数据关系：数据关系R R：若：若D D为空集，则称为空树；若为空集，则称为空树；若D D仅仅含一个数据元素，则含一个数据元素，则R R为空集，否则为空集，否则 R=H R=H，H H是如下是如下二元关系：二元关系： (1) (1) 在在D D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素rootroot，它在，它在关系关系H H下无前

9、驱；下无前驱； (2) (2) 若若D-root!=D-root!=，则存在，则存在 D-root D-root的一个划分的一个划分D D1 1，D D2 2，D Dm m (m0) (m0)，对任意，对任意jk(1jjk(1j，km)km)有有D Dj jDDk k=，且对任意的，且对任意的 i(1im)i(1im)，唯一存在数据，唯一存在数据元素元素x xi iDDi i，有，有rootHH；5.5.树的抽象类型定义树的抽象类型定义ADT List ADT List 数据关系数据关系R R： (3) (3) 对应于对应于 D-rootD-root的划分，的划分，H-rootH- ，root

10、 有唯一的一个划分有唯一的一个划分 H H1 1，H H2 2，H Hm m(m0)(m0)，对任意，对任意jk(1jjk(1j，km)km)有有 H Hj jHHk k=，对，对任意任意 i(1im)i(1im)，H Hi i是是D Di i上的二元关系，上的二元关系，(D(Di i，HHi i)是一棵符合本定义的子树，称为根是一棵符合本定义的子树，称为根rootroot的子树。的子树。基本操作：基本操作： ADT List ADT List 树的基本操作树的基本操作1 1）Root(T);Root(T);初始条件：树初始条件：树T T存在；操作结果：返回存在；操作结果：返回T T的根的根2

11、 2）Value(T, cur_e); Value(T, cur_e); 初始条件：树初始条件：树T T存在，存在， cur_ecur_e是是T T中某个结点中某个结点 操作结果：返回操作结果：返回cur_ecur_e的值的值3 3）Parent(T, cur_e);Parent(T, cur_e); 初始条件：树初始条件：树T T存在，存在， cur_ecur_e是是T T中某个结点。中某个结点。 操作结果：若操作结果：若cur_ecur_e是是T T的非根结点，则返回它的双的非根结点，则返回它的双 亲，否则其函数值为亲，否则其函数值为“空空”。4 4）TreeDepth(T);TreeDe

12、pth(T); 初始条件：树初始条件：树T T存在；操作结果：返回存在；操作结果：返回T T的深度。的深度。5 5）LeftChild(T, cur_e);LeftChild(T, cur_e); 初始条件：树初始条件：树T T存在，存在， cur_ecur_e是是T T中某个结点中某个结点 操作结果：若操作结果：若cur_ecur_e是是T T的非叶子结点，则返回它的最的非叶子结点，则返回它的最 左孩子，否则其函数值为左孩子，否则其函数值为 “ “空空”6 6）RightSibling(T, cur_e);RightSibling(T, cur_e); 初始条件：树初始条件：树T T存在，存

13、在， cur_ecur_e是是T T中某个结点中某个结点 操作结果：若操作结果：若cur_ecur_e有右兄弟，则返回它的右兄弟，有右兄弟，则返回它的右兄弟， 否否 则其函数值为则其函数值为“空空”7 7）TreeEmpty(T);TreeEmpty(T); 初始条件：树初始条件：树T T存在存在 操作结果：判别操作结果：判别T T是否为空树是否为空树8) TraverseTree(T, Visit();8) TraverseTree(T, Visit(); 初始条件：树初始条件：树T T存在。存在。VisitVisit是对结点操作的函数。是对结点操作的函数。 操作结果：按某种次序对操作结果：

14、按某种次序对T T的每个结点调用函数的每个结点调用函数 Visit()Visit()一次且至多一次一次且至多一次9 9）InitTree(&T); InitTree(&T); 操作结果：构造空树操作结果：构造空树T T1010）Assign(&T, cur_e, value); Assign(&T, cur_e, value); 初始条件：树初始条件：树T T存在，存在， cur_ecur_e是是T T中某个结点。中某个结点。 操作结果：结点操作结果：结点cur_ecur_e赋值赋值valuevalue。1111）DestroyTree(&T);Dest

15、royTree(&T); 初始条件：树初始条件：树T T存在存在 操作结果：销毁树操作结果：销毁树T T第第6 6章章 树和二叉树树和二叉树6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树 6.2.1 6.2.1 二叉树的定义二叉树的定义 6.2.2 6.2.2 二叉树的性质二叉树的性质 6.2.3 6.2.3 二叉树的存储结构二叉树的存储结构6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林6.6 6.6 赫夫曼树及其应用赫夫曼树及其应用6.2.1 6.2.1 二叉树的定义二叉树的定义 或者为空树；或者是由一个

16、根结点加上两棵或者为空树；或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树分别称为左子树和右子树的、互不相交的二叉树组成。二叉树的结点的子树要区分左子树和右子组成。二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。指出该子树是左子树还是右子树。二叉树的五种基本形态二叉树的五种基本形态二叉树的常用操作二叉树的常用操作 某些操作和树的基本操作类似，另由于二叉树本身特某些操作和树的基本操作类似，另由于二叉树本身特性，增加的操作有：性，增加的操作有： RightChild(T, e)

17、;RightChild(T, e); 初始条件：二叉树初始条件：二叉树T T存在，存在， e e是是T T中某个结点。中某个结点。 操作结果：返回操作结果：返回e e的右孩子，否则其函数值为的右孩子，否则其函数值为“空空”。 LeftSibling(T, e);LeftSibling(T, e); 初始条件：二叉树初始条件：二叉树T T存在，存在， e e是是T T中某个结点。中某个结点。 操作结果：返回操作结果：返回e e的左兄弟，若的左兄弟，若e e是是T T的左孩子或无左的左孩子或无左兄弟，则返回兄弟，则返回“空空”。PreOrderTraverse(T, Visit(); PreOrd

18、erTraverse(T, Visit(); 先序遍历先序遍历InOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); 中序遍历中序遍历PostOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); 后序遍历后序遍历LevelOrderTraverse(T, Visit();LevelOrderTraverse(T, Visit();层序遍历层序遍历6.2.2 6.2.2 二叉树的性质二叉树的性质性质性质1 1： 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结

19、点（个结点（i1i1）（利用归纳法容易证得此性质）（利用归纳法容易证得此性质）4 42 23 31 15 56 67 78 89 9101011111212131314141515性质性质2 2：深度为深度为K K的二叉树上至多含的二叉树上至多含2 2K K-1-1个结点（个结点（K1K1）（证明用求等比级数前（证明用求等比级数前k k项和的公式）项和的公式）1 12 23 34 44 42 23 31 15 56 67 78 89 9101011111212131314141515性质性质3 3： 对任一棵二叉树，若它含有对任一棵二叉树，若它含有n n0 0 个叶子结点，个叶子结点，n n2

20、 2 个度为个度为 2 2 的结点，则必存在关系式：的结点，则必存在关系式： n n0 0 = n = n2 2+1+1证明：证明：设二叉树上结点总数设二叉树上结点总数 n = nn = n0 0 + n + n1 1 + n + n2 2又二叉树上分支总数又二叉树上分支总数 B = nB = n1 1 + 2n+ 2n2 2而而 B = n -B = n - 1 = n1 = n0 0 + n + n1 1 + n + n2 2 - 1- 1由此，由此， n n0 0 = n = n2 2 + 1+ 12 23 31 14 45 56 67 78 89 9满二叉树满二叉树：深度为：深度为k

21、k且含有且含有2 2k k-1-1个结点的二叉树个结点的二叉树4 42 23 31 15 56 67 78 89 91010111112121313141415154 42 23 31 15 56 67 78 8完全二叉树完全二叉树：树中所含的：树中所含的n n个结点和满二叉树个结点和满二叉树 中编号为中编号为1 1至至n n的结点一一对应。的结点一一对应。4 42 23 31 15 56 67 78 89 910101111 12121313 141415154 42 23 31 15 56 67 78 89 910101111(a)(b)(c)完全二叉树的特点完全二叉树的特点(1) (1)

22、 叶子结点只可能在层次最大的两层上出现；叶子结点只可能在层次最大的两层上出现；(2) (2) 对任一结点，若其右分支下的子孙的最大层对任一结点，若其右分支下的子孙的最大层次为次为 L L，则其左分支下的子孙的最大层次必，则其左分支下的子孙的最大层次必为为 L L 或或 L+1L+1。 性质性质4 4：具有具有n n个结点的完全二叉树的高度为个结点的完全二叉树的高度为 loglog2 2n n + 1+ 14 42 23 31 15 56 67 78 89 9101011111212证明：证明： 设完全二叉树的高度为设完全二叉树的高度为h h，则有，则有 (2 (2h-1 h-1 -1 ) -1

23、 ) n n (2 (2h h -1) -1) 或或 2 2h-1 h-1 n n 2 2h h 两边取对数两边取对数 h-1h-1 log log2 2n n n2i n，则该结点无左孩子，否则，编号，则该结点无左孩子，否则，编号 为为2i2i的结点为其左孩子结点；的结点为其左孩子结点； 若若2i+1 n2i+1 n，则该结点无右孩子结点，否则，则该结点无右孩子结点，否则 ，编号为，编号为2i+12i+1的结点为其右孩子结点。的结点为其右孩子结点。4 42 23 31 15 56 67 78 89 91010111112126.2.3 6.2.3 二叉树的存储结构二叉树的存储结构 （1 1）

24、二叉树的顺序存储表示）二叉树的顺序存储表示（2 2）二叉树的链式存储表示）二叉树的链式存储表示1.1.二叉树的顺序存储表示二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 #define MAX_TREE_SIZE 100 / / 二叉树的最大结点数二叉树的最大结点数 typedef TElemType typedef TElemType SqBiTreeMAX_TREE_SIZE; SqBiTreeMAX_TREE_SIZE; / 0/ 0号单元存储根结点号单元存储根结点 SqBiTree bt;SqBiTree bt; 按照顺序存储结构的定义，在此约定，用一按照顺序

25、存储结构的定义，在此约定，用一组地址连续的存储单元依次组地址连续的存储单元依次自上而下、自左至右自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树存储完全二叉树上的结点元素，即将完全二叉树上编号为上编号为 i i的结点元素存储在如上定义的一维数的结点元素存储在如上定义的一维数组中下标为组中下标为 i-1 i-1 的分量中。的分量中。4 42 23 31 15 56 67 78 89 91010111112121 12 23 34 45 56 67 78 89 9101011111212数组下标：数组下标：0 1 2 3 4 5 6 7 8 9 10 110 1 2 3 4 5 6 7

26、 8 9 10 112 23 31 14 45 56 67 78 81 12 23 30 04 45 56 60 00 07 70 08 8 一般二叉树必须按完全二叉树的形式存储，一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。将造成存储的浪费。顺序存储结构的性能分析顺序存储结构的性能分析顺序存储结构仅适用于顺序存储结构仅适用于完全二叉树完全二叉树。因为，在最坏的情况下，一个深度为因为，在最坏的情况下，一个深度为k k且只有且只有k k个结点的单支树（树中不存在度为个结点的单支树（树中不存在度为2 2的结点）的结点）却需要长度为却需要长度为2 2k k-1-1的一维数组。这样就造成存的

27、一维数组。这样就造成存储空间的浪费。储空间的浪费。30301111555566660 02 26 61414红字红字为对应结点在顺序为对应结点在顺序结构中相应的位置结构中相应的位置下标下标2.2.二叉树的链式存储结构二叉树的链式存储结构 由二叉树的定义得知，二叉树的结点由一个由二叉树的定义得知，二叉树的结点由一个数据元素数据元素和分别指向其和分别指向其左、右子树左、右子树的两个分支构的两个分支构成，则表示二叉树的链表中的结点至少包含三个成，则表示二叉树的链表中的结点至少包含三个域：域：数据数据和和左、右指针域左、右指针域。DATADATALChildLChildRChildRChildPare

28、ntParent二叉树的结点二叉树的结点DBCEFAECBDF二叉链表二叉链表lchildDatarchildA二叉树的二叉链表存储表示二叉树的二叉链表存储表示typedef struct BiTNode typedef struct BiTNode TElemType data; TElemType data; struct BiTNode struct BiTNode * *lchild,lchild,* *rchild; rchild; / / 左右孩子指针左右孩子指针BiTNode, BiTNode, * *BiTree;BiTree;parentAECBDF三叉链表三叉链表rchil

29、dDatalchildBDCEFA二叉树的三叉链表存储表示二叉树的三叉链表存储表示typedef struct TriTNode typedef struct TriTNode TElemType data; TElemType data; struct TriTNode struct TriTNode * *lchild,lchild,* *rchild; rchild; / / 左右孩子指针左右孩子指针 struct TriTNode struct TriTNode * *parent; / parent; / 双亲指针双亲指针 TriTNode, TriTNode, * *TriTree

30、;TriTree; 在不同的存储结构中，实现二叉树的操作方在不同的存储结构中，实现二叉树的操作方法亦不同，如找结点法亦不同，如找结点 x x 的双亲的双亲 PARENT(TPARENT(T，e)e)，在三叉链表中很容易实现，而在二叉链表中则需在三叉链表中很容易实现，而在二叉链表中则需从根指针出发巡查。从根指针出发巡查。 由此，在具体应用中采用什么存储结构，除由此，在具体应用中采用什么存储结构，除了根据二叉树的形态之外，还应考虑需进行何种了根据二叉树的形态之外，还应考虑需进行何种操作。操作。总结总结 本讲我们学习了树和二叉树的定义，重点介本讲我们学习了树和二叉树的定义，重点介绍了二叉树的性质和存储结构，二叉树是非常重绍了二叉树的性质和存储结构，二叉树是非常重要的数据结构，请同学们重点掌握，在下一讲中要的数据结构，请同学们重点掌握，在下一讲中我们将学习二叉树的遍历和线索化操作。我们将学习二叉树的遍历和线索化操作。练习题练习题1. 1. 假设在树中，结点假设