树和二叉树.ppt

树和二叉树树和二叉树A只有根结点的树ABCDEFGHIJKLM有子树的树根6.1 树的定义和基本术语树的定义和基本术语在在自然科学自然科学，如地理学领域，水系、地貌（等高，如地理学领域，水系、地貌（等高线）、行政区划等都具有树结构关系；线）、行政区划等都具有树结构关系；在在社会人文社会人文领域，人类社会构成、组织机构等也领域，人类社会构成、组织机构等也具有树结构关系。具有树结构关系。n树的定义树的定义n定义：树定义：树(tree)是是n(n0)个结点的个结点的有限集有限集。在任一颗。在任一颗非空树中非空树中：n有且仅有一个特定的结点，称为树的有且仅有一个特定的结点，称为树的根根(root)n当当n1时，其余结点可分为时，其余结点可分为m(m0)个个互不相交互不相交的有限集的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的其中每一个集合本身又是一棵树，称为根的子子树树(subtree)n特点：特点：n树中至少有一个结点树中至少有一个结点根根n树中各子树是互不相交的集合树中各子树是互不相交的集合ABCDEFGHIJKLM有子树的树根子树n基本术语基本术语n结点结点(node)(node)表示树中的元素，包括一个数据元素表示树中的元素，包括一个数据元素及若干指向其子树的分支及若干指向其子树的分支n结点的度结点的度(degree)(degree)结点拥有的子树数结点拥有的子树数n叶子叶子(leaf)(leaf)度为度为0 0的结点的结点n孩子孩子(child)(child)结点的子树的根称为该结点的孩子结点的子树的根称为该结点的孩子n双亲双亲(parent)(parent)孩子结点的上层结点孩子结点的上层结点n兄弟兄弟(sibling)(sibling)同一双亲的孩子同一双亲的孩子n祖先祖先从根到该结点所经分支上的所有结点从根到该结点所经分支上的所有结点n子孙子孙以某结点为根的子树中的任一结点都称为该以某结点为根的子树中的任一结点都称为该结点的子孙结点的子孙n基本术语基本术语n树的度树的度一棵树中最大的结点度数一棵树中最大的结点度数n结点的层次结点的层次(level)(level)从根结点算起，根为第一层，从根结点算起，根为第一层，它的孩子为第二层它的孩子为第二层n深度深度(depth)(depth)树中结点的最大层次数树中结点的最大层次数n有序树与无序树：如果将树中结点的各子树看成从左有序树与无序树：如果将树中结点的各子树看成从左至右是有顺序的，即称为有序树；否则为无序树。至右是有顺序的，即称为有序树；否则为无序树。n森林森林(forest)m(m(forest)m(m 0)0)棵互不相交的树的集合棵互不相交的树的集合ABCDEFGHIJKLM结点A的度：结点B的度：结点M的度：叶子：结点A的孩子：结点B的孩子：结点I的双亲：结点L的双亲：结点B，C，D为兄弟结点K，L为兄弟树的度：结点A的层次：结点M的层次：树的深度：结点F，G为堂兄弟结点A是结点F，G的祖先320B，C，DE，FK，L，F，G，M，I，J3DE414 设树设树T的度为的度为4，其中度为，其中度为1，2，3和和4的结点的结点个数分别为个数分别为4，2，1，1 则则T中的叶子数为中的叶子数为 A 5 B 6 C 7 D 8 答案：答案：D 抽象数据类型树的定义抽象数据类型树的定义n数据对象数据对象n数据关系数据关系n基本操作基本操作数据对象数据对象数据对象数据对象D：D是具有相同特性的数据元素是具有相同特性的数据元素的集合。的集合。数据关系数据关系数据关系数据关系R：若：若D为空集，则称为为空集，则称为空树空树；若；若D仅含一个数据元素，则仅含一个数据元素，则R为空集，否则为空集，否则R=H，H是如下二元关系：是如下二元关系：（1）存在惟一的根的数据元素）存在惟一的根的数据元素（2）若）若D-root，则，则（3）对应于）对应于D-root 的划分的划分ABCDEFGHIJKLM有子树的树根D1D2D3基本操作基本操作InitTree(&T):构造空树构造空树T;DestroyTree(&T);CreateTree(&T,definition);/按按definition构造树构造树T。ClearTree(&T):将树将树T清为空树。清为空树。TreeEmpty(T):判断树的元素是否为空。判断树的元素是否为空。TreeDepth(T):返回树返回树T的深度。的深度。Root(T):返回返回T的根。的根。Value(T,Cur_e):返回返回Cur_e的值。的值。Assign(T,Cur_e,Value):结点结点Cur_e赋值为赋值为Value。Parent(T,Cur_e)LeftChild(T,Cur_e)RightSibling(T,Cur_e)InsertChild(&T,&P,i,c):插入插入c为为T中中P指结点的第指结点的第I棵子树。棵子树。DeleteChild(&T,&P,i):删除删除T中中p所指结点的第所指结点的第i棵子树。棵子树。TraverseTree(T,Visit():遍历树的每一个结点，并调用遍历树的每一个结点，并调用Visit()函函数。数。6.2 二叉树二叉树1 定义定义n定义：定义：二叉树是另一种树结构，其每个结点二叉树是另一种树结构，其每个结点最多最多只有只有两颗子树，并且子树有两颗子树，并且子树有左右左右之分。之分。n特点特点n每个结点至多有二棵子树每个结点至多有二棵子树(即不存在度大于即不存在度大于2的结点的结点)n二叉树的子树有左、右之分，且其次序不能任意颠倒二叉树的子树有左、右之分，且其次序不能任意颠倒n基本形态基本形态A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空抽象数据类型二叉树的定义抽象数据类型二叉树的定义n数据对象数据对象n数据关系数据关系n基本操作基本操作2 二叉树性质二叉树性质n性质性质1：证明：用归纳法证明之 i=1时，只有一个根结点，是对的 假设对所有j(1j=1的完全二叉树至少的完全二叉树至少有（有（）个结点。）个结点。A 2k 1 B 2k-1 1 C 2k-1 D 2k 答案：答案：C 一棵完全二叉树上有一棵完全二叉树上有1001个结点，其个结点，其中叶子结点的个数是（中叶子结点的个数是（）A 250 B 500 C 501 D 505 答案：答案：C 分析：分析：由二叉树结点的公式：由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为因为n=1001,所以所以1002=2n0+n1,在完全二叉树树中，在完全二叉树树中，n1只只能取能取0或或1,在本题中只能取在本题中只能取0，故，故n=501n性质性质5：如果对一棵有：如果对一棵有n个结点的个结点的完全二叉树完全二叉树的结点按层序编的结点按层序编号，则对任一结点号，则对任一结点i(1 i n)，有：有：(1)如果如果i=1，则结点则结点i是二叉树的根，无双亲；如果是二叉树的根，无双亲；如果i1，则，则其双亲是其双亲是 i/2 (2)如果如果2in，则结点，则结点i无左孩子；如果无左孩子；如果2i n，则其左孩子是，则其左孩子是2i (3)如果如果2i+1n，则结点，则结点i无右孩子；如果无右孩子；如果2i+1 n，则其右，则其右孩子是孩子是2i+1123114589126710 一棵完全二叉树共有一棵完全二叉树共有892个结点，试求个结点，试求（1）树的深度，（）树的深度，（2）叶子结点数，）叶子结点数，（3）最后一个非终端结点的序号）最后一个非终端结点的序号 答案答案（1）10（2）446（3）446 3 二叉树的存储结构二叉树的存储结构n顺序存储结构顺序存储结构n实现：按满二叉树的结点层次编号，依次存放二叉树中的数实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素据元素n特点：特点：n结点间关系蕴含在其存储位置中结点间关系蕴含在其存储位置中n浪费空间，适于存满二叉树和完全二叉树浪费空间，适于存满二叉树和完全二叉树abcdefga b c d e 0 0 0 0 f g 1 2 3 4 5 6 7 8 9 10 11n链式存储结构链式存储结构n二叉链表二叉链表typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;lchild data rchild lchild data rchild ABCDEFG在n个结点的二叉链表中，有n+1个空指针域 AB C D E F Gn三叉链表三叉链表typedef struct node datatype data;struct node *lchild,*rchild,*parent;JD;lchild data parent rchildABCDEFG A B C D E F Gn方法方法n先序遍历：先访问先序遍历：先访问根结点根结点，然后分别先序遍历，然后分别先序遍历左子树左子树、右子右子树树n中序遍历：先中序遍历中序遍历：先中序遍历左子树左子树，然后访问，然后访问根结点根结点，最后遍历，最后遍历右子树右子树n后序遍历：先后序遍历后序遍历：先后序遍历左左、右右子树，然后访问子树，然后访问根结点根结点DLRLDR、LRD、DLRRDL、RLD、DRL6.3 二叉树的遍历二叉树的遍历ADBCD L RAD L RD L RBDCD L R先序遍历序列：A B D C先序遍历:ADBCL D RBL D RL D RADCL D R中序遍历序列：B D A C中序遍历:ADBC L R DL R DL R DADCL R D后序遍历序列：D B C A后序遍历:B-*cab-*abc-*abc先序遍历示意图先序遍历示意图-*cab-*abc中序遍历示意图中序遍历示意图a*b-c-*cab-*abc后序遍历示意图后序遍历示意图ab*c-+/a*b-efcd先序遍历先序遍历：中序遍历：中序遍历：后序遍历：后序遍历：-+a*b-c d/e f-+a*b-cd/ef-+a*b-c d/e fa+b*(c-d)-e/f层次遍历：层次遍历：-+a*b-c d/e f遍历的算法遍历的算法先序遍历先序遍历Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(Visit(T-data)if(PreOrderTraverse(T-lchild,Visit)if(PreOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;主程序主程序Pre(T)返回返回pre(T R);返回返回pre(T R);ACBDTBprintf(B);pre(T L);BTAprintf(A);pre(T L);ATDprintf(D);pre(T L);DTCprintf(C);pre(T L);C返回T左是空返回pre(T R);T左是空返回T右是空返回T左是空返回T右是空返回pre(T R);先序序列：A B D C中序遍历中序遍历Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(InOrderTraverse(T-lchild,Visit)if(Visit(T-data)if(InOrderTraverse(T-rchild,Visit)return OK;return ERROR;else return OK;后序遍历后序遍历Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e)if(T)if(PostOrderTraverse(T-lchild,Visit)if(PostOrderTraverse(T-rchild,Visit)if(Visit(T-data)return OK;return ERROR;else return OK;创建树创建树Status CreateBiTree(BiTree&T)scanf(&ch);if(ch=)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);return OK;非递归算法非递归算法6.2void InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)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);/if /while return OK;/InorderTraverse思考题思考题 已知结点的前序序列和中序序列分别已知结点的前序序列和中序序列分别为：为：ABCDEFG，CBEDAFG，请思考如，请思考如何构造该二叉树，给出构造的方法、原何构造该二叉树，给出构造的方法、原因。因。P1546.6 赫（哈）夫曼树及其应用赫（哈）夫曼树及其应用1 赫（哈）夫曼树（赫（哈）夫曼树（Huffman定义）定义）n路径：从树中一个结点到另一个结点之间的分支构成这两个路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的结点间的n路径长度：路径上的分支数路径长度：路径上的分支数n树的路径长度：从树根到每一个结点的路径长度之和树的路径长度：从树根到每一个结点的路径长度之和n树的带权路径长度：树中所有叶子结点的带权路径长度之和树的带权路径长度：树中所有叶子结点的带权路径长度之和nHuffman树树设有设有n个权值个权值w1,w2,wn，构造一棵有，构造一棵有n个叶子结点的二叉树，每个叶子的权值为个叶子结点的二叉树，每个叶子的权值为wi,则则wpl最小的最小的二叉树叫二叉树叫abcd7524例例 有有4 4个结点，权值分别为个结点，权值分别为7 7，5 5，2 2，4 4，构造有，构造有4 4个叶子结点的二叉树个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=352 构造构造Huffman树的方法树的方法Huffman算法算法n构造构造Huffman树步骤树步骤n根据给定的根据给定的n个权值个权值w1,w2,wn，构造，构造n棵只有根结棵只有根结点的二叉树，令起权值为点的二叉树，令起权值为win在森林中选取两棵根结点权值最小的树作左右子树，构在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和树根结点权值之和n在森林中删除这两棵树，同时将新得到的二叉树加入森在森林中删除这两棵树，同时将新得到的二叉树加入森林中林中n重复上述两步，直到只含一棵树为止，这棵树即哈夫曼重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树树例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例 w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487152958113581923422914871529581003 Huffman树应用树应用n最佳判定树最佳判定树等级分数段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNA70a80a60CYNBYNDYNEYNA80a9060a70EADBC70a80a60CYNBYNDYNEYNA80a9060a70a80a70a60a90EYNDYNCYNBYNA等级分数段比例ABCDE05960697079 8089 901000.050.150.400.300.10a60a90a80a70EYNDYNCYNBYNAa80a70a60a90EYNDYNCYNBYNAN=500*1+1500*2+4000*3+3000*4+1000*4=31500N=500*3+1500*3+4000*2+3000*2+1000*2=220006.6.2 6.6.2 赫夫曼编码赫夫曼编码A(00)A(00)、B(01)B(01)、C(10)C(10)、D(11)D(11)ABCD010101前缀编码前缀编码：若要设计长短不等的编码，则必须：若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符编码的是任一个字符的编码都不是另一个字符编码的前缀，这种编码方式称为前缀编码。前缀，这种编码方式称为前缀编码。A(0)A(0)、B(10)B(10)、C(110)C(110)、D(111)D(111)：前缀编码：前缀编码A(0)A(0)、B(1)B(1)、C(10)C(10)、D(11)D(11)：无法解码：无法解码nHuffman编码：数据通信用的二进制编码编码：数据通信用的二进制编码n思想：根据字符出现频率编码，使电文总长最短思想：根据字符出现频率编码，使电文总长最短n编码：根据字符出现频率构造编码：根据字符出现频率构造Huffman树，然后将树中树，然后将树中结点引向其左孩子的分支标结点引向其左孩子的分支标“0”，引向其右孩子的分支，引向其右孩子的分支标标“1”；每个字符的编码即为从根到每个叶子的路径上；每个字符的编码即为从根到每个叶子的路径上得到的得到的0、1序列序列例例 要传输的字符集要传输的字符集 D=C,A,S,T,;D=C,A,S,T,;字符出现频率字符出现频率 w=2,4,2,3,3 w=2,4,2,3,3CS3364224814T;A00110110T:00;:01A:10C:110S:111n译码：从译码：从Huffman树根开始，从待译码电文中逐位取码。树根开始，从待译码电文中逐位取码。若编码是若编码是“0”，则向左走；若编码是，则向左走；若编码是“1”，则向右走，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束直到电文结束例例 电文是电文是CAS;CAT;SAT;ATCAS;CAT;SAT;AT 其编码其编码 “11010111011101000011111000011000”“11010111011101000011111000011000”电文为电文为“1101000”“1101000”译文只能是译文只能是“CAT”“CAT”CS3364224814T;A00110110T:00;:01A:10C:110S:111例，已知某系统在通讯联系中只出现例，已知某系统在通讯联系中只出现8 8种字符，种字符，其概率分别为其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.110.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，试设计赫夫曼编码。试设计赫夫曼编码。0.05:01100.29:100.07:11100.08:11110.14:1100.23:000.03:01110.11:0100.05 0.29 0.07 0.08 0.14 0.23 0.03 0.110.08 0.29 0.07 0.08 0.14 0.23 0.110.15 0.29 0.08 0.14 0.23 0.110.15 0.29 0.19 0.14 0.23 0.29 0.29 0.19 0.230.29 0.29 0.420.58 0.4229140101078123110101530101