数据结构课件：第六章 二叉树

第六章二叉树树及二叉树的定义二叉树的性质二叉树的存储二叉树的遍历二叉树的应用树的基本概念树定义：树是n（n≥0）个结点的有限集合（用T表示）。当n=0时，称为空树；当n>0时，该集合满足如下条件：(1)其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。(2)其余n-1个结点可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，可有零个或多个直接后继。

例如：一棵树的逻辑结构图为：ABCDGFEHIJKLM从图中可以看出它好象一棵倒栽的树。树的基本概念（续）树的相关术语：结点的度：一个结点的子树个数称为此结点的度。叶结点：度为0的结点，即无后继的结点，也称为终端结点。

分支结点：度不为0的结点，也称为非终端结点。结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。

树的基本概念（续）树的度：树中所有结点的度的最大值。树的深度：树中所有结点的层次的最大值。双亲结点：一个结点的直接前驱称为该结点的双亲结点。下图中A是B、C、D的双亲。兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。下图中的结点B、C、D互为兄弟结点。

孩子结点：一个结点的直接后继称为该结点的孩子结点。如下图的B、C、D是A的孩子。

我们常常借助人类家族的术语，以便于直观理解结点间的层次关系。

ABCDGFEHIJKLM二叉树的基本概念定义：我们把满足以下两个条件的树型结构叫做二叉树（BinaryTree）：（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。下面给出二叉树的五种基本形态：(a)空二叉数(c)只有左子树的二叉树(b)只有根结点的二叉树(d)左右子树均非空的二叉树(e)只有右子树的二叉树性质1：在二叉树的第i层上至多有2i-1个结点(i≥1).性质2：深度为k的二叉树至多有2k-1个结点(k≥1).性质3：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1.二叉树的性质两种特殊的二叉树满二叉树：深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。123456789101112131415满二叉树两种特殊的二叉树（续）完全二叉树：1234567891011121314关系：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。深度为k，结点数为n的二叉树，如果其结点1到n的位置序号分别与同深度的满二叉树的结点1到n的位置序号一一对应，则为完全二叉树

两种特殊的二叉树（续）满二叉树特点：每一层上的结点数都是最大结点数完全二叉树特点：叶子结点只可能在层次最大的两层上出现对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+11231145891213671014151231145891267101234567123456√×√×完全二叉树(性质４)12第二节二叉树具有n个结点的完全二叉树,其深度为log2n+1设k为深度，由二叉树性质２，已知2k-1-1

<n≤2k-1即2k-1≤n<2k即k=log2n+1第６章树与二叉树621754389101112完全二叉树(性质５)13第二节二叉树在完全二叉树中，结点i的双亲为i/2结点i的左孩子LCHILD(i)=2i结点i的右孩子RCHILD(i)=2i+1第６章树与二叉树6217543891011122i+2i2i+32i+12ii+1i/2二叉树的存储结构二叉树的结构是非线性的，每一结点最多可有两个后继。一、二叉树的顺序存储表示二、二叉树的链式存储表示二叉树的存储结构（续）1.顺序存储结构：是用一组连续的存储单元来存放二叉树的数据元素。ABCDEFGHIJKLABCDEFGHIJKL二叉树的顺序存储结构从上到下从左到右二叉树的存储结构（续）

对于一般的二叉树，我们必须按照完全二叉树的形式来存储，就会造成空间的浪费。单支树就是一个极端情况。ABCDA^B^^^C^^^^^^^D单支树二叉树的存储结构（续）2.链式存储结构：我们可以设计每个结点至少包括三个域：数据域、左孩子域和右孩子域：

LChildDataRChild二叉链表DABCEFGABCDEFG二叉树T二叉链表二叉树遍历指按一定规律对二叉树中的每个结点进行访问且仅访问一次。

