第5章二叉树.ppt

1、1,第5章 二叉树,5.1 二叉树的概念 5.2 二叉树的周游 5.3 二叉树的存储结构 5.4 二叉搜索树 5.5 堆 5.6 Huffman树,2,5.1 二叉树的概念,5.1.1 二叉树的定义及相关概念 5.1.2 满二叉树、完全二叉树、扩充二叉树 5.1.3 二叉树的主要性质,3,树的定义,树是包括n个结点的有限集合T（n1）。 有且仅有一个特定的称为根（root）的结点。 除根以外的其它结点被分成m个(m0)不相交的集合T1，T2，Tm，而且这些集合的每一个又都是树。 树T1，T2，Tm称作这个根的子树。 这个定义是递归的。,4,树是含有n个结点的有穷集合K (n0)，且在K上定义一

2、个满足以下条件的关系N： 有且仅有一个结点k0K，它对于关系N来说没有前驱。结点k0称作树的根。 除结点k0外，K中的每个结点对于关系N来说都有且仅有一个前驱。 除结点k0外的任何结点kK，存在结点序列k0，k1，ks(ks=k)，称为从根到结点k的路径。,5,树结构中的概念,树形结构中，两个结点的有序对，称作连接这两结点的一条边。 若N，则称k是k 的父结点，k是k的 子结点。 若有序对及N，则称k和k互为兄弟。 若有一条由 k到达ks的路径，则称k是ks的祖先，ks是k的子孙。,6,树结构中的概念,没有子树的结点称作树叶或终端结点。 非终端结点称为分支结点。 一个结点的子树的个数称为度数。

3、 根结点的层数为0，其它任何结点的层数等于它的父结点的层数加1。,7,5.1.1 二叉树的定义及相关概念,二叉树由结点的有限集合构成。这个有限集合或者为空集；或者由一个根结点及两棵互不相交的分别称为左子树、右子树的二叉树组成。,A,B,C,D,E,F,G,H,K,根结点,右子树,左子树,8,二叉树的定义是一个递归定义。二叉树可以是空集合，因此根可以有空的左子树或右子树，或者左右子树皆为空。,9,二叉树的五种基本形态,10,5.1.2 满二叉树、完全二叉树、扩充二叉树,如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树。,11,完全二叉树,如果一颗二叉树最多只有最

4、下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树。,12,扩充二叉树,当二叉树里出现空的子树时，就增加新的、特殊的结点空树叶。 对于原来二叉树中度数为1的分支结点，在它下面增加一个空树叶 对于原来二叉树的树叶，在它下面增加两个空树叶 扩充的二叉树是满二叉树，新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1。,13,扩充二叉树,14,扩充二叉树,外部路径长度E 从扩充的二叉树的根到每个外部结点的路径长度之和。 内部路径长度I 扩充的二叉树中从根到每个内部结点的路径长度之和。 E和I两个量之间的关系为 E=I+2n,15,1

5、. 二叉树的第i层（根为第0层，i0）最多有2i个结点。,5.1.3 二叉树的主要性质,用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 0 层时，只有一个根结点， 2i = 20 = 1；,假设对所有的 j，1 j i，命题成立;,二叉树上每个结点至多有两棵子树， 则第 i 层的结点数 = 2i-1 2 = 2i 。,16,二叉树的高度定义为二叉树中层数最大的叶结点的层数加1。 二叉树的深度定义为二叉树中层数最大的叶结点的层数。,17,2. 深度为k的二叉树至多有2k+1-1个结点。 证明: 利用性质1 20+21+22+23+.+2k=2k+1-1,18,3.任何一颗二叉树，度为0

