第6章树和二叉树old.ppt

《第6章树和二叉树old.ppt》由会员分享，可在线阅读，更多相关《第6章树和二叉树old.ppt（66页珍藏版）》请在三一办公上搜索。

1、第6章 树和二叉树,主要内容,6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树6.4 线索二叉树6.5 树和森林6.6 赫夫曼树及其应用,6.1 树的定义和基本术语(1),树（Tree）是n(n 0)个结点的有限集。在任意一棵非空树中:A、有且仅有一个称为根的结点；B、当n 2时，其余结点分为m(m 0)个互不相交的子集，每个子集本身又是一棵树，称为根的子树。,以上是一个递归的定义在树的定义中又用到了树的概念，由此可见递归是树的固有特性。,6.1 树的定义和基本术语(2),每个子集都是满足树的定义的树，称为A的子树B子树、C子树、D子树。,树根A没有直接前驱；其余结点有且仅有一个直接

2、前驱，有0个或多个直接后继。,三个互不相交的子集：B,E,F,K,L C,G D,H,I,J,M,树的特征：层次性和分支性,6.1 树的定义和基本术语(3),结点的度：结点的非空子树个数树的度：树内各结点度的最大值分支结点(非终端结点)：度非0的结点叶子结点(终端结点)：度为0的结点孩子：结点的子树的根双亲：孩子的直接前驱结点兄弟：同一个双亲的孩子结点互称为兄弟子孙：以某结点为根的子树中的任一结点祖先：从根到该结点所经历的分支上的所有结点堂兄:双亲在同一层的结点,结点的层次：从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第L层，则其子树的根在第L+1层。树的深度（高度）：结点层次的最