先序遍历过程：①访问根结点；②按先序遍历左子树；③按先序遍历右子树。RChildDataLChildDataLChildLChildRChild中序遍历过程：①按中序遍历左子树；②访问根结点；③按中序遍历右子树。后序遍历过程：①按后序遍历左子树；②按后序遍历右子树；③访问根结点遍历二叉树如果规定先左子树后右子树，则共有三种组合1.DLR[先序遍历]2.LDR[中序遍历]3.LRD[后序遍历]ＤLR二叉树遍历（续）先序遍历二叉树算法：1.若二叉树为空，则返回；否则：2.访问根节点(D)3.先序遍历左子树(L)4.先序遍历右子树(R)ＤLR二叉树遍历（续）二叉树遍历（续）例：给出下面二叉树的三种遍历序列ABCDEFGIH先序遍历：ABDEHICFG中序遍历：DBHEIAFCG后序遍历：DHIEBFGCA先序遍历二叉树算法(举例)：1.若二叉树为空，则返回；否则：2.访问根节点(D)3.先序遍历左子树(L)4.先序遍历右子树(R)输出结果：ABDEGCFADBFCGE二叉树遍历（续）先序遍历二叉树算法(C语言实现)：voidPreOrderTraverse(BinTreeT){if(T){cout<<T->data;PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);}}二叉树遍历（续）中序遍历二叉树算法：1.若二叉树为空，则返回；否则：2.中序遍历左子树(L)3.访问根节点(D)4.中序遍历右子树(R)ＤLR二叉树遍历（续）中序遍历二叉树算法(举例)：1.若二叉树为空，则返回；否则：2.中序遍历左子树(L)3.访问根节点(D)4.中序遍历右子树(R)输出结果：DBGEAFCADBFCGE二叉树遍历（续）三、中序遍历二叉树算法(C语言实现)：voidInOrderTraverse(BinTreeT){if(T){ InOrderTraverse(T->lChild); cout<<T->data;InOrderTraverse(T->rChild);}}二叉树遍历（续）后序遍历二叉树算法：1.若二叉树为空，则返回；否则：2.后序遍历左子树(L)3.后序遍历右子树(R)4.访问根节点(D)ＤLR二叉树遍历（续）后序遍历二叉树算法(举例)：1.若二叉树为空，则返回；否则：2.访问根节点(D)3.后序遍历左子树(L)4.后序遍历右子树(R)输出结果：DGEBFCAADBFCGE二叉树遍历（续）后序遍历二叉树算法(C语言实现)：voidPostOrderTraverse(BinTreeT){if(T){ PostOrderTraverse(T->lChild); PostOrderTraverse(T->rChild); cout<<T->data;}}二叉树遍历（续）什么是线索二叉树？类似与单向链表发展到双向链表线索二叉树有什么用途？线索二叉树一、增加新指针最简单的方法是在每个结点中，增加前驱(fwd)和后继(bkwd)指针在做二叉树遍历（前、中、后序），将每个结点的前驱和后继信息添入fwd和bkwd域中fwdlChilddatarChildbkwd线索二叉树二、利用空指针在有n个结点的二叉树中，必定存在n+1个空链域因为每个结点有两个链域（左、右孩子指针），因此共有2n个链域除根结点外，每个结点都有且仅有一个分支相连，即n-1个链域被使用线索二叉树（续）二、利用空指针在结点中增加两个标记位（LTag,RTag)LTag=0,lChild域指示结点的左孩子

LTag=1,lChild域指示结点的前驱结点RTag=0,rChild域指示结点的右孩子

RTag=1,rChild域指示结点的后继结点LTaglChilddatarChildRTag线索二叉树（续）一、树的存储结构1.双亲表示法采用一组连续的存储空间ABCDEFG-10001130123456AEBGDFC树和森林一、树的存储结构2.孩子表示法可以采用多重链表，即每个结点有多个指针最大缺点是空链域太多

[(d-1)n+1个]AEBGDFC