6、的结点比度为2的结点多一个。n0 = n2 + 1 证明：设有n个结点的二叉树度为0、1、2的结点数分别为=n0，n1，n2，则 n = n0 + n1 + n2 (公式5.1) 设边数为e。因为除根以外，每个结点都有一条边进入，故n = e + 1。由于这些边是有度为1和2的的结点射出的，因此e = n1+ 2n2，于是 n = e + 1= n1 + 2n2 + 1 （公式5.2） 因此由公式（5.1）（5.2）得 n0 + n1 + n2 = n1 + 2n2 + 1 即 n0 = n2 + 1,19,4.满二叉树定理： 非空满二叉树树叶数等于其分支结点数加1。 证明：设二叉树结点总数为

7、n，叶结点数为m，分支结点数为b。 n = m + b (公式5.3) 每个分支结点恰有两个子结点，故有2*b条边；一颗二叉树，除根结点外，每个结点都恰有一条边联接父结点，故共有n-1条边。即 n - 1 = 2b (公式5.4) 由(公式5.3)，(公式5.4)得： n-1=m+b-1 = 2b，得出 m = b + 1,20,5.满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1。 证明：设二叉树T，将其所有空子树换为树叶，记新的扩充满二叉树为T。所有原来T的结点现在是T的分支结点。根据满二叉树定理，新添加的树叶数目等于T结点个数加1。而每个新添加的树叶对应T的一个空子树

8、。 因此T中空子树数目等于T中结点数加1。,21,6. 有n个结点（n0）的完全二叉树的高度为log2 (n+1),深度为log2 (n+1) -1 。 证明: 设高度为k,则有: 2 k-1-1n=2k-1 2 k-1n+1=2k k-1log2(n+1)=k 因为k是整数，所以k= log2 (n+1),22,7.对于具有n个结点的完全二叉树，结点按层次由左到右编号，则有：(1) 如果i=0为根结点；如果i0，其父结点编号是(i-1)/2.(2)当2i+1n,i结点的左子结点是2i+1;否则i结点没有左子结点。(3)当2i+2n,i结点的右子结点是2i+2;否则i结点没有右子结点。,23,

9、n个结点的完全二叉树, 根的编号为0； 第 i 个结点的左孩子编号为 2i+1；右孩子的编号 2i+2； 双亲编号为 (i-1)/2 ,24,5.2 二叉树的周游,5.2.1 二叉树的抽象数据类型 5.2.2 深度周游二叉树 5.2.3 广度周游二叉树,25,5.2.1 二叉树的抽象数据类型,二叉树的操作： 整棵二叉树的运算 初始化二叉树 合并两棵二叉树 二叉树的结点运算 访问结点的左/右子结点、父结点 访问结点存储的数据,26,template class BinaryTreeNode friend class BinaryTree; private: T info; BinaryTreeN

