数据结构第五章树和二叉树

数据结构王向文1325300350@西北师范大学第五章树和二叉树1树的基本概念2二叉树3遍历二叉树4二叉搜索树5树与森林6Huffman树1树的基本概念树的定义树的基本术语1.1树的定义树(Tree)是n(n≧0)个结点的有限集合T，若n=0时称为空树，否则：⑴有且只有一个特殊的称为树的根(Root)结点；⑵若n>1时，其余的结点被分为m(m>0)个互不相交的子集T1,T2,T3…Tm，其中每个子集本身又是一棵树，称其为根的子树(Subtree)。1.1树的定义AABDCEGFHIMJNKL(a)

只有根结点(b)

一般的树1.2树的基本术语⑴结点(node)：一个数据元素及其若干指向其子树的分支。⑵结点的度(degree)、树的度：结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。⑶叶子(left)结点、非叶子结点：树中度为0的结点称为叶子结点(或终端结点)。相对应地，度不为0的结点称为非叶子结点(或非终端结点或分支结点)。除根结点外，分支结点又称为内部结点。1.2树的基本术语⑷孩子结点、双亲结点、兄弟结点：一个结点的子树的根称为该结点的孩子结点(child)或子结点；相应地，该结点是其孩子结点的双亲结点(parent)或父结点。⑸层次、堂兄弟结点：规定树中根结点的层次为1，其余结点的层次等于其双亲结点的层次加1。

若某结点在第l(l≧1)层，则其子结点在第l+1层。双亲结点在同一层上的所有结点互称为堂兄弟结点。1.2树的基本术语⑹结点的层次路径、祖先、子孙：从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径(有且只有一条)。结点p的层次路径上的所有结点（p除外）称为p的祖先(ancester)。以某一结点为根的子树中的任意结点称为该结点的子孙结点(descent)。⑺树的深度(depth)：树中结点的最大层次值，又称为树的高度。1.2树的基本术语⑻有序树和无序树：对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。⑼森林(forest)：是m(m≧0)棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。1.3树的抽象数据类型定义ADTTree{数据对象D：D是具有相同数据类型的数据元素的集合。数据关系R：若D为空集，则称为空树；

……基本操作：……}ADTTree2二叉树二叉树的定义二叉树的基本形态二叉树的性质二叉树的存储结构2.1二叉树的定义二叉树(Binarytree)是n(n≥0)个结点的有限集合。若n=0时称为空树，否则：⑴有且只有一个特殊的称为树的根(Root)结点；⑵若n>1时，其余的结点被分成为二个互不相交的子集T1,T2，分别称之为左、右子树，并且左、右子树又都是二叉树。2.2二叉树的基本形态AAAA(a)(b)(c)(d)(e)(a)空二叉树(b)单结点二叉树(c)右子树为空(d)左子树为空(e)左、右子树都不空二叉树的基本形态2.3二叉树的性质性质1：在非空二叉树中，第i层上至多有2i-1个结点(i≧1)。性质2：深度为k的二叉树至多有2k-1个结点（k≧1)。性质3：对任何一棵二叉树，若其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。2.3二叉树的性质满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树(FullBinaryTree)。满二叉树的特点：基本特点是每一层上的结点数总是最大结点数。满二叉树的所有的支结点都有左、右子树。可对满二叉树的结点进行连续编号，若规定从根结点开始，按“自上而下、自左至右”的原则进行。2.3二叉树的性质完全二叉树(CompleteBinaryTree)：如果深度为k，由n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应，该二叉树称为完全二叉树。或深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。

其中2k-1≦

n≦2k-1。完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。2.3二叉树的性质完全二叉树的特点：

若完全二叉树的深度为k，则所有的叶子结点都出现在第k层或k-1层。对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。894101151213614157213894101152112673(a)满二叉树(b)完全二叉树1362455674213(c)非完全二叉树特殊形态的二叉树2.3二叉树的性质性质4：n个结点的完全二叉树深度为：㏒2n

+1。其中符号：x表示不小于x的最小

整数。x

表示不大于x的最大整数。2.3二叉树的性质性质5：若对一棵有n个结点的完全二叉树(深度为

㏒2n

+1)的结点按层（从第1层到第㏒2n

