1、跳转到第一页 第五章第五章 树树本章内容：本章内容：*树的定义和基本操作；*二叉树的定义及遍历、存储结构；*树的应用；重点：重点：*树的定义 *二叉树的定义及遍历序列跳转到第一页 内内 容容5.1 树的定义和基本术语5.2 二叉树的定义及存储结构5.3 二叉树的遍历5.4 树的存储5.5 树的应用跳转到第一页 5.1 5.1 树的定义和基本术语树的定义和基本术语 树是由n个结点构成的有限集合。当n=0时，称为空树。在一棵非空树中（n0）中，有且仅有一个特定的结点，称根的结点；其余结点可分为m个（m0）互不相交的集合T1，T2Tm，其中，每一个集合本身又是一棵树,且称为根的子树。跳转到第一页 特
2、点：特点：树中至少有一个结点根,它没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点；树中各子树是互不相交的集合，树中所有结点可以有零个或多个后继结点。有限集合T1，T2Tm应该“互不相交”，即任意 两个集合不能有相重的结点。树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整棵树的根画在最上层，如图5.1所示跳转到第一页ABCDEFGHIJKLM有子树的树根子树A只有根结点的树图5.1跳转到第一页v结点(node)表示树中的元素，包括数据项及若干指向其子树的分支v结点的度(degree)结点拥有的子树个数v叶子(leaf)度为0的结点v孩子(child)
3、结点子树的根称为该结点的孩子v双亲(parents)孩子结点的上层结点叫该结点的v兄弟(sibling)同一双亲的孩子v树的度一棵树中最大的结点度数跳转到第一页结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数森林(forest)m(m0)棵互不相交的树的集合有序树 树中结点的各子树从左到右是有次序的，否则为无序树。例：例：如下图5.2所示，回答问题：跳转到第一页ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0树的度：3结点A的孩子：B，C，D结点B的孩子：E，F结点A的层次：1结点M的层次：4叶子：K，L，F，G，M，
4、I，J结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟结点F，G为堂兄弟结点A是结点F，G的祖先树的深度：4图5.2跳转到第一页1、直观表示法：图5.3表示法 2、文氏图法：hbacgdefijijdfghabe跳转到第一页 3、嵌套括号法 4、凹入表示法a(b(d,e(i,j),c(g,h)abdeijfcgh跳转到第一页跳转到第一页5.2 5.2 二叉树二叉树 一个二叉树是n个结点的有限集合（n0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。由上述定义可知，二叉树可以是空集，其根可以有空的左子树或右子树，或者左、
5、右子树皆为空。跳转到第一页 特点：特点：(1)每个结点至多有二棵子树(即不存在度大于2的结点);(2)二叉树的子树有左、右之分，且其次序不能任意颠倒;一般地，二叉树有五种基本形态，如图5.3所示。A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空图5.3跳转到第一页(1)满二叉树：定义1：在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。定义2：如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。特点：每一层上的结点数都是最大结点数。跳转到第一页1231
6、145891213671014151234567123114589126710123456满二叉树完全二叉树跳转到第一页 (2)完全二叉树：定义：一颗深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号（自左而右）从1至n的结点一一对应时，称为。特点：深度为k的完全二叉树，其前k-1层是一颗满二叉树；最后第k层的结点都尽量排在靠左的位置上。跳转到第一页1、性质1：)1(21iii个结点层上至多有在二叉树的第证明：用归纳法证明之 i=1时，只有一个根结点，是对的 假设对所有j(1j1，则其双亲是i/2 (2)如果2in，则其左孩子是2i；如果2in，则结点i无左孩子；(3
7、)如果2i+1n，则其右孩子是2i+1；如果2i+1n，则结点i无右孩子；跳转到第一页作业作业1:书上书上P87 1、4、5跳转到第一页 1 1、顺序存储结构、顺序存储结构l实现：按满二叉树的结点层次编号（从上至下，从左至右），依次存放二叉树中的数据元素，即将编号为i的结点存入一维数组的第i个单元。例如：例如：一般二叉树的存储abcdefga b c d e f g 1 2 3 4 5 6 7 8 9 10 11跳转到第一页l特点：u结点间关系蕴含在其存储位置中,即这种次序应能反映结点间的逻辑关系;u浪费空间，适于存储满二叉树和完全二叉树.应用：由二叉树，画出此二叉树的存储结构 由二叉树的存储
8、结构画出此二叉树跳转到第一页 A B C E F G D A B D C E G F Exercise1:Key:跳转到第一页Exercise2:1 2 3 4 5 6 7 8 9 10 11 12 13a b c d e f gabcedfgKey:跳转到第一页 2 2、链式存储结构、链式存储结构 对于非完全二叉树，可以采用链式，链表的头指针均指向根结点。二叉链表 通常每个结点中设置三个域,即数据（值）域、左指针域和右指针域，其结点结构如下：typedef struct node datatype data;struct node *lchild,*rchild;JD;left data r
9、ight 跳转到第一页ABCDEFG在n个结点的二叉链表中，有n+1个空指针域lchild data rchild A B C D E F G 例如：例如：跳转到第一页三叉链表lchild data parent rchildABCDEFG A B C D E F G 跳转到第一页 5.3 5.3 二叉树的遍历二叉树的遍历 1、遍历(Traversal)是指按一定的规律访问树的每个结点，且每个结点只被访问一次的过程，即找一个完整而有规律的走法，将非线性结构的树中的结点排列成一个线性序列的过程。跳转到第一页2、遍历的常用方法：l先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；l后
10、根（序）遍历：先依次遍历每棵子树，然后访问根结点；中序遍历：先依次访问树的左子树，根结点，然后访问树的右子树；l按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点。跳转到第一页 一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序：左、根、右；根、左、右；左、右、根；右、根、左；根、右、左；右、左、根；跳转到第一页 由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中、三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。对于用顺序法
11、表示的二叉树，各结点在数组中的编号很有规律，其遍历较容易进行，但对于用链式存储结构表示的二叉树，进行遍历就复杂一些。三种遍历次序以递归的形式定义：跳转到第一页1、先序（、先序（Preorder）遍历遍历若遍历的二叉树不为空，则依次执行下列操作：访问根结点；先序遍历左子树；先序遍历右子树。2、中序（、中序（Inorder）遍历遍历若遍历的二叉树不为空，则依次执行下列操作：中序遍历左子树；访问根结点；中序遍历右子树。跳转到第一页 3、后序（后序（Postorder）遍历遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：后序遍历左子树；后序遍历右子树；访问根结点。例：按不同的遍历方法，写出二
12、叉树遍历所例：按不同的遍历方法，写出二叉树遍历所得到的结点序列。得到的结点序列。跳转到第一页ADBCDD L RAD L RD L RBCD L R先序遍历先序遍历:先序遍历序列：A B D C跳转到第一页中序遍历中序遍历:中序遍历序列：B D A CL D RBL D RL D RADCL D RADBC跳转到第一页ADBC后序遍历后序遍历:后序遍历序列：D B C A L R DL R DL R DADCL R D跳转到第一页Exercise1:-+/a*b-efcdKey:先序：-+a *b -c d /e f 中序：a +b *c -d -e /f 后序：a b c d -*+e f
13、/-写出下列二叉树的三种序列。Exercise2:书上，P87跳转到第一页Exercise3:已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG，请画出此二叉树。B C D E F G A H Key3:跳转到第一页typedef struct node datatype data;struct node *left,*right;btree;链式存储结构的结点定义如下：链式存储结构的结点定义如下：先序遍历递归算法：跳转到第一页void preorder(JD*bt)if(bt!=NULL)printf(%dt,bt-data);preorder(bt-lchild);preo
14、rder(bt-rchild);返回pre(T R);返回T右是空返回返回返回返回pre(T R);T左是空返回T左是空返回TDprintf(D);pre(T L);Dpre(T R);TBprintf(B);pre(T L);BTCprintf(C);pre(T L);C主程序主程序Pre(T)TAprintf(A);pre(T L);AT左是空返回T右是空返回pre(T R);先序序列：A B D C跳转到第一页中序遍历递归算法：void inorder(btree*p)if(p！=NULL)inorder(p-left);printf(%d,p-data);inorder(p-right
15、);跳转到第一页作业作业2:1、有一颗二叉树 如下图，分别写出其先序、中序、后序遍历序列。abcdehifg2、书上，P87 3跳转到第一页3、有一颗二叉树 如下图，分别写出其先序、中序、后序遍历序列。B C D E F G A H I 跳转到第一页 4、采用顺序存储方法和链式存储方法分别画出如下图所示二叉树的存储结构。跳转到第一页Key1:先序：先序：a b d e h c f g i 中序：中序：d b h e a f c i g 后序：后序：d h e b f I g c a Key3:v中序遍历序列：H，D，I，B，E，A，F，C，Gv先序遍历序列：A，B，D，H，I，E，C，F，Gv
16、后序遍历序列：H，I，D，E，B，F，G，C，A跳转到第一页 9 1 2 3 4 5 6 8 7 9 0 1 2 3 4 5 5 7 14 13 12 1 1 10 9 8 15 Key4:4 1 5 3 2 6 7 9 8 跳转到第一页5.4 5.4 树的存储树的存储一、树的存储方式一、树的存储方式 1 1、双亲表示法、双亲表示法l实现：定义一组连续的结构数组存放树的结点，每个结点含两个域：u数据域：存放结点本身信息u双亲域：指示本结点的双亲结点在数组中的位置跳转到第一页typedef struct node datatype data;int parent;JD;JD tM;结点定义如下：
17、结点定义如下：l特点：找双亲容易，找孩子难跳转到第一页abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或存结点个数如何找孩子结点例例：跳转到第一页 2 2、孩子表示法、孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根定长结点的多重链表：取树的度D作为每个结点的指针域个数，即结点的指针个数相等；不定长结点的多重链表：树中每个结点都取它自己的度d作为指针域的个数，而终端结点不设指针域。data child1 child2 .childDdata degree child1 child2 .childd跳转到第一页孩子结点：t
18、ypedef struct node int child;/*该结点在表头数组中下标*/struct node *next;/*指向下一孩子结点*/JD;表头结点：typedef struct tnode datatype data;/*数据域*/struct node *fc;/*指向第一个孩子结点*/TD;TD tM;/*t0不用*/孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表.例例1 1:见P76跳转到第一页abcdefhgi6012345789acdefghibdatafc 2 3 4 5 9 7 8 6如何找双亲结点例例2 2：跳转到第一页 3、
19、带双亲的孩子表示法、带双亲的孩子表示法abcdefhgi612345789acdefghibdatafc 2 3 4 5 9 7 8 6012235551parent跳转到第一页 4、孩子兄弟表示法、孩子兄弟表示法实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 特点操作容易破坏了树的层次typedef struct node datatype data;struct node *fch,*nsib;JD;跳转到第一页abcdefhgi例例：a b c d e f g h i 跳转到第一页 普通树可用链式存储结构来表示，每个结点包括数据域以及指
20、向它各个儿子结点的指针域。若同一树的各结点有相同数据结构，则只能按结点度数最大值（该树的度数）给每个结点设置指针。这样较浪费存储空间。按照一定的原则将普通树用二叉树来表示，是较好的表示方法。跳转到第一页 将所有兄弟结点之间加一连线；对每个结点，保留与其左儿子结点的连线，去掉该结点与其它儿子结点的连线；将树向顺时针方向旋转45 把普通树转换成相应的二叉树，具体把普通树转换成相应的二叉树，具体方法如下：方法如下：跳转到第一页例例1：把普通树转换成相应的二叉树 书上P77 图5.18例例2：B C D E F G A H I J 树经过变换，可得下面的形式：跳转到第一页 B C D E F G A
21、H I J 得到的已是一棵二叉树，若按顺时针方向将它旋转就更清楚地变为下面所示的二叉树。跳转到第一页 B C D E F G A H I J v由于树根没有兄弟，所以树转换为二叉树后，二叉树的根结点的右子树必为空。跳转到第一页Exercise:Exercise:把普通树转换成相应的二叉树 1 1、2 2、abcdabcedf跳转到第一页5.5 5.5 树的应用树的应用一、二叉排序树一、二叉排序树 1、二叉排序树的定义、二叉排序树的定义v所谓排序，就是将一组杂乱无序的数据按一定的规律顺序排列起来。跳转到第一页v对一个二叉树若规定：任一结点如果有左子树，其左子树各结点的数据必须小于该结点的数据；任
22、一结点如果有右子树，其右子树各结点的数据必须等于或大于该结点的数据，按这样规定构成的二叉树叫做二叉排序树。v在一个二叉排序树中，其结点是按左子树、根和右子树的次序有序的，故对二叉排序树进行中序遍历得到的结点序列是一个有序序列。跳转到第一页v以整数类型的数据排列为例，设要求将一批正整数按递增的次序排列，若有相同的数据，则按先后次序列出。按二叉排序树要求可将这批正整数构成一个二叉排序树，每个参加排序的数据对应二叉树的一个结点，然后，对这种树进行一次中序遍历，按访问各结点的顺序输出所有结点的数据，这些数据就是按排序所要求的次序排列的。跳转到第一页 11 10 v中序遍历序列：1，2，3，4，5，6，
23、7，8，9，10，11 跳转到第一页2、二叉排序树的生成二叉排序树的生成v设已知一组待排序的数据，若要构造出对应的二叉排序树，一般是采取从空树开始，陆续插入一系列结点的办法，逐步生成对应的二叉排序树。v即首先以第一个数据构成根结点，以后对应每个数据插入一个结点，在插入过程中，原有的结点位置均不再变动，只是将新数据结点作为一个端结点插入到合适的位置处，使树中任何结点与其左、右子树结点数据之间的关系都符合二叉排序树的要求跳转到第一页v例：待排序的数据为一组正整数：10,15,20,5,10,30,9,7下图 二叉排序树生成过程 15 15 20 15 20 跳转到第一页 15 20 1 5 2 0
24、 3 0 15 20 30 15 20 30 跳转到第一页v假设一组待排序的数据均为正整数，并以1为结束输入的标志，生成二叉排序树函数如下：void creat(btree*b)int x;b=NULL;do scanf(%d,&x);/*读入一个整数*/insert(x,b);/*插入该结点*/while(x!=-1);生成二叉排序树算法:跳转到第一页二、哈夫曼树二、哈夫曼树Huffman 1、哈夫曼树基本术语：、哈夫曼树基本术语：1)路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。2)路径长度：路径上的分支数称为这两点之间的路径长度。3)树的路径长度：树的路径长度是从树
25、的根到每一结点的路径长度之和，一般记作pl。v在结点数目相同的二叉树中，完全二叉树或满二叉树的路径长度最短。跳转到第一页 4)结点的权：在许多实际应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。5)带权路径长度：从树的根结点到该结点之间的路径长度与该结点上权的乘积，称为该结点的带权路径长度。v树的带权路径长度：是树中所有叶子结点的带权路径长度之和，通常记为：niiilwwpl1跳转到第一页 其中n表示叶子结点个数，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。v给定一组n个实数，以它们作为各个叶子结点的权，可构成不同的有n个叶子结点的二叉树，这些二叉树的带权路径
26、长度wpl可能不同。P83niiilwwpl1跳转到第一页 2、哈夫曼树、哈夫曼树v哈夫曼树又称为最优二叉树，它是这样定义的：设有n个权值w1，w2，wn，以这些权值为各个叶子结点的权所构成的二叉树中，带权路径长度WPL最小的二叉树叫做哈夫曼树。v哈夫曼(Huffman)于1952年提出了得到这种树的算法，因此相应的算法称为哈夫曼算法。跳转到第一页v将n个权值w1，w2，wn按递增次序排列，设其顺序为w1，w2，wn，取出最小的两个w1和w2，分别作为根结点的左、右儿子结点的权组成一个二叉树，并认为其根结点的权w12=w1+w2；v将w12按其数值大小插入到w3至wn之间，使数值仍保持为递增的
27、次序；3、哈夫曼算法、哈夫曼算法跳转到第一页v再取出最小的两个作为根的左、右儿子的权组成二叉树，也令根的权等于此两数值之和，并同样将此根结点按权值大小插入到剩下的数据中，保持数值的递增次序。如此重复进行下去，直到构成一个二叉树为止，即得到哈夫曼树。v 如下图：如下图：哈夫曼算法过程哈夫曼算法过程例：例：给定4个数：7，5，2，4跳转到第一页 排序 第一步 第 二 步 11 11 第 三 步 跳转到第一页 18 11 第四步 跳转到第一页Exercise:1、给定一组权值5个数：9，1，8，5，3构造一个哈夫曼树。跳转到第一页4、哈夫曼编码、哈夫曼编码v哈夫曼编码（Haffman coding）
28、是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，其压缩效率取决于被压缩数据的特征。v通常我们将压缩过程称为编码，解压缩过程称为解码，利用哈夫曼树构造的用于通信的二进制编码称为哈夫曼编码。跳转到第一页例：设有一段电文“CAST_TAT_A_AS”，统计电文中字母的频度f(C)=1，f(S)=2，f=(T)=3，f=(_)=3，f=(A)=4。用频度1，2，3，3，4为权生成哈夫曼树，并在每个叶结点上注明对应的字符。跳转到第一页 0 13 0 0 0 1 1 1 1 C S T _ A 000 001 01 10 11 C S T _ A000 001 01 10 1
29、1 规定：左分支用“0”表示；右分支用“1”表示跳转到第一页作业作业3：1、设数据集合d=1,12,5,8,3,10,7,13,9,试依次取d中各数据，构造一棵二叉排序树，并给出该二叉排序树中序遍历序列。2、书上P87 6、7跳转到第一页作业作业3:Key1：1、设数据集合d=1,12,5,8,3,10,7,13,9,试依次取d中各数据，构造一棵二叉排序树，并给出该二叉排序树中序遍历序列。12 1 5 13 8 3 10 7 9 v解：本题产生的二叉排序树如图所示，中序遍历序列为：1，3，5，7，8，9，10，12，13。跳转到第一页v树v二叉树满二叉树完全二叉树v树的存储结构顺序存储结构链接
30、存储结构v二叉树的遍历中序遍历先序遍历后序遍历v树的应用二叉排序树哈夫曼树 小小 结结跳转到第一页Exercise:1.若二叉树中各结点值均不相同。1)已知一个二叉树的中序和后序遍历序列分别为GDHBAECIF和GHDBEIFCA，请画出此二叉树。2.一个二叉树如图5.23所示,分别写出其前序、中序、后序的遍历序列。3.输入一个正整数序列55,34,18,88,119,11,76,9,97,99,46，试构造一个二叉排序树。4.有一份电文中共使用5个字符：a、b、c、d、e，它们的出现频率依次为5、2、1、6、4。试画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。跳转到第一页 G B C D
31、E F A 2.如图5.23跳转到第一页Key:2先序遍历序列：A、B、D、E、F、C、G中序遍历序列：D、F、E、B、A、G、C后序遍历序列：F、E、D、B、G、C、A 跳转到第一页 119 55 34 88 46 76 97 99 18 11 9 Key3:跳转到第一页 18 7 11 3 1 2 4 6 5 0 0 0 0 1 1 1 1 b a e c d Key4:各字符对应的哈夫曼编码如下：各字符对应的哈夫曼编码如下：a:10,b:001,c:000,d:11,e:01。跳转到第一页5、已知某系统在通讯时，只出现C，A，S，T，B五种字符，它们出现的频率依次为2，4，2，3，3，试设计Huffman编码。W（权）权）=2，4，2，3，3，叶子结点，叶子结点个数个数n=5 构造的Huffman树148464223300011101 T B A C S