10、ode *leftchild,*rightchild; public: BinaryTreeNode(); BinaryTreeNode(const T,T value() const; BinaryTreeNode* leftchild() const; BinaryTreeNode* rightchild() const; void setLeftchild(BianryTreeNode*); void setRightchild(BinaryTreeNode*); void setValue(const T ,二叉树结点,27,template class BinaryTree priv

11、ate: BinaryTreeNode * root; public: BinaryTree() root = NUL; BinaryTree() DeleteBinaryTree(root); bool isEmpty() const; BinaryTreeNode* Root() return root; BinaryTreeNode* Parent(BinaryTreeNode* current); BinaryTreeNode* LeftSibling(BinaryTreeNode* current); BinaryTreeNode* RightSibling(BinaryTreeNo

12、de* current); void CreateTree(const T ,二叉树,28,5.2.2 深度优先周游二叉树,所谓周游是指系统地访问数据结构中的每个结点一次且仅一次。 周游一棵二叉树的过程就是将二叉树的结点放入一个线性序列的过程，即将二叉树线性化。,29,深度优先周游二叉树,可以有下列三种周游顺序： 前序周游(tLR次序)：访问根结点；前序周游左子树；前序周游右子树。 中序周游(LtR次序)：中序周游左子树；访问根结点；中序周游右子树。 后序周游(LRt次序)：后序周游左子树；后序周游右子树；访问根结点。,30,深度优先周游二叉树, 前序周游：ABDCEGFHI 中序周游：DBA

13、EGCHFI 后序周游：DBGEHIFCA,31,前序周游二叉树（递归实现）,template void BinaryTree:PreOrder( BinaryTreeNode* root ) if ( root != NULL) Visit(root-value(); / 访问根结点 PreOrder(root-leftchild(); / 前序周游左子树 PreOrder(root-rightchild(); / 前序周游右子树 ,32,中序周游二叉树（递归实现）,template void BinaryTree:InOrder(BinaryTreeNode* root) if ( roo

14、t != NULL) InOrder(root-leftchild(); / 中序周游左子树 Visit(root-value(); / 访问根结点 InOrder(root-rightchild(); / 中序周游右子树 ,33,后序周游二叉树（递归实现）,template void BinaryTree:PostOrder(BinaryTreeNode* root) if( root != NULL) PostOrder(root-leftchild(); / 后序周游左子树PostOrder(root-rightchild(); / 后序周游右子树 Visit(root-value();

15、 / 访问根结点 ,34,非递归深度优先周游二叉树,将递归转换为非递归需要借用栈模拟执行递归的过程。即利用一个栈记录尚未周游的结点或子树，以备以后访问。,35,前序周游二叉树算法（非递归）,pointer = root; 空指针入栈； while ( pointer 非空） Visit(pointer); if (pointer有右结点) 右结点入栈； if (pointer有左结点) 左结点入栈； pointer=退栈； ,36,前序周游二叉树（非递归）,template void BinaryTree:PreOrderWithoutRecursion(BinaryTreeNode* roo

16、t) using std:stack; stack* aStack; BinaryTreeNode * pointer = root; aStack.push(NULL); /栈底监视哨 while (pointer) Visit(pointer-value(); if (pointer-rightchild() != NULL) aStack.push(pointer-rightchild(); if (pointer-leftchild() != NULL) aStack.push(pointer-leftchild(); pointer=aStack.top(); aStack.pop(

17、); ,37,中序周游二叉树算法（非递归）,pointer = root; while ( 栈非空 | pointer 非空） if (pointer非空) 入栈；pointer指向左结点; else pointer = 退栈； Visit(pointer); pointer指向右结点； ,38,中序周游二叉树（非递归）,template void BinaryTree:InOrderWithoutRecursion(BinaryTreeNode* root) using std:stack; stack* aStack; BinaryTreeNode * pointer = root; wh

18、ile (！aStack.empty() | pointer) if (pointer) aStack.push(pointer); pointer = pointer-leftchild(); else /左子树访问完毕，转向访问右子树 pointer = aStack.top(); aStack.pop(); Visit(pointer-value(); pointer = pointer-rightchild(); ,39,后序周游二叉树算法（非递归）,pointer = root; while ( 栈非空 | pointer 非空） while (pointer非空) 入栈；point

19、er指向左结点; pointer = 退栈； if (标志为左) 换右标志入栈； pointer指向右结点； else Visit(pointer); pointer = NULL; ,40,后序周游二叉树（非递归）,/ 栈元素的定义 enum TagsLeft, Right; template class StackElement public: BinaryTreeNode * pointer; Tags tag; ;,41,后序周游二叉树（非递归）,template void BinaryTree:PostOrderWithoutRecursion(BinaryTreeNode* roo

20、t) using std:stack; StackElement element; stack aStack; BinaryTreeNode * pointer = root; while (!aStack.empty() | pointer) while ( pointer) 入栈；pointer指向左结点; element = aStack.top(); aStack.pop(); pointer=element.pointer; if (element.tag = Left) 换右标志入栈； pointer指向右结点； else Visit(pointer-value(); pointe

21、r = NULL; ,element.pointer = pointer; element.tag=Left; aStack.push(element); pointer=pointer-leftchild();,element.tag=Right; aStack.push(element); pointer=pointer-rgihtchild();,42,5.2.3 广度优先周游二叉树,从二叉树的顶层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。,ABCDEFGHI,43,广度优先周游二叉树算法,pointer = root; if (pointer) 入

22、队； while (队非空) pointer = 出队； Visit(pointer); if (pointer左结点非空) 左结点入队； if (pointer右结点非空) 右结点入队； ,44,广度优先周游二叉树,template void BinaryTree:LevelOrder(BinaryTreeNode* root) using std:queue; queue * aQueue; BinaryTreeNode *pointer=root; if (pointer) aQueue.push(pointer); while (!aQuene.empty() pointer=aQue

23、ue.front(); aQueue.pop(); Visit(pointer-value(); if(pointer-leftchild() aQueue.push(pointer-leftchild(); if(pointer-rightchild() aQueue.push(pointer-rightchild(); ,45,5.3 二叉树的存储结构,5.3.1 二叉树的链式存储结构 5.3.2 完全二叉树的顺序存储结构,46,5.3.1 二叉树的链式存储结构,二叉树是非线性的树形结构，在存储器里表示树形结构的最自然方法是链接方法。 在每个结点中除存储结点本身的数据外再设置两个指针字段l

24、eft和right，分别指向结点的左孩子和右孩子。 当结点的某个孩子为空时，则相应的指针为空指针。 结点的形式为,47,A,D,E,B,C,F,root,left info right,结点结构:,用链式存储结构表示二叉树,48,用二叉链表实现二叉树的定义,private: / 二叉树结点的数据域 T info; /二叉树结点指向左子树的指针 BinaryTreeNode* left; /二叉树结点指向右子树的指针 BinaryTreeNode* right;,49,template BinaryTreeNode* BinaryTree:Parent(BinaryTreeNode *curre

25、nt) pointer = root; if (树非空 /向右走 ,返回current的父结点,50,template BinaryTreeNode* BinaryTree:Parent(BinaryTreeNode *current) using std:stack; stack * aStack; BinaryTreeNode *pointer=root; if (root ,返回current的父结点,51,template void BinaryTree:DeleteBinaryTree( BinaryTreeNode* root) if (root != NULL) DeleteBi

26、naryTree(root-left); DeleteBinaryTree(root-right); delete root; ,删除二叉树,52,5.3.2 完全二叉树的顺序存储结构,当需要二叉树紧凑存储，并且在处理过程中，二叉树结构的大小和形状不发生动态变化时，可以采用顺序的方法存储 用顺序法存储二叉树，就是要把所有结点按照一定的次序顺序存储到一片连续的存储单元中 适当安排结点的线性序列，可以用结点在序列中的相互位置反映二叉树结构的部分信息,53,用顺序存储结构表示完全二叉树,按层次顺序将一棵有n个结点的完全二叉树的所有结点从0到n-1编号，就得到结点的一个线性序列。,54,完全二叉树的下

27、标公式,完全二叉树中除最下面一层外，各层都被结点充满，每一层结点个数恰是上一层结点个数的两倍。因此，从一个结点的编号就可以推知它的父结点，左、右子结点的编号 当2i+1n时，结点i的左孩子是结点2i+1，否则结点i没有左孩子 当2i+2n时，结点i的右孩子是结点2i+2，否则结点i没有右孩子,55,5.4 二叉搜索树,56,二叉搜索树（BST） 或者是一颗空树；或者是具有下列性质的二叉树： 对于任何一个结点，设其值为K，则该结点的左子树(若不空)的所有结点的值都小于K； 右子树(若不空)的所有结点的值都大于K； 它的左右子树也分别为二叉搜索树 二叉搜索树的性质: 按照中序周游将各结点打印出来，

28、得到的排列按照由小到大有序。,57,二叉搜索树,中序序列：20,30,32,35,40,50,80,85,88,90,58,二叉搜索树,二叉搜索树的搜索过程: 从根结点开始，在二叉搜索树中检索值K。如果根结点储存的值为K，则检索结束。 如果K小于根结点的值，则只需检索左子树。 如果K大于根结点的值,就只检索右子树。 这个过程一直持续到找到K或者遇上叶子结点。 如果遇上叶子结点仍没有发现K，则查找失败。,59,50,30,80,20,90,85,40,35,88,32,例如:,二叉搜索树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95,6

29、0,从上述查找过程可见，,在查找过程中，生成了一条查找路径：,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,61,二叉搜索树的插入,向二叉搜索树里插入新结点，要保证插入后仍符合二叉搜索树的定义。 插入过程为：用待插入结点与树根比较，若待插入的关键值小于树根的关键值，就进入左子树，否则进入右子树。 在子树中，按照同样的方式沿检索路径直到叶结点，将新结点插入到二叉搜索树的叶子结点位置。,62,二叉搜索树的插入,template void BinarySearchTree:Insert

30、Node(root , newpointer) pointer=root; while ( pointer 非空) if ( newpointer-value() = pointer-value() ) return ;else if ( newpointer-value() value() ) if ( pointer 左为空) 插在左子树; return; else 往左走； else if ( pointer右为空) 插在右子树; return; else 往右走； ,63,二叉搜索树的插入,template void BinarySearchTree:InsertNode( Binar

31、yTreeNode* root , BinaryTreeNode* newpointer) BinaryTreeNode* pointer=NULL; if (root=NULL) Initialize(newpointer);return; else pointer=root; while (pointer != NULL) if ( newpointer-value() = pointer-value() )return ;else if (newpointer-value() value() ) if ( pointer-leftchild() = NULL) pointer-left=

32、newpointer; return; else pointer = pointer-leftchild(); else if ( pointer-rightchild() = NULL) pointer-right=newpointer; return; else pointer = pointer-rightchild(); ,64,创建二叉搜索树,对于给定的关键码集合，为建立二叉搜索树，可以从一个空的二叉搜索树开始，将关键码一个个插进去。 将关键码集合组织成二叉搜索树，起到了对集合里的关键码进行排序的作用，按中序周游二叉搜索树，就能得到排好的关键码序列。,65,二叉搜索树的删除,与插入相

33、反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 删除过程分为如下情况： 被删除的结点是叶子 被删除的结点只有左子树或只有右子树 被删除的结点有左、右子树,66,50,30,80,20,90,85,40,35,88,32,（1）被删除的结点是叶子结点,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,67,50,30,80,20,90,85,40,35,88,32,（2）被删除的结点只有左子树或者只有右子树,其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。,被删关键字 = 40,80,68,若p有左右子树，则在左子

34、树里找中序周游的最后一个结点r，将r的右指针置成指向p的右子树的根，用结点p的左子树的根去代替被删除的结点p。,被删关键字 = 50,（3）被删除的结点既有左子树，也有右子树,69,50,30,80,20,90,85,40,35,88,32,（3）被删除的结点既有左子树，也有右子树,40,40,以其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字 = 50,70,5.5 堆与优先队列,71,最小值堆：最小值堆是一个关键码序列 K0，K1，Kn-1，它具有如下特性： KiK2i+1 (i=0，1， n/2-1) KiK2i+2 例如: (05,23,16,65,73,72,71,

35、94) 类似可以定义最大值堆,72,ki,k2i+1,k2i+2,通常将该记录序列看作一棵完全二叉树， 则 k2i+1 是 ki 的左孩子； k2i+2 是 ki 的右孩子。,05,23,16,65,94,73,72,71,是堆,14,不,(05,23,16,65,73,72,71,94),73,堆的性质,堆是一棵完全二叉树，可以用数组表示 堆中存储的数据局部有序 父与子之间的值存在某种联系 兄弟之间没有必然联系,74,建“初堆”的基本方法： 从堆中最后一个有孩子的结点开始利用调整。,40,55,49,73,81,64,36,12,27,98,（40,55,49,73,12,27,98,81,

36、64,36),12,36,81,73,49,98,81,73,55,98,49,40,64,36,12,27,75,76,77,78,堆的类定义,template class MinHeap private: T* heapArray; /存放堆数据的数组 int CurrentSize; /当前堆中元素数目 int MaxSize; /堆所能容纳的最大元素数目 void BuildHeap(); /建堆 public: MinHeap(const int n)； virtual MinHeap()delete heapArray; bool isLeaf(int pos) const; in

37、t leftchild(int pos) const; int rightchild(int pos) const; int parent(int pos) const; bool Remove(int pos, T void SiftDown(int left)； ,79,template MinHeap:MinHeap(const int n) if(n=0) return; CurrentSize=0; MaxSize=n;/初始化堆容量为n heapArray=new TMaxSize;/创建堆空间 /此处进行堆元素的赋值工作 BuildHeap(); ,80,template boo

38、l MinHeap:isLeaf(int pos) const return (pos=CurrentSize/2) = template int MinHeap:leftchild(int pos) const return 2*pos+1 ,81,template int MinHeap:rightchild(int pos) const return 2*pos+2; = template int MinHeap:parent(int pos) const return (pos-1)/2; ,82,筛选法,template void MinHeap:SiftDown(int posit

39、ion) int i=position; /标识父结点 int j=2*i+1; /标识关键值较小的子结点 T temp=heapArrayi; /保存父结点 while(jheapArrayj+1) j+; /j指向数值较小的子结点 if(tempheapArrayj) heapArrayi=heapArrayj; i=j; j=2*j+1; /向下继续 /end if else break; /end while heapArrayi=temp; ,i,j,83,建初堆,从第一个有子女的结点heapArrayCurrentSize/2-1 开始，自底向上逐步将以各结点为根的子树调整成堆 t

40、emplate void MinHeap:BuildHeap() /反复调用筛选函数 for (int i=CurrentSize/2-1; i=0; i-) SiftDown(i); ,84,插入新元素,template bool MinHeap:Insert(const T ,85,向上筛选调整堆,template void MinHeap:SiftUp(int position) /从position开始调整，使序列成为堆 int temppos = position; T temp = heapArraytemppos; while(temppos0) ,86,移出最小值,T ,87,

41、删除元素,template bool MinHeap:Remove(int pos, T ,88,建堆效率,由于堆有n层深，插入元素、删除元素的平均时间代价和最差时间代价都是(n) 建堆的时间复杂度为(nn),89,优先队列,优先队列是一种有用的数据结构。它是0个或多个元素的集合。每个元素有一个关键码值，主要操作有查找、插入和删除。 优先队列的特点：支持从一个集合中快速查找并移出具有最大值或最小值的元素。 最小优先队列适于查找与删除最小元素；最大优先队列适于查找与删除最大元素。,90,优先队列的实现,采用无序线性表或有序线性表 缺点：效率低 采用堆是一种较好的方案,91,5.6 Huffman

42、树及其应用,92,基本概念,路径 从树中一个结点到另一个结点之间的分支构成这两个结点间的路径 结点路径长度 从根结点到该结点的路径上分支的数目 树的路径长度 树中每个结点的路径长度之和,93,树的带权的路径长度 树中所有叶子结点的带权路径长度之和 Huffman树 设有n个权值w1,w2,wn，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫Huffman树,94,有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,95,根据给定的 n 个权值 w0, w2, , wn-1， 构造 n 棵二叉树的集合 F = T0, T2, , Tn-1， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;,如何构造Huffman树,(1),96,在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,(2),从F中删去这两棵树，同时加入刚生成的新树;,重