树和二叉树

nullnull线性结构 A , B , C , ······· ，X ,Y , Z学 生 成 绩 表线性表——结点间是以线性关系联结null树形结构全校学生档案管理的组织方式null树形结构 —— 结点间具有分层次的连接关系第六章 树和二叉树第六章 树和二叉树6.1 树的定义 由n(n≥0)个结点组成的有限集合。仅有一个根结点，结点间有明显的层次结构关系。n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,..,Tm，其中每一个集合本身又是一棵树，称为根的子树。现实世界中，能用树的结构表示的例子： 学校的行政关系、书的层次结构、人类的家族血缘关系等。null介绍几个概念： 结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。 结点的度（Degree）：结点拥有的子树数。 叶子（Leaf）：度为零的结点，也称端结点。 孩子（Child）：结点子树的根称为该结点的孩子结点。 双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲。 兄弟（Sibling）：同一双亲的孩子。 结点的层次：从根结点开始算起，根为第一层。 深度（Depth)： 树中结点的最大层次数。 森林（Forest）：m(m≥0)棵互不相交的树的集合。nullnull因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。树的基本操作： 构造树、销毁树、插入、删除、遍历等。6.2 二叉树 （Binary Tree）6.2 二叉树 （Binary Tree）1 、二叉树的定义及其性质 (1) 二叉树的定义二叉树的五种基本形态二叉树是另外一种树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。null 二叉树是n(n0)个结点的有限集合。它或为空树(n=0),或由一个根结点和两棵分别称为根的左子树和右子树的互不相交的二叉树组成。 特别要注意：二叉树不是树的特殊情况。aabb两棵不同的二叉树null 二叉树的基本操作： 构造二叉树、销毁二叉树、插入、删除、遍历等。nullInsertChild(T,p,LR,c); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c 与T不相交且右子树为空。 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结 点的原有左或右子树则成为c的右子树。LR=05nullInsertChild(T,p,LR,c); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c 与T不相交且右子树为空。 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结 点的原有左或右子树则成为c的右子树。LR=16nullDeleteChild(T,p,LR); 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。LR=0LR=1null练习: 给出InsertChild(T,p,LR,c)后的结果, 其中T,c如下图所示， LR=0。LR=0nullA、 二叉树的第i层上至多有2 i-1（i 1）个结点。(2) 二叉树的基本性质第三层上(i=3)，有23-1=4个节点。 第四层上(i=4)，有24-1=8个节点。nullA、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为h的二叉树中至多有2h-1个结点。(2) 二叉树的基本性质此树的深度h=4，共有24-1=15个节点。nullA、 二叉树的第i层上至多有2 i-1（i 1）个结点。 B、 深度为h的二叉树中至多含有2h-1个结点。 C、 若在任意一棵二叉树中，有n0个叶子结点， 有n2个度为2的结点，则：n0=n2+1(2) 二叉树的基本性质n0=8 n2=7null性质1：二叉树的第i层上至多有2 i-1（i 1）个结点。 证明：根据二叉树的特点，结论是显然的。性质2：深度为h的二叉树中至多含有2h-1个结点。 证明：深度为h的二叉树最多有h层，根据性质1，只要将第1层到第h层的最大结点数相加，就可得到整个二叉树中结点的最大值。 21-1 + 2 2-1+……+ 2 h-1 = 2 h-1 性质3：度为0的结点总比度为2的结点多一个,即 n0= n2+1 。 证明：设有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点， 则二叉树中结点总数为：n=n0+n1+ n2 设所有进入分支的总数为m,则总的结点个数为：n=m+1 总的射出分支与总的进入分支数相等：m= n1+2 n2 因此： n0+n1+ n2 = n1+2 n2 +1 所以： n0= n2+1 null（3）满二叉树特点：每一层上都含有最大结点数。null 非完全二叉树（4）完全二叉树特点：除最后一层外，每一层都取最大结点数， 最后一层结点都集中在该层最左边的若干位置。（5）树与二叉树的区别（5）树与二叉树的区别A．树中结点的最大度数没有限制，二叉树结点最大度数为2。 B．树的结点无左、右之分，二叉树的结点子树有明确的左、右之分。null2、二叉树的存储结构 (2) 链式存储结构(1) 顺序存储结构(1) 顺序存储结构用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。T[16]若双亲结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。2h-1=24-1 = 15一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。null(2) 链式存储结构图为一般二叉树的二叉链表结构每个结点由数据域、左指针域和右指针域组成。null 链式存储结构的描述： Typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, * BiTree;null6.3、 二叉树的遍历 查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。 （1）遍历定义及遍历算法 遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。 按先左后右的原则，一般使用三种遍历： 先序遍历(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。 中序遍历(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。 后序遍历(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。null （2）遍历算法先序遍历：D L R 中序遍历：L D R 后序遍历：L R DADBCT1T2T3D L R以先序遍历D L R为例演示遍历过程 ABDCBDAC DBCAnullVoid PreOderTraverse(BiTree T){ if(T! =NULL){ printf (T->data); PreOrderTraverse(T->lchild); PreOrderTraverser(T->rchild); } }/*先序遍历*/返回返回返回返回ACBD返回null中序遍历二叉树的递归算法： void inOrderTraverse(BiTree T) { if(T!=NULL) { inOrderTraverse(T->lchild); printf(T->data); inOrderTraverse(T->rchild); } }后序遍历二叉树的递归算法： void PostOrderTraverse(BiTree T) { if(T!=NULL) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf(T->data); } } null层序遍历二叉树的算法： void LevelOrder(BiTree BT) { if (!BT) exit; InitQueue(Q); p=BT; Visit(p); EnQueue(&Q,p); /*访问根结点，并将根结点入队 */ while (!QueueEmpty(Q)) { /*当队非空时重复执行下列操作*/ DeQueue(&Q,&p); /*出队*/ if (p->lchild) {Visit(p->Lchild);EnQueue(&Q,p->Lchild); if (p->rchild) {Visit(p->Rchild);EnQueue(&Q,p->Rchild); } }null （3）遍历二叉树的应用 1) 建立一棵二叉树 (在遍历过程生成结点，建立二叉树的存储结构，用链式存储结构）void CreatBiTree( BiTree T ) { scanf(&ch); if(ch= = ) T=NULL; else{ T=(BiTNode)malloc(sizeof((BiTNode)); T->data=ch; /*生成根结点*/ CreatBiTree(T->lchild); /*构造左子树*/ CreatBiTree (T->rchild); /*构造右子树*/ } }A B D CA B Φ D Φ Φ C Φ Φ按先序遍历null返回返回返回返回返回A B Φ D Φ Φ C Φ Φnull（2）统计二叉树中叶子结点的个数 方法：对二叉树进行遍历，判断被访问的结点是否叶子结点，若是叶子结点，则将计数器加1。 实现算法： int countleaf(BiTree T) { int n1,n2; if (T= =NULL) return 0; else if (T->lchild= =NULL) && (T->rchild= =NULL) return 1; else { n1=countleaf (T->lchild); n2=countleaf (T->rchild); return (n1+n2); } }null void change(BiTree T) { if (T!=NULL) { T->L<->T->R; change(T->L); change(T->R); } }练习：试以二叉链表作为存储结构，将二叉树中所有结点的左右子树进行交换。null2.5.3哈夫曼树及其应用 1、哈夫曼树 树的路径长度的概念： 从一个结点到另一个结点之间的分支数目称为这对结点之间的路径长度。 树的路径长度是从树的根结点到每一结点的路径长度之和。null1245367PL=0+1+1+2+2+2+2=10树的路径长度用PL表示。null1245367PL=0+1+1+2+2+2+2=101245367PL=0+1+1+2+2+3+3=12树的路径长度用PL表示。null 结点的带权路径长度： 从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度： 树中所有叶子结点的带权路径长度之和。WPL=7*2+5*2+2*2+4*2=36null树的带权路径长度记作： 其中：Wk为树中每个叶子结点的权； L k为每个叶子结点到根的路径长度。WPL最小的二叉树就称作最优二叉树或哈夫曼树 。null 哈夫曼树 （最优树） 加权路径长度最小的二叉树就是哈夫曼树。 公式：null2、哈夫曼树的构造———Huffman算法 例：给定权值{7，5，2，4}，构造哈夫曼树。方法： (1) 由原始数据生成森林； (2) 在森林中选取两棵根结点权值最小的和次小的二叉树作为左右子树构造一棵新的二叉树，其根结点的权值为左右子树根结点权值之和。规定左子树根结点的权值小于右子树根结点的权值。 (3) 将新的二叉树加入到森林F中，删除原来两棵权值最小的树； (4)重复2、3步骤，直至F中只剩一棵树为止。null练习：给定权值{5，15，40，30，10}，构造哈夫曼树。null练习：给定权值{5，15，40，30，10}，构造哈夫曼树。cabde515403010null练习：给定权值{5，15，40，30，10}，构造哈夫曼树。15bcaed154030510null练习：给定权值{5，15，40，30，10}，构造哈夫曼树。15bcaed15403051030null练习：给定权值{5，15，40，30，10}，构造哈夫曼树。15bcaed1540305103060null练习：给定权值{5，15，40，30，10}，构造哈夫曼树。15bcaed1540305103060100WPL=40*1+30*2+15*3+5*4+10*4=205null3、哈夫曼树的应用（1）判定树 在解决某些判定问题时，利用哈夫曼树可以得到最佳判定算法。 例1 将学生百分成绩按分数段分级的程序。 若学生成绩分布是均匀的，可用图（a)二叉树结构来实现。null(b) 学生成绩分布不是均匀的情况：以比例数为权构造一棵哈夫曼树，如（b)判断树所示。再将每一比较框的两次比较改为一次，可得到（c)判定树。输入10000个数据，仅需进行22000次比较。null输入10000个数据，则需进行31500次比较。null各字符编码是 T ； A C S       00 01 10 110 111 上述电文编码： 11010111011101000011111000011000方法： （1）用{ 2，4， 2，3， 3 }作为叶子结点的权值生成一棵哈夫曼树，并将对应权值wi的叶子结点注明对应的字符； （2）约定左分支表示字符“0”，右分支表示字符‘1’ （3）从叶子结点开始，顺着双亲反推上去，直到根结点，路径上的‘0’或‘1’连接的序列就是结点对应的字符的二进制编码的逆序。（2）哈夫曼编码-----利用哈夫曼树构造通讯中电文编码（前缀码） 例2：要传输的电文是{CAS；CAT；SAT；AT} 要传输的字符集是 D={C，A，S，T， ；} 每个字符出现的频率是W={ 2，4， 2，3， 3 }注意：编码的总长度恰好为哈夫曼树的带权路径长。null————Huffman 树和Huffman编码的存储表示———— typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; } HTNode, * HuffmanTree; //动态分配数组存储Huffman树 Typedef char ** HuffmanCode; //动态分配数组存储Huffman编码表Huffman 编码算法null例：已知某系统在通信联络中只可能出现八种字符，其概率 分别为 0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11，试设计 Huffman编码。