《数据结构》-二叉树

6.1 树的定义和基本术语,6.2 二叉树,6.3 遍历二叉树和线索二叉树,6.4 树和森林,6.6 哈夫曼树及其应用,第六章 树和二叉树,6.2 二叉树,6.2.1 二叉树的定义,（1）定义 二叉树（Binary Tree）：是另一种树型结构。 特点：每个结点至多只有两棵子树（即二叉树中不存在度大于2 的结点）。 子树有左右之分，其次序不能任意颠倒。,（2）图形表示,(a) (b) (c) (d) (e),图6.3二叉树的5种基本形态,(a) 空二叉树(b) 仅有根结点的二叉树(c) 右子树为空的二叉树(d) 左、右子树均非空的二叉树(e) 左子树为空的二叉树,定义：是由n（n=0)个结点的有限集合，它或为空树（n=0），或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2的结点，并且二叉树的子树有左子树和右子树之分。,二叉树的定义：,二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。,根结点,左子树,右子树,E,F,二叉树的五种基本形态：,N,空树,只含根结点,N,N,N,L,R,R,右子树为空树,L,左子树为空树,左右子树均不为空树,（3）二叉树的抽象数据类型定义,CreateBiTree (初始条件：二叉树T存在， e是T中某个结点。操作结果：结点e赋值为value。,Parent(T, e);初始条件：二叉树T存在， e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则函数值为“空”。 LeftChild(T, e);初始条件：二叉树T存在， e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“空”。 RightChild (T, e);初始条件：二叉树T存在， e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。 LeftSibling(T, e);初始条件：二叉树T存在， e是T中某个结点。操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。 RightSibling (T, e);初始条件：二叉树T存在， e是T中某个结点。操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。 InsertChild(T, P, LR, c);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉 树c与T不相交且右子树为空。操作结果：根据LR为0或1，插入c为T中p指结点的左或右子树。p所指 结点的原有左或右子树则成为c的右子树。,DeleteChild(T, P, LR);初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。 PreOrderTraverse (T, visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：先序遍历T，对每个结点调用函数visit()一次且仅一次。 一旦visit()失败，则操作失败。 InOrderTraverse (T, visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：中序遍历T，对每个结点调用函数visit()一次且仅一次。 一旦visit()失败，则操作失败。 PostOrderTraverse (T, visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：后序遍历T，对每个结点调用函数visit()一次且仅一次。 一旦visit()失败，则操作失败。 LevelOrderTraverse (T, visit();初始条件：二叉树T存在，visit是对结点操作的应用函数。操作结果：层序遍历T，对每个结点调用函数visit()一次且仅一次。 一旦visit()失败，则操作失败。ADT BinaryTree,（4）特殊形态的二叉树,满二叉树：一棵深度为k且有2k1个结点的二叉树称为满二叉树。 特点：每一层上的结点数都是最大结点数。,完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。特点：叶子结点只可能在层次最大的两层上出现； 对任一结点，若其右分支下的子孙的最大层次为l， 则其左分支下的子孙的最大层次必为l或l1。,(a) 满二叉树,(b) 完全二叉树,图6.4特殊形态的二叉树,(c) 非完全二叉树 (d) 非完全二叉树,6.2.2 二叉树的性质,用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点， 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立;,二叉树上每个结点至多有两棵子树，则第 i 层的结点数 = 2i-2 2 = 2i-1 。,性质 1 ： 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1,性质 2 ： 深度为 k 的二叉树上至多含 2k-1 个结点（k1）,证明：,设 二叉树上结点总数 n = n0 + n1 + n2,又 二叉树上分支总数 b = n1 + 2n2,而 b = n-1 = n0 + n1 + n2 - 1,由此， n0 = n2 + 1,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1,除根结点外，其余结点都有一个分支进入，设b为分支总数，则n=b+1。,两类特殊的二叉树：,满二叉树：指的是深度为k且含有2k-1个结点的二叉树。,这种树的特点是每一层上的结点数都是最大结点数。,两类特殊的二叉树：,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树。,完全二叉树的特点（1）叶子结点只可能在层次最大的两层出现；（2）对任一结点，若其右分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次为l或l+1。,性质 4 ： 具有 n 个结点的完全二叉树的深度为 log2n +1,证明：,设 完全二叉树的深度为 k,则根据第二条性质得 2k-1 n 2k,即 k-1 log2 n n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,性质 5 ：,6.2.3 二叉树的存储结构,二、二叉树的链式存储表示,一、 二叉树的顺序存储表示,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0号单元存储根结点SqBiTree bt;,一、 二叉树的顺序存储表示,用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i1的分量中。,例如:,1,4,0,13,2,6,图6.5二叉树的顺序存储结构,(a)完全二叉树,(b)一般二叉树,图中以“0”表示不存在此结点,6 7,1,2 3,4 5,root,结点结构:,二、二叉树的链式存储表示,图形表示,(a)单支树的二叉链表,(b)二叉链表,图6.7二叉链表存储结构,易知，在含有n个结点的二叉链表中有n1个空链域。,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,结点结构:,C 语言的类型描述如下:,root,2三叉链表,结点结构:,typedef struct TriTNode / 结点结构 TElemT