+1层)序自左至右进行编号,则对于编号为i（1≦i≦n)的结点：⑴若i=1：则结点i是二叉树的根，无双亲结点；否则，若i>1，则其双亲结点编号是

i/2

。⑵如果2i>n：则结点i为叶子结点，无左孩子；否则，其左孩子结点编号是2i。⑶如果2i+1>n：则结点i无右孩子；否则，其右孩子结点编号是2i+1。性质6：给定N个节点，能构成CN种不同的二叉树，其中为卡塔兰数（Catalan）。2.4二叉树的存储结构顺序存储结构：用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中。对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中。最坏的情况下，一个深度为k且只有k个结点的单支树需要长度为2k-1的一维数组。abcdhiejklfg(a)完全二叉树(b)非完全二叉树abcdefghØØØ123456789101112

abcdefghijkl

(c)完全二叉树的顺序存储形式1234567891011abcdeØhØ

Ø

fg(d)非完全二叉树的顺序存储形式2.4二叉树的存储结构链式存储结构：二叉链表结点。有三个域：一个数据域，两个分别指向左右子结点的指针域。三叉链表结点。除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点。LchilddataRchildLchilddataparentRchild(a)二叉链表结点(b)三叉链表结点链表结点结构形式2.4二叉树的存储结构(a)二叉树afedcbg(c)三叉链表

a⋀

⋀

b⋀

c⋀

d⋀

e⋀

f⋀⋀

g⋀T(b)二叉链表

a⋀

b⋀c⋀

d⋀e⋀g⋀⋀f⋀T3遍历二叉树遍历二叉树(TraversingBinaryTree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。先(根)序遍历中(根)序遍历后(根)序遍历3.1先序遍历二叉树若二叉树为空，则遍历结束；否则⑴访问根结点；⑵先序遍历左子树(递归调用本算法)；⑶先序遍历右子树(递归调用本算法)。3.1先序遍历二叉树voidPreorderTraverse(BTNode*T){if(T!=NULL){visit(T->data);/*访问根结点*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}3.2中序遍历二叉树若二叉树为空，则遍历结束；否则⑴中序遍历左子树(递归调用本算法)；⑵访问根结点；⑶中序遍历右子树(递归调用本算法)。3.2中序遍历二叉树voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*访问根结点*/InorderTraverse(T->Rchild);}}3.3后序遍历二叉树若二叉树为空，则遍历结束；否则⑴后序遍历左子树(递归调用本算法)；⑵后序遍历右子树(递归调用本算法)；⑶访问根结点。3.3后序遍历二叉树voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*访问根结点*/}}3.4根据遍历结果构建二叉树二叉树遍历的结果是将一个非线性结构中的数据通过访问排列到一个线性序列中。前序序列：abdce特点是第一个访问的a一定是树根，只要左子树非空，后面紧跟的b一定是根的左子女，…中序序列：bdaec特点是树根a把整个中序分成两部分，a左侧子序列是根的左子树上的结点数据，右侧子序列是根的右子树上的结点数据。abcde3.4根据遍历结果构建二叉树由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},构造二叉树过程如下：HBDFEKCGAEKCGABHDF3.4根据遍历结果构建二叉树KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG3.5层次遍历二叉树层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。这种遍历需要使用一个先进先出的队列，在处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历完后，下一层结点正好处于队列的队头，可以继续访问它们。4二叉搜索树二叉排序树（BinarySortTree）又称二叉查找树（BinarySearchTree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的节点。4.1二叉搜索树的查找若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。4.2二叉搜索树的插入在插入之前，先使用搜索算法在树中检查要插入元素有还是没有。如果搜索成功，说明树中已经有这个元素，不再插入；如果搜索不成功，说明树中原来没有关键码等于给定值的结点，把新元素加到搜索操作停止的地方。输入数据