3、大值有序树和无序树：若树中所有结点的的各子树看成是从从至右是有次序的（即不能置换），称为有序树，否则称为无序树。森林：m（m0）个树的集合,Tree=(A(B(E(K,L),F),C(G),D(G,H(M),I,J),6.1 树的定义和基本术语(4),树的基本操作：构造空树InitTree(,6.1 树的定义和基本术语(5),6.2 二叉树,二叉树的定义二叉树的性质二叉树的存储结构,6.2.1 二叉树的定义(1),二叉树是另一种树型结构，它的特点是每个结点至多只有两 棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树可以为空，称为空二叉树;非空二

4、叉树一定有两个子树；左、右子树有次序关系，不能互换；二叉树可以有5种基本形态：二叉树不是结点的度都不超过2的有序树.,6.2 二叉树,左子树,右子树,6.2.1 二叉树的定义(2),具有三个结点的树与二叉树,6.2 二叉树,A、三个结点的树有两种不同的形态,B、三个结点的二叉树有五种不同的形态,树型结构的共同特征：层次性、分支性,6.2.1 二叉树的定义(3),二叉树的基本操作初始化空二叉树InitBiTree(&T)销毁二叉树DestroyBiTree(&T)创建二叉树CreateBiTree(&T,definition)清空二叉树ClearBiTree(&T)判断空二叉树BiTreeEmp

5、ty(T)求二叉树深度BiTreeDepth(T)求双亲parent(T,e)求左孩子LeftChild(T,e)求右孩子RightChild(T,e)求左兄弟LeftSibling(T,e)求右兄弟RightSibling(T,e)插入子树InsertChild(T,p,LR,c)删除子树DeleteChild(T,p,LR)先序遍历二叉树PreOrderTraverse(T,visite()中序遍历二叉树InOrderTraverse(T,visite()后序遍历二叉树PostOrderTraverse(T,visite()按层次遍历levelTraverse(T,visite(),6.2

6、 二叉树,6.2 二叉树,二叉树的定义二叉树的性质二叉树的存储结构,6.2.2 二叉树的性质(1),性质1 在二叉树的第i层上至多有2i-1个结点(i 1)；性质2 深度为k的二叉树上至多有2k-1个结点(k 1)；性质3 设任意一棵二叉树中有n0个度为0的结点，n2个度为2个结点，则有：n0=n2+1；,6.2 二叉树,满二叉树：一棵深度为k且有 2k1个结点的二叉树。即：所有非终端结点的度都等于2，且所有树叶都分布在同一个层次上。,完全二叉树：将深度为k，有n个结点的二叉树自上而下，自左向右进行编号，当且仅当编号与深度为k的满二叉树中前n个结点一一对应。,6.2.2 二叉树的性质(2),性

7、质4 完全二叉树的深度为k log2n+1 或 k=log2(n+1)；性质5 将完全二叉树自上而下，自左向右地编号，对任意一结点i（1 i n）的结点X有：A、若i1，则X是根；若i1,则X的PARENT(i)=i/2;B、若X有左孩子，则X左孩子LCHILD(i)=2i；C、若X有右孩子，则X右孩子RCHILD(i)=2i1；D、若i为奇数且i1，则X的左兄弟为i1；E、若i为偶数且in，则X的右兄弟为i1；,6.2 二叉树,i 为偶数,i 为奇数,6.2 二叉树,二叉树的定义二叉树的性质二叉树的存储结构,6.2.3 二叉树的存储结构(1),设计存储结构的一般原则:保存所有的数据元素 正确

8、地表达出数据元素之间的逻辑关系 便于对数据进行操作和运算 节省空间 二叉树的存储结构：顺序存储结构 链式存储结构,6.2 二叉树,6.2.3 二叉树的存储结构(2),顺序存储结构 根据二叉树性质5，则可以利用一数组存放一棵完全二叉树.,6.2 二叉树,A,C,B,E,D,F,.,结点在完全二叉树中的编号与数组下标一致，可利用性质5来计算结点的双亲、孩子、兄弟的下标。,6.2.3 二叉树的存储结构(3),对于普通二叉树，可以将其补足成完全二叉树后再进行编号，存储。,6.2 二叉树,?,基本数据结构：#define MAX_TREE_SIZE 100typedef TElemType SqBiTr

9、eeMAX_TREE_SIZE;SqBiTree bt;,6.2.3 二叉树的存储结构(4),链式存储结构,6.2 二叉树,左孩子指针,二叉链表,右孩子指针,结点值,三叉链表,亲代指针,6.2.2 二叉树的存储结构(5),6.2 二叉树,二叉树,三叉链表表示,二叉链表表示,基本数据结构：typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,6.3 遍历二叉树,遍历二叉树遍历二叉树的递归与非递归算法表达式求值二叉树的运算举例层序遍历二叉树,6.3.1 遍历二叉树(1),遍历：按某种

10、次序访问二叉树的所有结点，且每个结点仅访问一次。“访问”的含义非常的广泛，可以是对结点作各种处理，如输出结点的信息等。根据二叉树的结构：左子树_根_右子树，可以把对二叉树的遍历分解为三项子任务：访问根 D遍历左子树 L遍历右子树 R根据这三项任务的执行次序的不同，有六种可能的遍历方案：DLR、LDR、LRD先左后右DRL、RDL、RLD先右后左如果约定先左后右，则取前三种方案,6.3 遍历二叉树,6.3.1 遍历二叉树(2),根据访问根的时机不同，将这三种遍历方案分别称为:先根遍历（先序遍历）DLR中根遍历（中序遍历）LDR后根遍历（后序遍历）LRD,6.3 遍历二叉树,6.3 遍历二叉树,遍

11、历二叉树遍历二叉树的递归与非递归算法表达式求值二叉树的运算举例层序遍历二叉树,6.3.2 遍历二叉树的递归与非递归算法(1),先序遍历二叉树 若二叉树为空，则空操作；否则访问根；先序遍历左子树；先序遍历右子树；,6.3 遍历二叉树,void PreOrderTraverse(BiTree T)if(!T)return;visit(T-data);/访根 PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);,6.3.2 遍历二叉树的递归与非递归算法(2),先序遍历二叉树,6.3 遍历二叉树,A,C,B,E,D,L,F,K,G,J,I,H,6

12、.3.2 遍历二叉树的递归与非递归算法(3),中序遍历二叉树 若二叉树为空，则空操作；否则中序遍历左子树；访问根；中序遍历右子树；,6.3 遍历二叉树,void InOrderTraverse(BiTree T)if(!T)return;InOrderTraverse(T-lchild);visit(T-data);/访根 InOrderTraverse(T-rchild);,6.3.2 遍历二叉树的递归与非递归算法(4),中序遍历二叉树,6.3 遍历二叉树,A,C,B,E,D,L,F,K,G,J,I,H,6.3.2 遍历二叉树的递归与非递归算法(5),后序遍历二叉树 若二叉树为空，则空操作；

13、否则后序遍历左子树；后序遍历右子树；访问根；,6.3 遍历二叉树,void PostOrderTraverse(BiTree T)if(!T)return;PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);visit(T-data);/访根,6.3.2 遍历二叉树的递归与非递归算法(6),先序遍历二叉树,6.3 遍历二叉树,A,C,B,E,D,L,F,K,G,J,I,H,6.3.2 遍历二叉树递归与非递归算法(7),中序遍历的非递归算法(借助堆栈实现)void InOrderTraverse(BiTree bt,void(*visi

14、t)(BiTree)/中序遍历的非递归算法 InitStack(S);Push(S,T);While(!StackEmpty(S)While(GetTop(S,p),6.3 遍历二叉树,6.3.2 遍历二叉树递归与非递归算法(8),先序遍历的非递归算法(借助堆栈实现)void PreOrderTraverse(BiTree bt)if(!bt)return;InitStack(S);push(S,bt);/树根的指针进栈while(!EmptyStack(S)pop(S,p);while(p)/沿着左链一路向下 visit(p-data);/访问 if(p-rchild)push(S,p-rc

15、hild);/右孩子进栈 p=p-lchild;,6.3 遍历二叉树,6.3 遍历二叉树,遍历二叉树遍历二叉树的递归与非递归算法表达式求值二叉树的运算举例层序遍历二叉树,6.3.3 表达式求值,表达式求值,6.3 遍历二叉树,算术表达式中的二叉树表示,Model：a+b*(c-d)-e/f,a,b,c,d,e,f,+,*,-,-,/,先序遍历得到前缀表达式：-+a*b c d/e f中序遍历得到中缀表达式：a+b*(c d)e/f后序遍历得到后缀表达式：a b c d-*+e f/-,6.3 遍历二叉树,遍历二叉树遍历二叉树的递归与非递归算法表达式求值二叉树的运算举例层序遍历二叉树,6.3.4

16、 二叉树的运算举例(1),计算二叉树中的结点数 Number()思路：二叉树结点数1+左子树结点数+右子树结点数,6.3 遍历二叉树,int Number(BiTree bt)if(!bt)return 0;/空二叉树 else nl=Number(bt-lchild);nr=Number(bt-rchild);return 1+nl+nr;,void Number(BiTree bt,int,计算二叉树中叶子结点的数目 Leafs()思路：叶子数左子树叶子数+右子树叶子数,6.3.4 二叉树的运算举例(2),6.3 遍历二叉树,int Leafs(BiTree bt)if(!bt)retur

17、n 0;/空二叉树 if(！bt-lchild,void Leafs(BiTree bt，int,6.3.4 二叉树的运算举例(3),计算二叉树的深度 Depth()思路：深度=max(左子树深度，右子树深度)+1,6.3 遍历二叉树,int Depth(BiTree bt)if(!bt)return 0;hl=Depth(bt-lchild);/计算bt的左子树深度 hr=Depth(bt-rchild);/计算bt的右子树深度 return(hlhr?(Hl+1):(hr+1),6.3 遍历二叉树,遍历二叉树遍历二叉树的递归与非递归算法表达式求值二叉树的运算举例层序遍历二叉树,6.3.5

18、层序遍历二叉树(1),自上而下、自左向右地遍历二叉树，先被访问结点的孩子先被访问。遍历思想为：空树,结束。初始化一个空队列Q,树根入队;队头e元素出队,访问e;如果e有左孩子,则左孩子入队;如果e有右孩子,则右孩子入队;如果队列不空转3;否则结束,6.3 遍历二叉树,6.3.5 层序遍历二叉树(2),算法 LevelTraverse()void LevelTraverse(BiTree bt)/按层次遍历二叉树算法 if(!bt)return;/空树 InitQueue(Q);/初始化空队列Q EnQueue(Q,bt);/根入队 while(!EmptyQueue(Q)DeQueue(Q,p

19、);/队头p出队 visit(p-data);/访问p if(p-lchild)EnQueue(Q，p-lchild);/p的左孩子入队 if(p-rchild)EnQueue(Q,p-rchild);/p的右孩子入队,6.3 遍历二叉树,6.4 线索二叉树(1),二叉树的遍历序列是线性序列。在二叉树上找某个结点在某种遍历序列中的直接前驱或直接后继，只能在对二叉树遍历时动态求得。如何在遍历过程中保留下结点的前驱和后继的信息呢？最直接的办法也许就是给每个结点增加两个指针。这样做会使得结构的存储密度大大降低。做如下规定：若结点有左子树，则其lchild域指向其左孩子，否则指向其前驱；若结点有右子树

20、，则其rchild域指向其右孩子，否则指向其后继。其中：,6.4 线索二叉树,6.4 线索二叉树(2),二叉树的二叉线索存储表示：,6.4 线索二叉树,typedef enum PointerTagLink,Thread;typedef struct BiThrNode TElemType data;struct BiThrNode*lchild,*rchild;PointerTag Ltag,Rtag;/左右标志BiThrNode,*BiThrTree;,中序线索二叉树：,6.4 线索二叉树(3),二叉树的二叉线索存储：,6.4 线索二叉树,6.4 线索二叉树(4),线索化，就是在已知二叉链

21、的前提下，填写每个结点左线索LTag域和右线索RTag域。若要建立中(先、后）序线索，则在中(先、后）序遍历过程中完成线索化操作。通过中序遍历建立中序线索化链表的算法在教材P.134,135中。遍历线索二叉树 在线索二叉树中，由于可以直接找到每个结点的后继或前驱，所以遍历可以用非递归的方法实现，而且不必借助栈.(算法 P.134),6.4 线索二叉树,6.5 树和森林,树的存储结构森林与二叉树的转换树和森林的遍历,6.5.1 树的存储结构(1),双亲表示法,6.5 树和森林,#define MAX_TREE_SIZE 100typedef struct PTNode TElemType dat

22、a;int parent;PTNode;typedef struct PTNode nodesMAX_TREE_SIZE;int r,n;/根位置和结点数目 Ptree;,6.5.1 树的存储结构(2),孩子表示法,6.5 树和森林,typedef struct CTNode int child;struct CTNode*next;*ChildPtr;typedef struct TElemType data;ChildPtr firstchild;CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int r,n;/根位置和结点数目 CTree;,6

23、.5.1 树的存储结构(1),孩子-兄弟表示法,6.5 树和森林,typedef struct CSNode TElemType data;struct CSNode*firstchild,*nextsibling;CSNode,CSTree;,树的孩子兄弟表示可以将树转化为二叉树,6.5 树和森林,树的存储结构森林与二叉树之间的转换树和森林的遍历,6.5.2 森林和二叉树之间的转换(1),树用孩子兄弟链表表示时，就已转化成二叉树了。一棵树可以唯一地转换成一棵右子树为空的二叉树。,6.5 树和森林,森林转化为二叉树：把森林中的每一棵树转换成二叉树；将所有二叉树的树根用线相连；以第一棵二叉树的树

24、根为圆心，顺时针转45度。,6.5.2 森林和二叉树之间的转换(2),6.5 树和森林,6.5 树和森林,树的存储结构森林与二叉树之间的转换树和森林的遍历,6.5.3 树和森林的遍历(1),先序遍历树：若树不空，则 访问根；从左至右先序遍历根的各个子树。,6.5 树和森林,后序遍历树：若树不空，则 从左至右后序遍历根的各个子树。访问根。,先根序列：RADEBCFGHK后根序列：DEABGHKFCR,先序序列：RADEBCFGHK中序序列：DEABGHKFCR后序序列：EDKHGFCBAR,等价,6.5.3 树和森林的遍历(2),先序遍历树，等价于先序遍历由这棵树转换而成的二叉树；后序遍历树，等

25、价于中序遍历由这棵树转换而成的二叉树；,6.5 树和森林,先序遍历森林：若森林不空，则 访问第一棵树的根结点；先序遍历第一棵树根结点的子树森林；先序遍历森林中去掉第一棵树后剩下的树构成的森林中序遍历森林：若森林不空，则 中序遍历第一棵树根结点的子树森林；访问第一棵树的根结点；中序遍历森林中去掉第一棵树后剩下的树构成的森林,6.5.3 树和森林的遍历(3),6.5 树和森林,等价,先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG,先序序列：ABCDEFGHIJ中序序列：BCDAFEHJIG后序序列：DCBFJIHGEA,6.6 赫夫曼树及其应用,最优二叉树（赫夫曼树）赫夫曼树的构造赫

26、夫曼编码,6.6.1 最优二叉树（赫夫曼树）(1),路径：从一个结点到另一个结点所经过的分支。路径长度L：路径上分支的数目。树的路径长度：从树根到每一个结点的路径产度之和。树的带权路径长度：树中所有的叶子结点的带权路径长度之和，通常记作：,6.6 赫夫曼树及其应用,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,6.6.1 最优二叉树（赫夫曼树）(2),哈夫曼树：由权值为w1,w2,.,wn)的n片叶子构成的所有二叉树中，WPL值最小的二叉树。,6.6 赫夫曼树及其应用,WPL=7*1+5*2+2*3+4

27、*3=35,WPL=7*1+5*2+2*3+4*3=35,哈夫曼树不一定是最矮的树哈夫曼树形态可能不唯一,6.6 赫夫曼树及其应用,最优二叉树（赫夫曼树）赫夫曼树的构造赫夫曼编码,6.6.2 赫夫曼树的构造(1),1952年，Huffman提出了一个构造最优二叉树的一个精巧算法，被人们称为Huffman算法。算法的思想：将权值为w1,w2,.,wn的n个叶子构成一个具有n棵树的森林F；从森林F中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和；重复2，直到F中只剩下一棵树为止，这棵树就是所求的Huffman树。

28、,6.6 赫夫曼树及其应用,6.6.2 赫夫曼树的构造(2),构造n个叶子的哈夫曼树需要经过n-1次合并，每次合并都要增加一个新结点。所以n个叶子的哈夫曼树上有且仅有2n-1个结点。哈夫曼树上不存在度为1的结点。我们把这种不存在度为1的结点的二叉树称为严格二叉树或正则二叉树。,6.6 赫夫曼树及其应用,存储表示：typedef struct unsigned int child;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;构造算法参见教材（P.147）,6.6 赫夫曼树及其应用,最优二叉树（赫夫曼树）赫夫曼树的构造赫夫曼编码,6.

29、6.3 赫夫曼编码(1),6.6 赫夫曼树及其应用,编码发送：电文 0,1 序列(比特流)接收：0,1序列 电文 解码例如：电文“abcdedacafcfadcacfdaef”字符集 a,b,c,d,e,f 字符出现次数 6,1,5,4,2,4,6.6.3 赫夫曼编码(2),6.6 赫夫曼树及其应用,电文“abcdedacafcfadcacfdaef”字符集 a,b,c,d,e,f 编码方案：,前缀码：任何字符的编码都不是其他字符编码的前缀,6.6.3 赫夫曼编码(3),6.6 赫夫曼树及其应用,如何得到使电文长度最短的二进制前缀编码呢？假设每种字符在电文中出现的次数为wi，其编码长度为l，电文中只有n种字符，则电文的总长度为：对应到二叉树上，若位置wi为叶子结点的权，l为从树根到叶子结点的路径长度，则电文的总长度恰好为二叉树上带权路径长度。,设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵赫夫曼树的问题。,算法的具体实现见教材 P.147,148,