datachild1child2child3childd树与森林一、树的存储结构2.孩子表示法将每个结点的孩子排列起来，用单链表表示将每个结点排列成一个线性表AEBGDFCABCDEFG0123456Root123^45^6^树与森林（续）一、树的存储结构3.孩子兄弟表示法采用二叉链表左边指针指向第一个孩子，右边指针指向兄弟AEBGDFC

datafirstChildnextSiblingBCDGFEA树与森林（续）二、树与二叉树的对应关系树与二叉树都可以采用二叉链表作存储结构任意给定一棵树，可以找到一个唯一的二叉树(没有右子树)AEBGDFCBCDGFEAABGDFCE树对应的二叉树树与森林（续）三、森林与二叉树的对应关系如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应三棵树的森林对应的二叉树T1T2T3AFHBCDGIJEKABCEDHIKFGJ树与森林（续）森林转为二叉树(算法)如果F={T1,T2,…,Tn}是森林，B＝（root，LB，RB）是二叉树（1）若F为空，即n＝0，则B是空树；（2）若F非空，则B的根root即为F中第一棵树T1的根root（T1）；B的左子树LB是从T1中根结点的子树森林F1={T11,T12,…,T1m}转换而成的二叉树；B的右子树RB是从F2={T2,…,Tn}转换而成的二叉树；树与森林（续）二叉树转为森林(算法)如果F={T1,T2,…,Tn}是森林，B＝（root，LB，RB）是二叉树（1）若B为空，则F是空；（2）若B非空，则F中第一棵树T1的根root（T1）即为B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1外，其他树组成的森林F2={T2,…,Tn}是从B的右子树RB转换而成的森林；树与森林（续）四、树的遍历对树的遍历主要有两种：1.先根（次序）遍历2.后根（次序）遍历AEBGDFC树与森林（续）四、树的遍历1.先根（次序）遍历当树非空时访问根结点依次先根遍历根的各棵子树输出结果：ABEFCDGAEBGDFC树与森林（续）四、树的遍历2.后根（次序）遍历当树非空时依次后根遍历根的各棵子树访问根结点输出结果：EFBCGDAAEBGDFC树与森林（续）一、最优二叉树路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径路径长度：路径上的分支数目树的路径长度：从树根到每个结点的路径长度之和右树路径长度为：

2*1+3*2+1*3=11ADBFCGE赫夫曼树及其应用（续）一、最优二叉树带权路径长度：从结点到树根之间的路径长度与结点上权的乘积树的带权路径长度(WPL)：树中所有叶子结点的带权路径长度之和WPL=2*5+3*3+2*4=27ADBFCGE5３４赫夫曼树及其应用（续）一、最优二叉树最优二叉树：假设二叉树有n个叶子，其每个叶子结点带权wi，则带权路径长度WPL最小的二叉树称为最优二叉树赫夫曼(Huffman)树就是一棵最优二叉树WPL=1*5+2*3+2*4=19ADBCE5３４赫夫曼树及其应用（续）二、Huffman树(构造)在Huffman树中，权值最大的结点离根最近权值最小的结点离根最远ADBCE5３４赫夫曼树及其应用（续）二、Huffman树(算法)1.根据给定的n个权值(w1,w2,…,wn)构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带树为Ti的根结点2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和3.在F中删除这两棵树，同时将新得到的二叉树加入F中4.重复2,3，直到F只含一棵树为止赫夫曼树及其应用（续）二、Huffman树(举例)F:{7}{5}{2}{4}F:{7}{5}{6}F:{7}{11}7524初始合并{2}{4}75246F:{18}1175246合并{5}{6}5合并{7}{11}27461118赫夫曼树及其应用（续）三、Huffman编码设给出一段报文：GOOD_GOOD_GOODGODG字符集合是{O,G,_,D}，各个字符出现的频度(次数)是W＝{7,5,2,4}。若给每个字符以等长编