{53,78,65,17,87,09,81,15}4.3二叉搜索树的删除删除叶结点，只需将其双亲结点指向它的指针清零，再释放它即可。被删结点右子树为空，可以拿它的左子女结点顶替它的位置，再释放它。被删结点左子树为空，可以拿它的右子女结点顶替它的位置，再释放它。被删结点左、右子树都不为空，可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中，再来处理这个结点的删除问题。4.3二叉搜索树的删除被删结点右子树为空：4.3二叉搜索树的删除被删结点左子树为空：4.3二叉搜索树的删除被删结点左、右子树都不为空：5树与森林树的存储结构树与二叉树的转换5.1树的存储结构以二叉链表作为树的存储结构两个指针域：分别指向结点的第一个子结点和下一个兄弟结点。结点类型定义如下：typedefstructCSnode{ElemTypedata;structCSnode*firstchild,*nextsibing;}CSNode;树及孩子兄弟存储结构(b)树

FGRABCDE(c)孩子兄弟存储结构

R⋀

A⋀D

C⋀⋀G⋀B⋀F⋀⋀E⋀孩子结点兄弟结点firstchilddatanextsibing(a)结点结构5.2树与二叉树的转换由于二叉树和树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。树与二叉树的对应关系二叉树

CERADB

R⋀

A⋀D⋀⋀C⋀

B⋀E⋀树

RABCDE对应关系

R⋀

A⋀D⋀⋀C⋀

B⋀E⋀⋀C⋀

B⋀E⋀

R

A⋀D⋀存储解释存储解释5.2树与二叉树的转换树转换成二叉树：⑴加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。⑵去连线。除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。⑶旋转。将树顺时针旋转450，原有的实线左斜。⑷整型。将旋转后树中的所有虚线改为实线，并向右斜。5.2树与二叉树的转换树向二叉树的转换过程(a)一般的树

FGRABCDEFGRABCDE(b)加虚线，去连线后

(C)转换后的二叉树FGRACDBE5.2树与二叉树的转换转换后的二叉树的特点是：

二叉树的根结点没有右子树，只有左子树；

左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子结点均是原来树中该结点的兄弟结点。5.2树与二叉树的转换二叉树转换成树：⑴加虚线。若某结点i是其父结点的左子树的根结点，则将该结点i的右子结点以及沿右子链不断地搜索所有的右子结点，将所有这些右子结点与i结点的父结点之间加虚线相连。⑵去连线。去掉二叉树中所有父结点与其右子结点之间的连线。⑶规整化。将图中各结点按层次排列且将所有的虚线变成实线。5.2树与二叉树的转换二叉树向树的转换过程(C)还原后的树FGRABCDE(b)去连线后(a)加虚线后FGRACDBECFGRADBE5.3二叉树与森林的转换森林转换成二叉树：(1)将F={T1,T2,⋯,Tn}中的每棵树转换成二叉树。(2)按给出的森林中树的次序，从最后一棵二叉树开始，每棵二叉树作为前一棵二叉树的根结点的右子树，依次类推，则第一棵树的根结点就是转换后生成的二叉树的根结点。5.3二叉树与森林的转换ACBDGMLHK(a)森林森林转换成二叉树的过程(b)森林中每棵树对应的二叉树ABCDGLKHM(c)森林对应的二叉树ABCDGLKHM5.3二叉树与森林的转换二叉树转换成森林：(1)去连线。将二叉树B的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连线全部去掉，得到若干棵孤立的二叉树，每一棵就是原来森林F中的树依次对应的二叉树。(2)二叉树的还原。将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树。5.3二叉树与森林的转换二叉树还原成森林的过程ACBDMGLHK(c)还原成森林(a)二叉树ABCDGLKHM(b)去连线后ABCDMGLKH5.4树与森林的遍历树的遍历：先序遍历：先访问根结点，然后依次先序遍历完每棵子树。后序遍历：先依次后序遍历完每棵子树，然后访问根结点。树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同。5.4树与森林的遍历先序遍历的次序是：ABCDEFGIJHK后序遍历的次序是：CDBFGIJHEKAABDCKGJIFHE5.4树与森林的遍历森林的遍历：先序遍历：按先序遍历树的方式依次遍历森林中的每棵树。中序遍历：按后序遍历树的方式依次遍历森林中的每棵树。6Huffman树基本概念Huffman树的构造6.1基本概念结点路径：从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。路径长度：结点路径上的分支数目称为路径长度。树的路径长度：从树根到每一个结点的路径长度之和。结点的带权路径长度：从该结点的到树的根结点之间的路径长度与结点的权(值)的乘积。6.1基本概念