数据结构课件C版.pptx
2023/3/17树 -树的定义和术语 树：一棵树 T，简称为树，它是n(n0)个结点的有限集合。当n=0时，T 称为空树；否则，T 是非空树，记作其中，r 是一个特定的称为根(root)的结点，它没有直接前驱；根以外的其他结点划分为 m(m 0)个互不相交的有限集合T1,T2,Tm，每个集合又是一棵树，并且称之为根的子树。第1页/共69页2023/3/17树 -树的定义和术语 相关术语子女：若结点的子树非空，结点子树的根即为该结点的子女。双亲：若结点有子女，该结点是子女双亲。兄弟：同一结点的子女互称为兄弟。度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。分支结点：度不为0的结点即为分支结点，亦称为非终端结点。第2页/共69页2023/3/17树 -树的定义和术语 叶结点：度为0的结点即为叶结点，亦称为终端结点。祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。子孙：某结点的所有下属结点，都是该结点的子孙。结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以此类推。深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。第3页/共69页2023/3/17树 -树的定义和术语 高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。有序树：树中结点的各棵子树 T0,T1,是有次序的，即为有序树。无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。森林：森林是m（m0）棵树的集合。第4页/共69页2023/3/17树 -树的抽象数据类型教材 p118-120第5页/共69页2023/3/17二叉树-二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。第6页/共69页2023/3/17二叉树-二叉树的性质 性质1 若二叉树结点的层次从 1 开始,则在二叉树的第 i(i1)层最多有 2i-1 个结点。证明用数学归纳法性质2 深度为 k(k0)的二叉树最少有 k 个结点，最多有 2k-1个结点。证明：因为每一层最少要有1个结点，因此，最少结点数为 k。最多结点个数借助性质1用求等比级数前k项和的公式20+21+22+2k-1=2k-1第7页/共69页2023/3/17二叉树-二叉树的性质 性质3 对任何一棵二叉树，如果其叶结点有 n0 个,度为 2 的非叶结点有 n2 个,则有 n0n21证明：若设度为 1 的结点有 n1 个，总结点数为n，总边数为e，则根据二叉树的定义，n=n0+n1+n2 ,e=2n2+n1=n-1 因此，有 2n2+n1=n0+n1+n2-1则 n2=n0-1 n0=n2+1 第8页/共69页2023/3/17二叉树-二叉树的性质 定义1 满二叉树(Full Binary Tree)：深度为k的满二叉树是有2k-1个结点的二叉树。定义2 完全二叉树(Complete Binary Tree)：若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层(1k-1)的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。第9页/共69页2023/3/17二叉树-二叉树的性质 性质4 具有 n(n0)个结点的完全二叉树的深度为 log2(n+1)。证明：设完全二叉树的深度为k，则有2k-1-1 n 2k-1 即 2k-1 n+12k，取对数 k-1 1,则 i 的双亲为 i2；3)若2*i=n,则 i 的左子女为 2*i；4)若2*i+1 data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;/PreOrderTraverse第22页/共69页2023/3/17二叉树 -二叉树的遍历中序遍历二叉树T的非递归算法Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)/算法6.2.采用二叉链表存储结构，Visit是对数据元/素操作的应用函数。中序遍历二叉树T的非递归算/法，对每个数据元素调用函数Visit。第23页/共69页2023/3/17二叉树 -二叉树的遍历 InitStack(S);Push(S,T);/根指针进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);/空指针退栈 if(!StackEmpty(S)/访问结点，向右一步 Pop(S,p);if(!Visit(p-data)return ERROR;Push(S,p-rchild);return OK;/InOrderTraverse第24页/共69页2023/3/17二叉树 -二叉树的遍历中序遍历二叉树T的非递归算法Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)/算法6.3.采用二叉链表存储结构，Visit是对数据/元素操作的应用函数。中序遍历二叉树T的非递归/算法，对每个数据元素调用函数Visit。第25页/共69页2023/3/17二叉树 -二叉树的遍历 InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;else Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/InOrderTraverse第26页/共69页2023/3/17二叉树 -以递归方式建立二叉树BiTree CreateBiTree(BiTree&T)/算法6.4 /按先序次序输入二叉树中结点的值（一个字/符），#字符表示空树，构造二叉链表表示的二/叉树T。第27页/共69页2023/3/17二叉树-以递归方式建立二叉树 char ch;scanf(%c,&ch);if(ch=#)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)return ERROR;T-data=ch;/生成根结点 CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树 return T;/CreateBiTree第28页/共69页2023/3/17二叉树 例1：给定一棵二叉树的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，画出这颗二叉树。第29页/共69页2023/3/17二叉树 例2：给定一棵二叉树的中序序列DCBGEAHFIJK和后序序列DCEGBFHKJIA，画出这颗二叉树。第30页/共69页2023/3/17二叉树 例3：给定一棵二叉树的先序和后序序列不能确定一棵二叉树。第31页/共69页2023/3/17线索二叉树-线索二叉树的概念为什么提出线索二叉树？遍历的过程实质上是对一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这个线性序列中有且仅有一个直接前驱和直接后继。二叉树中只存储了左右孩子的信息，因此，前驱和后继的信息无法直接找到。就提出了线索二叉树的概念。又因为n个结点的二叉链表中有n+1个空链域，从而得到线索二叉树的存储结构如下。第32页/共69页2023/3/17线索二叉树-线索二叉树的概念规定：若结点有左子树，则lchild指示其左孩子，否则令lchild指示其前驱；若结点有右子树，则其rchild域指示其右孩子，否则令rchild指示其后继。为避免混淆，增加两个标志域：LTag为0（1）表示lchild指向左孩子（前驱），RTag为0（1）表示rchild指向右孩子（后继）。第33页/共69页2023/3/17线索二叉树-线索二叉树的概念其中，指向结点前驱和后继的指针叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化。第34页/共69页2023/3/17线索二叉树-线索二叉树的概念第35页/共69页2023/3/17线索二叉树-二叉树的二叉线索存储表示typedef enum PointerTag Link,Thread;/Link=0:指针，Thread=1:线索typedef struct BiThrNod TElemType data;struct BiThrNode *lchild,*rchild;/左右指针 PointerTag LTag,RTag;/左右标志 BiThrNode,*BiThrTree;第36页/共69页2023/3/17线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱和后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。线索二叉树-通过中序遍历建立中序线索化二叉树第37页/共69页2023/3/17线索二叉树-通过中序遍历建立中序线索化二叉树Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/算法6.6 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;/右指针回指 if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);/算法6.7 pre-rchild=Thrt;pre-RTag=Thread;Thrt-rchild=pre;return OK;/InOrderThreading第38页/共69页2023/3/17线索二叉树-通过中序遍历建立中序线索化二叉树void InThreading(BiThrTree p)/算法6.7 if(p)InThreading(p-lchild);/左子树线索化 if(!p-lchild)/建前驱线索 p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后继线索 pre-RTag=Thread;pre-rchild=p;pre=p;/保持pre指向p的前驱 InThreading(p-rchild);/右子树线索化 /InThreading第39页/共69页2023/3/17线索二叉树-中序遍历二叉线索链表表示的二叉树Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(ElemType)/算法6.5p=T-lchild;/p指向根结点 while(p!=T)/空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;/p进至其右子树根 return OK;/InOrderTraverse_Thr第40页/共69页2023/3/17线索二叉树-寻找当前结点在中序下的后继 寻找当前结点在中序下的后继 后继为右子女结点后继为当前结点右子树的中序下的第一个结点！=NULL无后继无此情况=NULL=1=0RTagrchild第41页/共69页2023/3/17线索二叉树-寻找当前结点在中序下的后继 寻找当前结点在中序下的前驱前驱为左子女结点前驱为当前结点左子树中序下的最后一个结点！=NULL无前驱无此情况=NULL=1=0LTaglchild第42页/共69页2023/3/17树与森林-树的存储表示 双亲表示法（父指针表示法）以一组连续的存储单元来存放树中的结点，每个结点有两个域，一个是data域，用来存放数据元素，一个是parent域，用来存放指示其父结点位置的指针。这种存储表示适合经常需要寻找父结点的应用。第43页/共69页2023/3/17树与森林-树的存储表示 树的双亲表存储表示#define MAX_TREE_SIZE 100typedef struct PTNode/结点结构 TElemType data;int parent;/双亲位置域 PTNode;typedef struct/树结构 PTNode nodesMAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;第44页/共69页2023/3/17树与森林-树的存储表示 孩子表示法（子女链表表示法）为树中每个结点设置一个子女链表，并将这些结点的数据和对应子女链表的头指针放在一个向量中，就构成了子女链表表示。这种存储表示适合需要频繁寻找子女的应用。无序树情形链表中各结点顺序任意，有序树必须自左向右链接各个子女结点。第45页/共69页2023/3/17树与森林-树的存储表示 树的孩子链表存储表示typedef struct CTNode /孩子结点结构 int child;struct CTNode*next;*ChildPtr;typedef struct /双亲结点结构 TElemType data;ChildPtr firstchild;/孩子链的头指针 CTBox;typedef struct /树结构 CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;第46页/共69页2023/3/17树与森林-树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法）子女-兄弟链表表示法也称为树的二叉树表示。他的每个结点的度为2，是最节省存储空间的树的存储表示。每个结点由三个域组成：firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。nextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。第47页/共69页2023/3/17树与森林-树的存储表示 孩子兄弟表示法（子女-兄弟链表表示法）第48页/共69页2023/3/17树与森林-树的存储表示 树的二叉链表存储表示typedef struct CSNode TElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;第49页/共69页2023/3/17树与森林-森林与二叉树的转换将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。森林与二叉树表示的转换可以借助树的二叉树表示来实现。第50页/共69页2023/3/17树与森林-森林与二叉树的转换森林转化成二叉树的规则若 F 为空，即 n=0，则对应的二叉树 B 为空树。若 F 不空，则i.二叉树 B 的根是 F 第一棵树 T1 的根；ii.其左子树为B(T11,T12,T1m)，其中，T11,T12,T1m 是 T1 的根的子树；iii.其右子树为 B(T2,T3,Tn)，其中，T2,T3,Tn 是除 T1 外其它树构成的森林。第51页/共69页2023/3/17树与森林-森林与二叉树的转换二叉树转换为森林的规则如果 B 为空，则对应的森林 F 也为空。如果 B 非空，则i.F 中第一棵树 T1 的根为 B 的根；ii.T1 的根的子树森林 T11,T12,T1m 是由 B 的根的左子树 LB 转换而来；iii.F 中除了 T1 之外其余的树组成的森林 T2,T3,Tn 是由 B 的根的右子树 RB 转换而成的森林。第52页/共69页2023/3/17树与森林-森林与二叉树的转换第53页/共69页2023/3/17树与森林-树的遍历 深度优先遍历先根次序遍历：先访问树的根结点，然后先根遍历根的每棵子树。树的先根遍历结果与其对应二叉树表示的前序遍历结果相同。树的先根遍历可以借助对应二叉树的前序遍历算法实现。后根次序遍历：先依次后根遍历每棵子树，然后访问根结点。树的后根遍历结果与其对应二叉树表示的中序遍历结果相同。树的后根遍历可以借助对应二叉树的中序遍历算法实现。第54页/共69页2023/3/17树与森林-森林的遍历森林的遍历也分为深度优先遍历和广度优先遍历，深度优先遍历又可分为先根次序遍历和后根次序遍历。深度优先遍历给定森林 F，若 F=，则遍历结束。否则若F=T1=r1,T11,T1k,T2,.,Tm，则可以导出先根遍历、后根遍历两种方法。其中，r1是第一棵树的根结点，T11,T1k是第一棵树的子树森林，T2,.,Tm是除去第一棵树之后剩余的树构成的森林。第55页/共69页2023/3/17树与森林-森林的遍历森林的先根次序遍历若森林F=，返回；否则访问森林的根（也是第一棵树的根）r1；先根遍历森林第一棵树的根的子树森林T11,T1k；先根遍历森林中除第一棵树外其他树组成的森林T2,.,Tm。森林的后根次序遍历若森林 F=，返回；否则后根遍历森林 F 第一棵树的根结点的子树森林T11,T1k；访问森林的根结点 r1；后根遍历森林中除第一棵树外其他树组成的森林T2,.,Tm。第56页/共69页2023/3/17树与森林-森林的遍历森林的先根次序遍历和后根次序遍历分别对应为二叉树的前序遍历和中序遍历。广度优先遍历若森林 F 为空，返回；否则依次遍历各棵树的根结点；依次遍历各棵树根结点的所有子女；依次遍历这些子女结点的子女结点；第57页/共69页2023/3/17Huffman树 -相关概念路径长度(Path Length)两个结点之间的路径长度 PL 是连接两结点的路径上的分支数。树的外部路径长度是各叶结点（外结点）到根结点的路径长度之和 EPL。树的内部路径长度是各非叶结点（内结点）到根结点的路径长度之和 IPL。树的路径长度 PL=EPL+IPL。第58页/共69页2023/3/17Huffman树 -相关概念n 个结点的二叉树的路径长度不小于下述数列前 n 项的和，即第59页/共69页2023/3/17Huffman树 -相关概念其路径长度最小者为完全二叉树满足这个要求。带 权 路 径 长 度 (Weighted Path Length,WPL)树的带权路径长度为树中所有叶子结点的带权路径长度之和。第60页/共69页2023/3/17Huffman树 -相关概念第61页/共69页2023/3/17Huffman树 -相关概念Huffman树假设有n个权值w1,w2,wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树为最优二叉树，即Huffman树。第62页/共69页2023/3/17Huffman树 -Huffman树的构造算法 1.根据给定的n个权值w1,w2,wn构造n棵二叉树的集合F=T1，T2，Tn，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3.在F中删除这两棵树，同时将新得到的二叉树加入F中。4.重复（2）、（3）步，直到F只含一棵树为止，这棵树为Huffman树。第63页/共69页2023/3/17Huffman树 -Huffman树的构造算法 第64页/共69页2023/3/17Huffman树 -Huffman树的构造算法 第65页/共69页2023/3/17Huffman树 -Huffman 编码 主要用途是实现数据压缩。设给出一段报文：CAST CAST SAT AT A TASA字符集合是 C,A,S,T，各个字符出现的频度（次数）是 W 2,7,4,5。若给每个字符以等长编码（2位二进制足够）A:00 T:10 C:01 S:11则总编码长度为(2+7+4+5)*2=36。第66页/共69页2023/3/17Huffman树 -Huffman 编码 能否减少总编码长度，使得发出同样报文，可以用最少的二进制代码？若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为 2/18,7/18,4/18,5/18,化整为 2,7,4,5。以它们为各叶结点上的权值,建立Huffman树。左分支赋 0，右分支赋 1，得Huffman编码(变长编码)。A:0 T:10 C:110 S:111第67页/共69页2023/3/17Huffman树 -Huffman 编码 A:0 T:10 C:110 S:111它的总编码长度：7*1+5*2+(2+4)*3=35。比等长编码的情形要短。总编码长度正好等于Huffman树的带权路径长度WPL。Huffman编码是一种前缀编码，即任一个二进制编码不是其他二进制编码的前缀。解码时不会混淆。因为需要编码的结点都是叶子结点，他不会成为别的结点的祖先结点，所以也不会成为前缀。第68页/共69页2023/3/17mayan 感谢您的观看！第69页/共69页
