《算法与数据结构课件_dsc6》由会员分享，可在线阅读，更多相关《算法与数据结构课件_dsc6（35页珍藏版）》请在金锄头文库上搜索。
1、第六章. 树和二叉树 （Chapter 6. Tree and Binary Tree) 6.1 树的定义及基本操作 树型结构是一种非常重要的非线性数据结构，可 广泛应用于描述家族关系或行政组织机构。 树是 n (n0) 个结点的有限集。在一棵非空树中， 有且仅有唯一的根（root）结点，当 n1 时，除根结点 外其余结点可分为 m (m0)个互不相交的有限集，它们 本身也是一棵树，称为根的子树（subtree）。 A BC EFG D 一棵树如右图所示： 树还可以用下面的 形式化描述来表示： Tree = （D,R） 其中：D= ai | aiD0, i=1,2,n, n0 R= H H 为
2、如下描述的二元关系： 1、在 D 中存在唯一的根元素 root，它在关系 H 下无 前驱； 2、若D - root，则存在 D - root 的一个划分 D1, . , Dm (m0)，对任意一对 jk ( 1j, k m) 有 Dj Dk = ，且对任意的 i ( 1i m)，唯一存在数据元素xi Di，有 H； 3、对于 D - root 的划分，H - , , 有唯一的划分 H1 , H2 , . , Hm ( m0 )，对任意 一对 jk ( 1j , k m) 有Hj Hk = ，且对任意的 i ( 1i m)，Hi 是 Di 上的二元关系，且 ( Di , Hi ) 也是一棵符合本
3、定义的树，称为 root 的子树。 树的一些基本术语： 结点的度（degree） 结点所拥有的子树的数目。 叶子结点（leaf-又称终端结点 terminal node） 度为零的结点。 度不为零的结点。 孩子（ child-也称儿子 son） 结点的子树的根称为结点的孩子。 分支结点（branch node -又称非终端结点 non-terminal node ） 双亲（ parent） 结点是其孩子的双亲。 祖先（ forefather） 从树根到双亲的所有结点称为该结点的祖先。 子孙（progeny） 以结点为根的子树的所有结点称为该结点的子孙。 兄弟（sibling） 同一父母的所有孩
4、子互称兄弟。 层次（level） 树根为第一层，其孩子为第二层，孙子为第三层 ，以此类推。 有序树（ordered tree） 结点各子树从左至右是有秩序的树称为有序树。 无序树（unordered tree） 结点各子树没有秩序的树称为无序树。 森林（forest ） 森林是 m (m0) 棵互不相交的树的集合。 堂兄弟（cousin） 双亲在同一层的结点互称堂兄弟。 深度（depth） 树中结点的最大层次称为树的深度。 树的基本操作： InitiateRoot Traverse Child Crt_TreeClearIns_ChildDel_Child Right_Sibling Pare
5、nt 6.2 二叉树 二叉树（binary tree）是一棵度为二的树，其孩子有 左右之分，也分别都是二叉树。 二叉树的基本操作： InitiateRootParentL(R)child Crt_btClearIns_L(R)child Del_L(R)child Traverse L(R)sibling 性质一、在二叉树的第 i 层上最多有 2i -1 个结点（i1）。 性质二、深度为 k 的二叉树最多有 2k-1个结点（k1）。 性质三、对任一二叉树，叶子结点数为 n0，度为2的结点 数为 n2，则 n0 = n2 +1。 性质四、具有 n 个结点的完全二叉树的深度为 log2n +1。
6、满二叉树（full binary tree）：一棵深度为 k 且有 2k-1个结 点的二叉树称为满二叉树。 二叉树的性质： 完全二叉树（complete binary tree）：一棵深度为 k 的满 二叉树的第 k 层的右边几个结点不存在则为完全二叉树。 性质五、对一棵有 n 个结点的完全二叉树从上到下、从左 到右进行连续编号，则对任一结点 i (1in) 有： 1、i=1的结点是树根，i1 的结点的父母为 i / 2 ； 2、若左右孩子存在，则分别为 2i 和 2i+1 结点。 二叉树的存储结构： A B DEF C 1、顺序存储结构： A、按完全二叉树存储 A B C DE F 1 2
7、3 4 5 6 7 A B DEF C B、用父母指针存储 ABC DEF 0-11-2 -33 1 2 3 4 5 6 2、链式存储结构： 用二叉链表存储 A B C DEF #define maxlen user_supply typedef elemtype comptree maxlen; #define maxlen user_supply typedef struct elemtype data; int parent ; node; struct node btree maxlen; typedef struct node elemtype data; struct node *
8、lchild, *rchild; node, *bitptr; 作 业 13. 一棵满 k 叉树按层次顺序从 1 开始对全部 结点编号，若所求结点存在，则： 1、各层的结点数目是多少？ 2、编号为 n 的结点的父结点的编号是多少？ 3、结点 n 的第 i 个儿子的编号是多少？ 4、结点 n 有右兄弟的条件是什么？ 14. 已知一棵度为 m 的树中有 ni 个度为 i 的 结点，则该树中有多少个叶子结点。 6.3 二叉树的遍历和线索二叉树 遍历二叉树（ traversing binary tree） 即按某种搜索顺序对二叉树中每个结点访问且仅访问一次。 根据搜索路径的不同，二叉树的遍历分为八种：
9、 1、前序遍历（preorder traversal） DLR 2、中序遍历（inorder traversal） LDR 3、后序遍历（postorder traversal） LRD 4、逆前序遍历（inverse preorder traversal） DRL 5、逆中序遍历（inverse inorder traversal） RDL 6、逆后序遍历（inverse postorder traversal） RLD 7、按层次遍历（level-by-level traversal） 8、按层次逆遍历（ inverse level-by-level traversal） A B DEF
10、C 1、ABDCEF2、DBAECF 3、DBEFCA4、ACFEBD 5、FCEABD6、FECDBA 7、ABCDEF8、ACBFED void Preorder ( struct node *t ) if ( t ) visit ( t ); Preorder (t-lchild); Preorder (t-rchild); void Inorder ( bitptr t ) if ( t ) Inorder (t-lchild); visit ( t ); Inorder (t-rchild); void Postorder ( struct node *t ) if ( t ) Po
11、storder (t-lchild); Postorder (t-rchild); visit ( t ); void Preorder (struct node * t) /前序遍历的非递归算法 Inistack(s); if ( t ) Push( s, t ); while ( ! Empty( s ) Pop( s, t ); visit( t ); if ( t-rchild ) Push( s, t-rchild ); if ( t-lchild ) Push( s, t-lchild ); void Postorder (struct node * t) /后序遍历的非递归算法
12、Inistack(s); while ( t | ! Empty(s) while ( t ) Push( s, ( t , L); t=t-lchild; tag=R; while ( !Empty(s) if (tag=L) Push( s, (t, R); t=t-rchild; else visit( t ); t=NULL; void Levelorder ( struct node * t ) / 按层次遍历的算法 Iniqueue( q); if ( t ) Enqueue( q, t ); while (! Empty( q) t = Dequeue( q); visit( t
13、 ); if ( t- lchild) Enqueue( q, t - lchild ); if ( t- rchild) Eequeue( q, t - rchild ); 能否用任意两 种遍历的序列 来生成一棵唯 一的二叉树？ * + a e f + / b - c d 前序： * + a / b - c d + e f 中序： a + b / c - d * e + f 表达式： ( a + b / ( c - d ) ) * ( e + f ) 后序： a b c d - / + e f + * 中序遍历时括号怎么加上？ 能够用前序遍历和中序遍历或者用中序遍历和后序遍 历唯一的确定一棵
14、二叉树，但不能用前序遍历和后序遍历 唯一的确定一棵树，为什么？ 中序遍历序列是 LDR，可以用来分出左右孩子。 而前序和后序遍历是DLR和LRD，不能分出左右孩子。 二叉树遍历的应用： 作 业 15. 已知在二叉链表表示的二叉树中 ，root 为根结点， p和 q为二叉树中 两个结点，试编写算法求距离它们最近 的共同祖先。 16. 试给出算法求二叉链表表示的二叉 树的直径（高度、最大层次数）以及长 度等于直径的一条路经（从根到叶子的 结点序列）。 作 业 17. 试给出算法将二叉树表示的 表达式按中序遍历输出并加上相 应的扩号。 线索二叉树（ threaded binary tree） 在二叉
15、树的遍历序列中很容易就找到每个结点的前驱 和后继，但要在二叉树中找这个结点的前驱和后继就很困 难。如何解决这个问题呢？ 方法之一是将二叉链表扩展为四叉链表，亦即加上指 向前驱和后继的指针，但这将浪费许多空间。有没有更好 的办法呢? 方法之二即是使用线索二叉树，该方法是由 A.J.Perlis 和 C.Thornton 二人提出的。 一棵二叉链表表示的二叉树有 n+1 个空指针，可以利 用这些空指针来存储结点的前驱和后继，这即是线索。为 了区分到底是孩子指针还是线索，还需在每个结点内设置 两个标志位 ltag 和 rtag，标志位为0，表示是孩子指针；标 志位为 1，则表示是线索。其中 lchild 指向前驱，rchild 指 向后继。 对二叉树以某种遍历使其变为线索二叉树的过程即称 为线索化。 下面是一棵二叉树的中序线索树： A B C DEF 000000 0000
