《数据结构、代码》第4章 树和二叉树

第4章树和二叉树张成文北京邮电大学计算机学院编辑ppt树的定义与基本术语1.定义:树是n(n≥0)个结点的有限集合T。当n=0时,称为空树;当n>0时,该集合满足如下条件:(1)其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。(2)其余n-1个结点可以划分成m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm,其中Ti又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或多个直接后继。一、树(tree)的基本概念:编辑pptABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2树根例如:编辑ppt(1).树型图示(2).嵌套集合(3).凹入(书目)(4).广义表(用根作为表的名字写在表的左边)ABCDEFGHIJKLMA------------B----------E--------K------L------F--------C----------G--------D----------H--------M

------

I--------J--------2.树的表示法:编辑ppt线性结构树型结构第一个数据元素(无前驱)

根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、

一个后继)其它数据元素(一个前驱、

多个后继)对比树型结构和线性结构的结构特点编辑ppt结点(node):树的度:叶子结点(leaf):分支结点:数据元素+若干指向子树的分支树各结点的度的最大值度为零的结点度大于零的结点DHIJM3.树的相关术语结点的度(degree):结点拥有的子树数结点的层次:(level)假设根结点的层次为1,第l层的结点的子树根结点的层次为l+1树的深度(depth):叶子结点所在的最大层次分支(branch):表示数据元素与它的子树的关系编辑ppt路径(path):常用家族树的术语表示结点关系孩子(child)结点双亲(parent)结点

兄弟结点由根到该结点所经的分支和结点构成ABCDEFGHIJMKL树的结点数n和分支数b的关系是:

b=n-1编辑ppt任何一棵非空树是一个二元组Tree=(root,F)其中:root被称为根结点F被称为子树森林森林(forest):是m(m≥0)棵互不相交的树的集合ArootBCDEFGHIJMKLF编辑ppt二叉树1二叉树的定义与基本操作定义：满足以下两个条件的树称做二叉树(BinaryTree):（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。编辑ppt

二叉树或为空树,或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。注意:二叉树是有序树,它的子树有左右之分。二叉树的度数不超过二,但度数不超过二的树未必是二叉树。ABCDEFGHK根结点左子树右子树编辑ppt二叉树的五种基本形态:N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均非空树编辑ppt用归纳法证明:

归纳基:

归纳假设:

归纳证明:i=1层时,只有一个根结点:

2i-1=20=1命题成立;假设

i-1命题成立,即:第i-1层至多有结点=2i-1-1=2i-2个;二叉树每个结点至多有两棵子树,则第i层至多有结点=2i-22=2i-1个。2二叉树的重要特性性质1:二叉树第i层上至多有2i-1个结点。编辑ppt证明:

基于性质1,深度为k的二叉树上的结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k的二叉树上含结点数至多为：

20+21++2k-1=2k-1

性质2:

深度为k的二叉树上至多含2k-1个结点(k≥1)。编辑ppt证明:设二叉树上结点总数：n=n0+n1+n2再根据树的性质：b=n-1

=n0+n1+n2-1由有二叉树分支总数：b=n1+2n2两式右边相等得:n0=n2+1。性质3:

对任何一棵二叉树,若它含有n0个叶子结点、n2个度为2的结点,则必存在关系式:n0=n2+1。也可以用归纳法证明编辑ppt满二叉树在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。编辑ppt完全二叉树 如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。编辑ppt完全二叉树:树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。abcdefghij编辑ppt可用一维数组存储:bt[n]顺序:完全二叉树中将编号i的结点存在bt[i]中。一、二叉树的顺序存储3二叉树的存储结构二叉树是非线性结构，结点最多有两个后继。存储结构有两种：顺序存储结构和链式存储结构。ABCDEFGHIJKLABCDEFGHIJKL编辑ppt例如:

ABDCEF1

23

456

789

1011

121314ABCDEF2511437一般二叉树，按完全二叉树结点的编号存放,无结点的单元存放空元素。会造成空间浪费编辑ppt二、二叉树的链式存储表示二叉链表每个结点包括两个指针域：指向左孩子和右孩子LChildDataRChildDABCEFGABCDEFG二叉树T二叉链表结点结构:编辑pptlchilddatarchild结点结构:二叉链表结点的结构用C语言描述为：typedefstructNode{DataTypedata;strctNode*LChild;structNode*RChild;}BiTNode,*BiTree;

编辑ppt一、问题的提出二、先左后右的遍历算法三、算法描述二叉树的遍历编辑ppt

“遍历”:

沿某条搜索路径巡访二叉树的结点,

使每个结点均被访问一次,且仅被访问一次。一、问题的提出“访问”:

的含义很广,如:输出结点信息等。

“遍历”是任何类型均有的操作,对线性结构而言,只有一条搜索路径(因为每个结点只有一个后继),故不需要另加讨论.编辑ppt二叉树是非线性结构,每个结点有两个后继,

则存在按什么样的搜索路径遍历的问题。 “二叉树”由三部分组成：根结点、左子树和右子树。若能依次遍历这三部分，就遍历了整个二叉树。

用L、D、R表示遍历左子树、访问根结点、遍历右子树，则有8种遍历二叉树方案：先左后右：DLR、LDR、LRD、按层次先右后左：DRL、RDL、RLD、按层次编辑ppt二、先左后右的遍历算法先序的遍历算法DLR中序的遍历算法LDR后序的遍历算法LRDDLR编辑ppt

若二叉树为空树,则空操作;否则,(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。先序的遍历算法:DLR编辑ppt

若二叉树为空树,则空操作;否则,(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。中序的遍历算法:DLR编辑ppt

若二叉树为空树,则空操作;否则,(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。后序的遍历算法:DLR编辑pptabcdefghij例如:先序序列:

abdhiejcfg中序序列:

hdibjeafcg后序序列:

hidjebfgca编辑ppt三、算法描述1)先序遍历voidPreOrder(BiTreebt)/*先序遍历,根指针为bt的二叉树*/{if(bt!=NULL){Visit(bt->data);//访问根结点

PreOrder(bt->LChild);//遍历左子树

PreOrder(bt->RChild);//遍历右子树}}编辑ppt2)中序遍历voidInOrder(BiTreebt)/*中序遍历根指针为bt的二叉树*/{if(bt!=NULL){

InOrder(bt->LChild);//遍历左子树 Visit(bt->data);//访问根结点

InOrder(bt->RChild);//遍历右子树}}

编辑ppt3)后序遍历voidPostOrder(BiTreebt)/*后序遍历根指针为bt的二叉树*/{if(bt!=NULL){

PostOrder(bt->LChild);//遍历左子树

PostOrder(bt->RChild);//遍历右子树 Visit(bt->data);//访问根结点}}

编辑ppt利用遍历结果确定二叉树问题先序序列+中序序列中序序列+后序序列先序序列+后序序列(x)

先序序列:ABCDEFGH中序序列:BDCEAFHGABFCGDEH利用遍历结果确定二叉