《西北大学树和二叉树》由会员分享，可在线阅读，更多相关《西北大学树和二叉树（133页珍藏版）》请在金锄头文库上搜索。
1、第6章 树和二叉树6.1 树的定义与基本术语6.2 二叉树6.3 二叉树的遍历与线索化6.4 树、森林和二叉树的关系6.5 哈夫曼树及其应用6.6 总结与提高 6.1 树的定义与基本术语1树的基本概念2树的图解表示法 3树的相关术语 4树的抽象数据类型 6.1 树的定义与基本术语树定义：是n（n0）个结点的有限集合T。当n=0时 ，称为空树；当n0时，该集合满足如下条件： (1) 其中必有一个称为根（root）的特定结点，它没有 直接前驱，但有零个或多个直接后继。(2) 其余n-1个结点可以划分成m（m0）个互不相交 的有限集T1，T2，T3，Tm，其中Ti又是一棵树 ，称为根root的子树。
2、每棵子树的根结点有且仅有一 个直接前驱，可有零个或多个直接后继。 1树的基本概念 例如：一棵树的逻辑结构图（6.1）为：ABCDGFEHIJKLM从图中可以看出它好象一棵倒栽的树。2树的图解表示法 1）倒置树结构（树形表示法）图6.1 2）文氏图表示法（嵌套集合形式） 图6.2FKLEABGCIJMHD3）广义表形式（嵌套扩号表示法 ） 4）凹入表示法 图6.3图6.2 文氏图表示法图6.3 凹入表示法3.树的相关术语：结点：包含一个数据元素及若干指向其它结点的分支信息。结点的度：一个结点的子树个数称为此结点的度。叶结点：度为0的结点，即无后继的结点，也称为终端结点。 分支结点：度不为0的结点
3、，也称为非终端结点。结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推 。 结点的层次编号：将树中的结点按从上层到下层、同层从左到右的次序排成一个线性序列 ，依次给它们编以连续的自然数。 树的度：树中所有结点的度的最大值。树的高度（深度）：树中所有结点的层次的最大值。有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。森林：m（m0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一 个森林；反之，给森林增加一个统一的根结点，森林就变成一棵树。同构：对两棵树，通过对结点适当地重命名，就可以使两棵树完全相等（结点对应相 等，对应结点的相关关系也
4、像等），则称这两棵树同构。 双亲结点：一个结点的直接前驱称为该结点的双亲结点。上图中A是B、C的双亲。兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。上图中的结点H、I、J互为兄弟结点。 祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。如结 点K的祖先结点是A、B、E。 子孙结点：一个结点的直接后继和间接后继称为该结点的子孙结点。如结点D的子孙是H、I、J、M。 孩子结点：一个结点的直接后继称为该结点的孩子结点。如上图的B、C是A的孩子。 我们常常借助人类家族树的术语，以便于直观理解结点间的层次关系。 堂兄弟：父亲是兄弟关系或堂兄关系的结点称为堂兄弟结点。在图6.1中，结
5、点E、G、H互为堂兄弟。 前辈：层号比该结点小的结点，都称为该结点的前辈。 后辈：层号比该结点大的结点，都称为该结点的后辈。 4.树的抽象数据类型数据对象D：一个集合，该集合中的所有元素具有相 同的特性。 数据关系R：若D为空集，则为空树。若D中仅含有 一个数据元素，则R为空集，否则R=H，H是如下 的二元关系： (1) 在D中存在唯一的称为根的数据元素root，它在关 系H下没有前驱。 (2) 除root以外，D中每个结点在关系H下都有且仅有 一个前驱。 基本操作：(1) InitTree（Tree）： 将Tree初始化为一棵空树。 (2) DestoryTree（Tree）： 销毁树Tre
6、e。 (3) CreateTree（Tree）： 创建树Tree。 (4) TreeEmpty（Tree）： 若Tree为空，则返回TRUE，否则返回FALSE。 (5) Root（Tree）： 返回树Tree的根。 (6) Parent（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x为非根 结点，则返回它的双亲，否则返回“空”。(7) FirstChild（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x为 非叶子结点，则返回它的第一个孩子结点，否则返回“空”。 (8) NextSibling（Tree，x）： 树Tree存在，x是Tree中的某个结点。若x
7、不 是其双亲的最后一个孩子结点，则返回x后面的下一个兄弟结点，否则 返回“空”。 基本操作:(9) InsertChild（Tree，p，Child）： 树Tree存在，p指向 Tree中某个结点，非空树Child与Tree不相交。将Child插入 Tree中，做p所指向结点的子树。(10) DeleteChild（Tree，p，i）： 树Tree存在，p指向Tree中 某个结点，1id，d为p所指向结点的度。删除Tree中p所指 向结点的第i棵子树。 (11) TraverseTree（Tree，Visit（）： 树Tree存在，Visit （）是对结点进行访问的函数。按照某种次序对树Tre
8、e的每 个结点调用Visit（）函数访问一次且最多一次。若Visit（） 失败，则操作失败。 6.2 二叉树6.2.1 二叉树的定义与基本操作6.2.2 二叉树的性质6.2.3 二叉树的存储结构6.2.1 二叉树的定义与基本操作定义：我们把满足以下两个条件的树型结构叫做二 叉树（Binary Tree）： （1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。下面给出二叉树的五种基本形态：(a)空二叉数(c)只有左子 树的二叉树(b)只有根结 点的二叉树(d)左右子树均 非空的二叉树(e)只有右子树 的二叉树二叉树的基本操作： (1)Initiate（bt）：将bt初始化为空
9、二叉树。 (2) Create(bt)：创建一棵非空二叉树bt。 (3) Destory（bt）： 销毁二叉树bt。 (4) Empty（bt）： 若bt为空，则返回TRUE，否则 返回FALSE。 (5) Root(bt)： 求二叉树bt的根结点。若bt为空二叉 树，则函数返回“空”。 (6) Parent（bt，x）：求双亲函数。求二叉树bt中结 点x的双亲结点。若结点x是二叉树的根结点或二 叉树bt中无结点x，则返回“空”。 基本操作：(7) LeftChild（bt，x）：求左孩子。若结点x为叶子 结点或x不在bt中，则返回“空”。 (8) RightChild（bt，x）：求右孩子。
10、若结点x为叶子 结点或x不在bt中，则返回“空”。 (9) Traverse（bt）: 遍历操作。按某个次序依次访问 二叉树中每个结点一次且仅一次。 (10) Clear（bt）：清除操作。将二叉树bt置为空树。 6.2.2 二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i1)。 当i=1时，整个二叉树只有一根结点，此时2i-1=20=1，结 论成立。 证明：假设i=k时结论成立，即第k层上结点总数最多为2k-1个。 现证明当i=k+1时，结论成立： 因为二叉树中每个结点的度最大为2，则第k+1层的结点 总数最多为第k层上结点最大数的2倍，即22k-1=2(k+1)-1， 故结论
11、成立。 性质2：深度为k的二叉树至多有2k-1个结点（k1） 。 证明：因为深度为k的二叉树，其结点总数的最大值是将二 叉树每层上结点的最大值相加，所以深度为k的二叉 树的结点总数至多为：第i层上的最大结点个数= 2i-1= 2k-1 i=1ki=1k故结论成立。性质3：对任意一棵二叉树T，若终端结点数为n0，而 其度数为2的结点数为n2，则n0= n2+1 。证明：设二叉树中结点总数为n，n1为二叉树中度为1的结点总 数。因为二叉树中所有结点的度小于等于2，所以有n= n0+ n1+n2设二叉树中分支数目为B，因为除根结点外，每个结点均对应 一个进入它的分支，所以有：n=B+1。又因为二叉树
12、中的分支都是由度为1和度为2的结点发出，所以 分支数目为：B=n1+2n2整理上述两式可得到：n=B+1=n1+2n2+1将n= n0+ n1+n2代入上式得出n0+ n1+n2=n1+2n2+1，整理后得 n0= n2+1，故结论成立。 两种特殊的二叉树：满二叉树：深度为k且有2k-1个结点的二叉树。在满 二叉树中，每层结点都是满的，即每层结点都具有最 大结点数。 12345678910111213 1415满二叉树完全二叉树：12345678910111213 14关系：满二叉树必为完全二叉树，而完全二叉树不一 定是满二叉树。 深度为k，结点数为n的二叉树，如果其结点1n的位置序 号分别与
13、满二叉树的结点1n的位置序号一一对应，则为 完全二叉树 性质4：具有n个结点的完全二叉树的深度为2n+1 。 证明：设n个结点的完全二叉树的深度为k，根据性 质2可知，k-1层满二叉树的结点总数为： 2k-1-1 k层满二叉树的结点总数为： 2k-1 显然有：2k-1 - 1 1, 1, 则则 i i 的双亲结点为的双亲结点为 i i /2/2 (2)(2)若若2*2*i i n n, , 则则 i i 无左孩子无左孩子若若2*2*i i n n, , 则则 i i 结点的左孩子结点为结点的左孩子结点为2*2*i i (3)(3)若若 2*2*i+1i+1 n n , ,则则i i 无右孩子无
14、右孩子若若 2*2*i+1i+1 n n, , 则则i i的右孩子结点为的右孩子结点为2* 2* i i+1+1用归纳法证明其中的(2)和(3)。6.2.3 二叉树的存储结构二叉树的结构是非线性的，每一结点最多可有两个 后继。二叉树的存储结构有两种：顺序存储结构和链式 存储结构。1.顺序存储结构：是用一组连续的存储单元来存放二 叉树的数据元素 。ABCDEFGHIJKLA B C D E F G H IJ K L二叉树的顺序存储结构对于一般的二叉树，我们必须按照完全二叉树的 形式来存储，就会造成空间的浪费。单支树就是一 个极端情况。ABCDA B C D单支树2. 链式存储结构对于任意的二叉树
15、来说，每个结点只有两个孩子 ，一个双亲结点。我们可以设计每个结点至少包括三 个域：数据域、左孩子域和右孩子域： LChildDataRChild二叉链表DABCEFGABCDEFG二叉树T二叉链表typedef struct NodeDataType data;strct Node * LChild;struct Node * RChild;BiTNode, *BiTree; 用C语言描述定义二叉树的二叉链表结构如下 ： 结论：若一个二叉树含有n个结点，则它的二 叉链表中必含有2n个指针域，其中必有n1个 空的链域。证明：分支数目B=n-1，即非空的链域有n-1个，故 空链域有2n-(n-1)
16、=n+1个。为了便于找到双亲结点，可以增加一个Parent域， 以指向该结点的双亲结点。采用这种结点结构存放 称做二叉树的三叉链表存储结构。 RChildParentDataLChild三叉链表6.3 二叉树的遍历与线索化6.3.1 二叉树的遍历6.3.2 遍历算法应用6.3.3 基于栈的递归消除6.3.4 线索二叉树6.3.5 由遍历序列确定二叉树6.3 二叉树的遍历与线索化二叉树的遍历：指按一定规律对二叉树中的每个结点进 行访问且仅访问一次。 二叉树的基本结构由根结点、左子树和右子树组成RChildDataLChildDataLChildLChildRChild如图示6.3.1 二叉树的遍历用L、D、R分别表示遍历左子树、访问根结点、遍 历右子树，那么对二叉树的遍历顺序就可以有：(1)访问根，遍历左子树，遍历右子树(记做DLR)。(2)访问根，遍历右子树，遍历
