《数据结构树.ppt》由会员分享，可在线阅读，更多相关《数据结构树.ppt（63页珍藏版）》请在三一文库上搜索。
1、树和二叉树,1,版权所有, 1997 (c) Dale Carnegie & Associates, Inc.,树的初步认识,树的定义：树(tree)是n0个结点的有限集合。 当n0时称为空树。 当n1时只包含一个根节点 当n0时除根结点外；其余的结点Tt被分割成m0个不相交的有穷子集T1Tm，其中每个这样的子集Ti(im)本身又是一棵树，称为根结点的子树。由此可见，树的定义是一个递归定义。,2,树的逻辑表示,3,树的基本术语,结点的度和树的度 每个结点具有的子树数或者说后继结点数 被定义为该结点的度(degree)。所有结点 的度的最大值被定义为该树的度。 分支结点和叶结点 度大于0的结点称
2、作分支结点或非终端结 点；度等于0的结点称作叶结点或终端结 点。,4,树的基本术语,儿结点、父结点和兄弟结点 每个结点的子树的根，或者说每个结点的后继， 被习惯地称作该结点的儿结点(child)，相应地， 该结点被称作儿结点的父结点。具有同一父结点 的儿结点互称兄弟(sibiling)。 结点的层数和树的高度 树既是一种递归结构，也是一种层次结构，树中 的每个结点都处在一定的层次上。结点的层数 (level)从树根开始定义，根结点为第一层，它 的孩子结点为第二层，以此类推。树中结点的最 大层数称为树的深度(depth)或高度(height)。,5,树的基本术语,有序树和无序树 若树中各结点的子
3、树是按照一定的次序从左向右 安排的，则称之为有序树，否则称之为无序树。 森林 森林是m(m0)棵互不相交的树的集合。,6,二叉树的定义,二叉树(binary tree)是指树的度为2的有序树。它 是一种最简单、而且最重要的树。 递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树。,7,二叉树的五种基本形态,8,二叉树的基本性质1*,任意非空二叉树中，若叶结点的数目为n0，度为2 的结点数目为n2，则有关系：n0= n2+1 证明： 二叉树的结点总数n为 n= n0+n1+n2 n=B+1= n1+2n2+1 所以
4、 n0+n1+n2 = n1+2n2+1 即 n0= n2+1,9,二叉树的基本性质2 *,一棵非空二叉树的第i层最多有2i-1个结点(i1),10,二叉树的基本性质3 *,高度为k的二叉树最多有2k-1个结点(k1) 显然，高度为k的二叉树只有在每一层都达到最 大结点数时，整个二叉树的结点数才能达到最大。 即当每层的结点数目都达到该层的最大结点数2i-1 时（性质2），对应的二叉树的结点数目取得最 大值(等比数列求和),11,满二叉树和完全二叉树,若一棵二叉树高度为k且有2k-1个结点，则称该二叉树为满 二叉树。满二叉树的特点就是每层的结点数目都达到该层 的最大结点数。,12,满二叉树和完全
5、二叉树,一个深度为K具有N个节点的二叉树，若其节点的编号与 深度为K的满二叉树编号为1n的节点完全对应，则称之 为完全二叉树,13,1,8,3,2,7,6,5,4,15,14,13,12,11,10,9,完全二叉树的基本性质4*,具有n0个结点的完全二叉树的高度k=log2n+1 。 根据完全二叉树定义以及二叉树的性质3，有： 2k-11 n2k1 或 2k-1n 2k 由上式可推出 k1log2n k 由于k为正整数，因此 k= log2n+1 *表示不大于*的最大整数,14,klog2n+1 klog2n,完全二叉树的基本性质5*,父子序号规律 若对具有n个结点的完全二叉树按层次从上到下，
6、每层从左至右的规则对结点编号，则序号为i的结点具有以下性质. 若i1，则序号为i的结点的双亲结点的序号为i/2；当i=1时，则对应结点为二叉树的根结点，没有双亲结点。 若2in，则序号为i的结点的左孩子结点的序号为2i；若2in，则序号为i的结点无左孩子。 若2i1n，则序号为i的结点的右孩子结点的序号为2i+1；若2i+1n，则序号为i的结点无右孩子。,15,A,B,C,D,E,二叉树的存储结构,一维数组表示法： 用一组连续的存储单元存储二叉树的数据元素。为了反映各结点在二叉树中的位置及相互关系，必须适当安排各结点的存储次序。,16,二叉树的链式存储结构,二叉链表： struct BTree
7、Node T data; BTreeNode *lchild, *rchild; ；,17,二叉树的链式存储结构,三叉链表： struct BTreeNode T data; BTreeNode *parent, *lchild, *rchild; ；,18,二叉树结点类的定义,template class BTree; template class BSTree; template class BTreeNode friend class BTree ; friend class BSTree ; T data; BTreeNode *lchild,*rchild; public: BTre
8、eNode():lchild(NULL),rchild(NULL); BTreeNode(T d, BTreeNode *l=NULL, BTreeNode *r=NULL) :data(d),lchild(l),rchild(r); T getdata()return data; BTreeNode *getleft()return lchild; BTreeNode *getright()return rchild; ;,19,二叉树类的定义,template class BTree T *a; int n; BTreeNode *build0(int i); protected: BTr
9、eeNode *root; public: BTree(BTreeNode *p=NULL) copybt(root,p); BTree(T a,int n);/由T类型的数组a的n个元素构造二叉树 int num(); static int num(BTreeNode *p); int dep(); static int dep(BTreeNode *p); bool equal(BTree,20,建立二叉链表,21,建立二叉链表 构造函数,template BTree: BTree(T a,int n) this-a=a; this-n=n; root=build0(1); BTreeNo
10、de * build0(int i) 功能：以数组a中的第i个元素（下标为i-1）为根结点，递归地创建二叉链表，并返回指向该链表的指针。 处理过程： (1) 若序号为i的数组元素存在，即i小于等于数组的长度且数组的第i个元素非空，则创建一个结点作为根结点，在其数据域中存放数组的第i个元素。 (2) 以2*i为参数，调用build0创建左子树，并挂在该结点的左支上。 (3) 以2*i+1为参数，调用build0创建右子树，并挂在该结点的右支上。,22,建立二叉链表 递归函数的程序代码,template BTreeNode * BTree:build0(int i) BTreeNode *p; i
11、nt l,r; if (i ; p-data=ai-1; l=2*i; r=2*i+1; p-lchild=build0(l); p-rchild=build0(r); return(p); else return(NULL); ,23,template BTreeNode * BTree:build0(int i) BTreeNode *p; int l,r; if (i ; p-data=ai-1; l=2*i; r=2*i+1; p-lchild=build0(l); p-rchild=build0(r); return(p); else return(NULL); ,计算二叉树结点个数
12、,int num(BTreeNode *p) 功能:返回p所指向的二叉树的结点个数， 处理过程： 1)若p为NULL则返回0；否则 2)通过递归调用求出左、右子树的结点个数，并返回两者之和加1 template int BTree:num(BTreeNode *p) if(p=NULL) return(0); else return(num(p-lchild)+num(p-rchild)+1); 实例函数，求当前对象中的结点个数： template int BTree:num() return(num(root); ,24,计算二叉树结点个数,template int BTree:num(BT
13、reeNode *p) if(p=NULL) return(0); else return(num(p-lchild)+num(p-rchild)+1); ,25,num(root)=?,num(B)=?,num(D)=?,num(H)=?,num(I)=?,0,0,1,0,0,1,3,0,4,num(C)=?,num(F)=?,num(G)=?,0,0,1,0,0,1,3,8,互动环节:计算二叉树的高度,int dep(BTreeNode *p) 功能:返回p所指向的二叉树的高度， 处理过程： (1)若p为NULL则返回0，否则； (2)求出左、右子树的高度l1、l2并返回max(l1+ l
14、2)+1。,26,互动环节:计算二叉树的高度,template int BTree:dep(BTreeNode *p) int max; if(p=NULL) return(0); else max=dep(p-lchild); if (dep(p-rchild)max) max=dep(p-rchild); return(max+1); 实例函数求当前对象中的高度： template int BTree:dep() return(dep(root); ,27,判断两个二叉树相等,bool equal(BTreeNode *p, BTreeNode *q) 功能:为判断p、q所指向的两棵二叉树
15、是否相等，若相等则返回true否则返回false 处理过程： (1) 若p、q均为空，则返回true；否则， (2)若p、q中有一个为空，则返回false；否则 (3)若结点数据和左右子树均相等，则返回true,否则返回false。 template bool BTree:equal(BTreeNode *p,BTreeNode *q) bool b; if(p=NULL ,28,判断两个二叉树相等,equal函数的另一种形式是实例函数： bool equal(BTree ,29,复制二叉树：拷贝函数,void copybt(BTree ,30,复制二叉树：递归函数,void copybt(B
16、TreeNode * 要注意的是参数p是结点指针类型，其值会有所改变，因此必修加上引用符号&。,31,二叉树的遍历,二叉树的遍历是指按照一定次序访问树中所有结 点，并且每个结点仅被访问一次的过程。 按根节点被访问的先后可分为先序、中序、后序 先序：根节点、左子树、右子树 中序：左子树、根节点、右子树 后序：左子树、右子树、根节点 显然，遍历左、右子树的问题仍然是遍历二叉树 的问题，所以二叉树的这三种遍历方式可以用递 归算法实现。,32,二叉树的遍历,先序：根节点、左子树、右子树 A B D H I C F G 中序：左子树、根节点、右子树 H D I B A F C G 后序：左子树、右子树、
17、根节点 H I D B F G C A,33,H,I,中序遍历的递归函数与实例函数,void inorder(BTreeNode *p,void visit(BTreeNode *p) 功能:对p所指的二叉树进行中序遍历，对每个结点执行visit函数的操作， 处理过程：若p非空，则 (1)中序遍历p所指结点的左子树。 (2)对根结点执行visit函数的操作。 (3) 中序遍历p所指结点的右子树。 另一种形式的inorder函数不设置结点指针参数，是对当前二叉树进行中序遍历，称为实例函数。 void BTree:inorder(void visit(BTreeNode *p),34,中序遍历的递
18、归函数与实例函数,template void BTree:inorder(void visit(BTreeNode *p) inorder(root,visit); cout void BTree:inorder(BTreeNode *p, void visit(BTreeNode *p) if (p!=NULL ) inorder(p-lchild,visit); visit(p); inorder(p-rchild,visit); 先序、后序遍历的递归函数也与之类似,35,中序遍历递归函数的执行过程,执行过程：,36,In(-),In(C),显示(-),In(*),显示(a),显示(*),
19、显示(b),显示(C),In(b),In(a),-,*,C,a,b,表达式的逆波兰表示,（a+b）*（c-d） 先序遍历 先序序列 中序遍历 中序序列 后序遍历 后序序列（逆波兰表示）ab+cd-*,37,*,+,-,a,b,c,d,中序遍历的非递归函数,void inorder1(void visit(BTreeNode *p) 其功能为对当前二叉树进行非递归的中序遍历，执行visit函数的操作，其处理过程为： (1) 栈初始化，根结点进栈。 (2) 若栈非空，则栈顶结点的左儿子相继进栈，直至NULL退栈；访问栈顶结点（执行visit函数的操作）并使栈顶结点的右儿子成为栈顶结点。 (3) 重
20、复执行步骤(2)直至栈为空。,38,中序遍历的非递归函数,template void BTree:inorder1(void visit(BTreeNode *p) BTreeNode *stack10,*p; int top; s=“; top=0;stacktop=root; while(top=0) while(stacktop!=NULL) p= stacktop-lchild; stack+top=p; top-; if (top=0) p=stacktop; visit(p); stacktop=p-rchild ; coutendl; ,39,-,*,c,a,b,互动环节：二叉树
21、显示,为二叉树类增设一个打印二叉树的成员函数，按二叉树的凹入表示法打印二叉树，其输出的形式相当于把二叉树逆时针旋转90度。 设计思想：该算法的设计思想与中序遍历二叉树相类似。由于把二叉树逆时针旋转90度后显示在上方的右子树，然后是根节点，最后是左子树，所以该算法是一种特殊的中序遍历算法。为了使不同层次中的结点显示在不同的位置上，在递归函数中设置一个表示递归调用深度的参数。递归打印函数的程序代码如下：,40,互动环节：二叉树显示,template void BTree:prnt(BTreeNode *p, int l) if (p!=NULL ) prnt(p-rchild,l+1); for
22、(int i=0;idatalchild,l+1); void prnt()prnt(root,1);,41,互动环节：重置函数及其测试,template void BTree:setroot(BTreeNode *p) dest(root); copybt(root,p); void main( ) char *str2=“abcd f“; BTreebt2(str2,6); bt2.prnt(); BTreeNode *p1=new BTreeNode(x,NULL,NULL); BTreeNode *p2=new BTreeNode(y,NULL,NULL); BTreeNode *p3
23、=new BTreeNode(z,p1,p2); bt2.setroot(p3); bt2.prnt(); c f a b d y z x,42,排序二叉树的定义,排序二叉树或为空树或为满足具有以下特点的二 叉树： （1）所有结点的（数据）值均不相同； （2）若左子树为非空，则左子树中所有结点 的值均小于根结点的值； （3）若右子树为非空，则右子树中所有结点 的值均大于根结点的值； （4）左子树和右子树均是排序二叉树。,43,排序二叉树的动态生成过程,32,16,43,14,25,57,18,52,61,44,32,57,43,18,61,52,16,25,14,P=nil,32,16,32,
24、43,16,25,14,32,排序二叉树类的定义,template class BSTree : public BTree public: BSTree(BTreeNode *p=NULL)root=p; T minv(); T maxv(); BTreeNode *sear(T el); /查找实例函数 BTreeNode *sear1(T el); /非递归查找函数 static BTreeNode *sear(T el, BTreeNode *bst);/递归查找函 数 void inst(T el); /插入实例函数 void inst1(T el); /非递归插入函数 static
25、void inst(BTreeNode *p, BTreeNode *,45,求排序二叉树的最值,T minv() 功能:返回当前排序二叉树中结点关键码的最小值。 处理过程： 使p=root，若p为空，则显示相应的信息，否则 (1) 若p所指结点有左儿子，则令p指向该结点； (2) 重复(1)，直至p所指结点的左儿子链为空； (3) 返回p所指结点的关键码。 程序代码为： template T BSTree:minv() BTreeNode *p=root; if (p=NULL) coutlchild!=NULL) p=p-lchild; return p-data; ,46,树与森林,森林
26、是m(m0)棵互不相交的树的集合。 树 当节点个数 n0 时由根节点与M棵子树构成 的森林所构成。,47,树的存储结构：儿子双亲表示法,把树中每个结点的儿子节点排列起来，用单链表 来存储；而每个单链表的头指针又组成一个线性 表，同时在线性表的元素中又增加父节点的序 号，构成儿子双亲表示法,48,树的存储结构：儿子兄弟表示法,依据：从最先的祖先开始，只要能确定家属中每 个人的儿子与兄弟，即可找到家属中的每个人。,49,树、森林转换成二叉树,树转换成二叉树 转换方法：用儿子兄弟表示法表示一棵树，并将 儿子链看作为左子树，将兄弟链看作为右子树。,50,e,d,a,c,b,e,d,a,c,b,树、森林
27、转换成二叉树,森林转换成二叉树，转换方法： 将第一棵树转换成二叉树， 将第二棵树转换成二叉树，作为第一棵二叉树的右子树； 将第三棵树转换成二叉树，作为第二棵二叉树的右子树； 以此类推,51,树的应用：哈 夫 曼 树,哈夫曼树的定义 节点的路径长度：从树中一个结点到另一个 结点之间的分支构成这两个结点之间的路 径，路径上的分支数目称做路径长度 树的路径长度：从树根到每一结点的路径长度之和 树的带权路径长度：被定义为从各叶结点到树根之间的路径长度与结点上权的乘积和。,52,树的应用：哈 夫 曼 树,(a) WPL = 9262523246 (b) WPL = 6132935354 (c) WPL
28、= 9162533345,53,b,5,3,c,6,d,a,9,a,6,5,b,9,c,d,3,a,5,6,c,9,b,d,3,哈夫曼树的定义,具有n个带权叶节点的二叉树中WPL最小的二叉树称为哈夫曼树 意义：用于编码设计 编码长度路径长度 使用频率权值 报文总长WPL 报文总长最短WPL最小,54,各类编码,55,哈夫曼树的构造,设给定叶结点的个数n及权值集合 w1 , w2 , wn 为使二叉树的带权路径长度达到最小，权值越大的叶结点 应越靠近根结点，而权值越小的叶结点则离根结点越远。 构造方法如下：,56,a,6,5,b,9,c,d,3,a,5,6,c,9,b,d,3,a,6,b,9,c
29、,d,a,9,5,6,c,b,d,3,57,哈夫曼树的建树及编码,58,26,11,5,15,7,3,4,1,2,3,8,6,2,7,3,5,4,6,2,1,编码方式：左分支为0 ，右分支为1，重复下去，直到叶子结点，可以得到：,1(110) 2(1110) 3(00) 4(10) 5(011) 6(010) 7(1111),树的应用：哈夫曼编码生成程序,在程序中要使用到两种结构类型，一种是哈夫曼树的结点类型，另一种是哈夫曼编码的结构类型。 struct HaffNode int weight; int parent; int lchild; int rchild; ; struct Haff
30、Code int bitmaxlen; int start; int weight; ;,59,树的应用：哈夫曼编码生成程序,void Haffman(int w,int n,HaffNode ht,HaffCode hc) int i,j,m1,m2,x1,x2; /m1、m2分别表示最小、次小的权值,x1、x2分别表示当前分支结点的左右儿子 /步骤1 构造哈夫曼树 for(i=0;i2*n-1;i+) /哈夫曼树初始化 if(in)hti.weight=wi;else hti.weight=0; hti.parent=0; hti.lchild=-1; hti.rchild=-1; ; 在
31、构造某一个分支结点时使用了一个循环for(j=0;jn+i;j+)表示从根结点到当前已生成的分支结点中找出两个权值最小的结点。当然应该在还没有确定父结点的结点中进行查找。,60,树的应用：哈夫曼编码生成程序,for(i=0;in-1;i+) /构造哈夫曼树的n-1个分支结点 m1=m2=1000; x1=x2=0; for(j=0;jn+i;j+) if( htj.weightm1 ,61,树的应用：哈夫曼编码生成程序,/步骤2 由哈夫曼树生成哈夫曼编码 HaffCode cd; int child,parent; for(i=0;in;i+) /由哈夫曼树生成哈夫曼编码 cd.start=n
32、-1; cd.weight=hti.weight; child=i; parent=htchild.parent; while (parent!=0) if( htparent.lchild=child) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; child=parent; parent=htchild.parent; ; for(j=cd.start+1;jn;j+) hci.bitj=cd.bitj; hci.start=cd.start; hci.weight=cd.weight; ;,62,哈夫曼编码生成程序：执行实例,设有
33、字符集A、B、C、D、E、F、G，各字符对应的权值分别为4,2,6,8,3,2,1，设计各字符的哈夫曼编码。程序代码如下： void main( ) int w =4,2,6,8,3,2,1; int n=7,i,j; HaffNode *ht = new HaffNode 2*n-1; HaffCode *hc = new HaffCode n; Haffman(w,n,ht,hc); for(i=0;in;i+) cout“weight=“ hci.weight“ code=“; for(j=hci.start+1;jn;j+) couthci.bitj; coutendl; ; ,63,weight=4 code=101 weight=2 code=1001 weight=6 code=01 weight=8 code=11 weight=3 code=001 weight=2 code=100 weight=1 code=1000,