《第4章 计算机软件技术基础理论》由会员分享，可在线阅读，更多相关《第4章 计算机软件技术基础理论（67页珍藏版）》请在金锄头文库上搜索。
1、第4章 树,树与图属于非线性结构,4. 1 树的概念,4.1树的概念树型结构应用举例,“资源管理器” 界面。,4.1树的概念树的结构定义,树(Tree)是n(n=0)个结点的有限集合。当n=0时，称为空树；当n0时，称为非空树。在任意一棵非空树中：（1）有且仅有一个特定的结点，称为树根(root)，它没有直接前驱，但有零个或多个直接后继 （2）当n1时，其余结点被划分成m个互不相交的子集，每个子集又是一棵树，被称为子树(subtree)。,4.1树的概念树的表示方法（层次）,a,b,c,d,g,h,i,j,f,e,m,l,k,4.1树的概念树的表示方法（集合）,4.1树的概念树的表示方法（凹凸
2、图）,4.1树的概念树的表示方法（广义表）,(a(b(e(k,l),f),c(g),d(h(m),i,j),4.1树的概念基本术语,结点 结点的度，树的度 叶子(终端结点) 非终端结点 结点的层次树的深度 有序树，无序树 森林,a,b,c,d,g,h,i,j,f,e,m,l,k,4.1树的概念基本术语,孩子 双亲 兄弟 祖先 子孙 堂兄弟,a,b,c,d,g,h,i,j,f,e,m,l,k,4. 2 二叉树的基本概念和主要性质,二叉树定义,二叉树 由n(n=0)个元素组成。当n=0时，为空二叉树；当n0时，有且仅有一个元素为根，其余结点分成最多两个互不相交的子集，子集有左右顺序，每个子集又是一
3、个二叉树。,4.2二叉树的概念和性质定义,4.2二叉树的概念和性质二叉树的五种形态,R L L R,满二叉树,深度为k，且有2k-1个结点的二叉树。,4.2二叉树的概念和性质满二叉树,完全二叉树:一棵深度为h，结点数为n的二叉树，如果其结点1n的位置序号分别与满二叉树的结点1n的位置序号一一对应，则为完全二叉树。,满二叉树 完全二叉树,4.2二叉树的概念和性质完全二叉树,二叉树性质（性质1）,在二叉树的第i层上至多有2 i-1个结点。证明：(数学归纳法) i=1，只有根结点， 2 i-1=20=1 成立设 1ji，2 j-1成立,即 j=i-1，2 j-1=2 i-2则第i层至多有2 i-2*
4、2=2 i-1,4.2二叉树的概念和性质二叉树性质,二叉树性质（性质2）,深度为h的二叉树至多有2h-1个结点。证明:利用性质1 20+21+22+23+.+2 h-1=2h-1,4.2二叉树的概念和性质二叉树性质,二叉树性质（性质3）,对于一个非空的二叉树，若其具有n0个叶子结点，有n2个度为2的结点，则有:n0=n2+1证明: n=n0+n1+n2 (1) B=n1+2n2; n=B+1 n=n1+2n2+1 (2)(2)-(1)得: n0=n2+1,4.2二叉树的概念和性质二叉树性质,二叉树性质（性质4）,具有n个结点的完全二叉树的深度为 log2n+1。证明: 设深度为k,则有: 2
5、k-1-1n=2k-1 2 k-1=n2k k-1=log2n1，则序号为i的结点的双亲结点序号为 i/2 ；如2in，则序号为i的结点无左孩子；如2in，则序号为i的结点的左孩子结点的序号为2i ；如2i1n，则序号为i的结点无右孩子；如2i1n，则序号为i的结点的右孩子结点的序号为2i1。,4.2二叉树的概念和性质二叉树性质,4. 3 二叉树的存储,顺序存储结构：顺序存储就是用一组地址连续的存储单元来存放一棵二叉树的结点。 适用于存储完全二叉树或满二叉树。,4.3二叉树的存储顺序存储结构,二叉树顺序存储结构定义=typedef struct DataType data ; int num；
6、 BTree;,4.3二叉树的存储顺序存储结构,链式存储结构：二叉树的链式存储结构是用链表来表示二叉树。,4.3二叉树的存储链式存储结构,4.3二叉树的存储链式存储结构,二叉树链式存储结构定义=typedef struct BTNode DataType data; struct BTNode *lchild, *rchild;BTree;,4.3二叉树的存储链式存储结构,4.4 二叉树的遍历,遍历二叉树：按某种搜索路径巡访二叉树中每个结点一次且仅一次的过程。,访问顺序有： DLR, DRL LDR, RDL LRD, RLD,4.4 二叉树的遍历遍历的概念,遍历二叉树,DLR 先序遍历LDR
7、 中序遍历LRD 后序遍历,4.4 二叉树的遍历遍历的概念,PreOrder: a b c d e g f h,InOrder: c b e g d f a h,PostOrder: c g e f d b h a,4.4 二叉树的遍历遍历的概念,先序遍历递归算法,Void DLR (BTree *T) if (T) Visit(T-data); DLR (T-lchild) ; DLR(T-rchild) ; ,4.4 二叉树的遍历遍历的算法,中序遍历递归算法,Void LDR (BTree *T) if (T) LDR (T-lchild) ; Visit(T-data); LDR(T-r
8、child) ;,4.4 二叉树的遍历遍历的算法,后序遍历递归算法,Void LRD (BTree *T) if (T) LRD (T-lchild) ; LRD (T-rchild) ; Visit(T-data); ,4.4 二叉树的遍历遍历的算法,层次遍历算法步骤,要借助于队列结构实现分两步进行：（1）访问队头结点；（2）将该结点非空左右子树进队；重复上两步操作，直到队列为空为止。,4.4 二叉树的遍历遍历的算法,层次遍历算法,Void LOrder (BTree *T) BTree *qMAX; int f,r; if (!T) return; f=0;r=1; q0=T; while
9、 (f!=r)Visit(qf- data); if (qf-Lchild) qr= qf-Lchild;r+; if (qf-Rchild) qr= qf-Rchild;r+; f+; ,4.4 二叉树的遍历遍历的算法,二叉树遍历算法应用1,由遍历序列恢复二叉树由二叉树的先序遍历和中序遍历序列或后序遍历和中序遍历序列可以恢复二叉树。由二叉树的先序遍历或后序遍历序列确定根结点，由二叉树的中序遍历序列确定左右子树。例：先序遍历序列：ABCDEFGHI 中序遍历序列：BCAEDGHFI,4.4 二叉树的遍历遍历的算法,二叉树遍历算法应用2,统计二叉树T中叶结点的数目int count(BTree
10、*T) if (T= NULL) return 0; if (T-Lchild = NULL &T-Rchild = NULL) return 1; return count (T-Lchild) + count (T-Rchild);int count=0;Void LDR (BTree *T) if (T) LDR (T-lchild) ; if (!T-Lchild) & (!T-Rchild) count+; LDR(T-rchild) ;,4.4 二叉树的遍历遍历的算法,二叉树遍历算法应用3,在二叉树T中查找值为x的结点BTree *p=NULL;void find (BTree *
11、T,DataType x) if (T-data=x) p=T; else if (T-Lchild) find (T-Lchild,x); if (T-Rchild) find (T-Rchild,x);,4.4 二叉树的遍历遍历的算法,二叉树遍历算法应用4,表达式,a+b*(c-d)-e/f,4.4 二叉树的遍历遍历的算法,先序序列：(波兰式) -+a*b-cd/ef中序序列： a+b*c-d-e/f后序序列：(逆波兰式) abcd-*+ef/-,4.4 二叉树的遍历遍历的算法,表达式,4.5 二叉树的应用,基本概念,路径长度树的路径长度树的带权的路径长度,4.5 二叉树的应用哈夫曼树,7
12、,5,2,4,WPL=(7+5+2+4)*2=36,4.5 二叉树的应用哈夫曼树,树的带权的路径长度WPL,WPL=7*2+2*1+5*3+4*3=43,WPL=2*2+7*1+5*3+4*3=38,结论：树型和每个权值的位置都可能影响WPL。,4.5 二叉树的应用哈夫曼树,哈夫曼树：WPL最小的二叉树称为最优二叉树。哈夫曼树被广泛的应用在各种技术中，其中最典型的就是在编码技术上的应用。利用哈夫曼树，我们可以得到平均长度最短的编码。,4.5 二叉树的应用哈夫曼树,在电文传输中，通常将文字转换成二进制编码等长编码 ABACCDAA 00 B 01 C 10 D 11发送 000100101011
13、00译码 ABACCDA特点 ：译码方便，无二义性,4.5 二叉树的应用哈夫曼树,不等长编码A 0 B 1 C 01 D 100 1 0 0 1 0 1 1 0 0问题：无法译码原因：某编码可能是另一个编码的前缀,4.5 二叉树的应用哈夫曼树,前缀编码(哈夫曼编码)A0 B 10 C 110 D 111特点：任何编码均不是其他 编码的前缀0 1 0 0 1 1 0 1 1 0 1 1 1 0译码无二义性,4.5 二叉树的应用哈夫曼树,应用举例,已知某系统在通信联络中只可能出现 8 种字符，其频率分别为：0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，试设计哈夫曼编码。,4.5 二叉树的应用哈夫曼树,
