《数据结构第六章树和二叉树资料教程》由会员分享，可在线阅读，更多相关《数据结构第六章树和二叉树资料教程（62页珍藏版）》请在金锄头文库上搜索。
1、,第六章 树和二叉树,第一节 树的类型定义,A 为“根” T1、T2和T3都是一棵树，称为A的子树。 称根和子树根之间的连线为“分支” 结点分支的个数定义为“结点的度”，如结点B的度为2，D 的度为3。 树中所有结点度的最大值定义为“树的度”。 称度为零的结点为“叶子” 或“终端结点” 所有度不为零的结点 被称作分支结点,基本定义,森林为 m(m0) 棵互不相交的树的集合。 树的深度定义为树中叶子结点所在最大层次数。 称根结点为子树根的双亲。 称子树根为根结点的孩子“ 根的所有子树根互为“兄弟”。 有序树、无序树 如果树中 每棵子树从左向右的排列拥有 一定的顺序，不得互换，则称 为有序树，否则
2、称为无序树。,基本操作：结构初始化InitTree(初始条件：树 T 存在。操作结果：销毁树 T。,引用型操作TreeEmpty(T);初始条件：树 T 存在。操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE。TreeDepth(T);初始条件：树T存在。操作结果：返回T的深度。Root(T);初始条件：树 T 存在。操作结果：返回 T 的根。Value(T, cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：返回 cur_e 的值。,Parent(T, cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：若 cur_e
3、 是T的非根结点，则返回它的双亲，否则返回空。LeftChild(T, cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：若 cur_e 是T的非叶子结点，则返回它的最左孩子，否则返回空。RightSibling(T, cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空。TraverseTree(T, visit();初始条件：树T存在，visit 是对结点操作的应用函数。操作结果：按某种次序对 T 的每个结点调用函数 visit() 一次且至多一次。一旦 visit() 失败，则
4、操作失败。,加工型操作Assign(T, cur_e, value);初始条件：树T存在，cur_e 是 T 中某个结点。操作结果：结点 cur_e 赋值为 value。ClearTree(初始条件：树 T 存在，p 指向 T 中某个结点，1ip 指结点的度。操作结果：删除 T 中 p 所指结点的第 i 棵子树。 ADT Tree,树和线性结构对照：,第二节 二叉树类型,定义：二叉树是另一种树形结构。它与树形结构的区别是： （1）每个结点最多有两棵子树； （2）子树有左右之分。 二叉树也可以用递归的形式定义。即：二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一
5、个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。,二叉树的5种形态：,(a),(b),(c),(d),(e),6.2.1 二叉树的类型定义,ADT BinaryTree 数据对象：D 是具有相同特性的数据元素的集合。数据关系：若 D 为空集，称 BinaryTree 为空二叉树；否则 关系 R=H： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L
6、 不空，则必存在一个根结点 ，它是 root 的左后继(H)，如果右子树 R 不空，则必存在一个根结点 为 root 的右后继(H)。,基本操作P：结构初始化 InitBiTree(初始条件：二叉树 T 存在。操作结果：销毁二叉树 T。,引用型操作BiTreeEmpty(T);初始条件：二叉树 T 存在。操作结果：若T为空二叉树，则返回 TRUE，否则返回 FALSE。BiTreeDepth(T);初始条件：二叉树 T 存在。操作结果：返回 T 的深度。Root(T);初始条件：二叉树 T 存在。操作结果：返回 T 的根。Value(T, e);初始条件：二叉树 T 存在，e 是 T 中某个结
7、点。操作结果：返回 e 的值。,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 是其双亲的左孩子或无
8、左兄弟，则返回空。,RightSibling(T, e);初始条件：二叉树 T 存在，e 是 T 的结点。操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟，则返回空。PreOrderTraverse(T, visit();初始条件：二叉树 T 存在,visit 是对结点操作的应用函数。操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。InOrderTraverse(T, vsit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一
9、旦 visit() 失败，则操作失败。PostOrderTraverse(T, visit();初始条件：二叉树T存在，visit 是对结点操作的应用函数。操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。,LevelOrderTraverse(T, visit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则操作失败。 加工型操作ClearBiTree(初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：
10、结点 e 赋值为 value。,InsertChild(初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 ADT BinaryTree,6.2.2 二叉树的几个特性,一、在二叉树的第 i 层上至多有 2i-1 个结点(i1)。 二、深度为k的二叉树中至多含有 2k-1 个结点，(k1)。 三、对任何一棵二叉树 T，如果其终端结点数为n0，度为2的结点数为n2，则n0 =n2+ 1,若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。 假如一棵包含 n
11、个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一、一对应，则称这类二叉树为完全二叉树。,第三节 二叉树的存储表示,6.3.1 顺序存储结构 二叉树的顺序存储结构的定义如下： const MAXSIZE = 100; / 暂定二叉树中结点数的最大值为100typedef struct ElemType *data; / 存储空间基址(初始化时分配空间)int nodeNum; / 二叉树中结点数 SqBiTree; / 二叉树的顺序存储结构,6.3.2 链式存储结构,二叉树的二叉链表存储表示 typedef struct BiTNode ElemType data; struc
12、t BiTNode *Lchild, *Rchild;/ 左、右孩子指针 *BiTree;,二叉树的三叉链表存储表示,typedef struct TriTNode ElemType data; struct BiTNode *Lchild, *Rchild; /左、右孩子指针struct BiTNode *parent;/ 双亲指针 *TriTree;,二叉树的双亲链表存储表示,typedef struct BPTNode / 结点结构ElemType data;int *parent; / 指向双亲的指针 char LRTag;/ 左、右孩子标志域 BPTNode,第四节 二叉树的遍历,“
13、遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。 由于二叉树中每个结点都有两个后继，则可以有三条搜索路径：1) 先左(子树)后右(子树)；2) 先右(子树)后左(子树)；3) 按层次从上到下。,6.4.1 先左后右的遍历 6-4-1遍历.swf,G H,D E F,B C,A,先序序列：ABDGCEFH 中序序列：DGBAECHF 后序序列：GDBEHFCA,先序遍历递归算法,void PreOrder(BTree BT) if (BT) Visit(BT); PreOrder(BT-Lchild); PreOrder(BT-Rchild); 6-4-2-1.swf,中序遍历递归
14、算法,void InOrder(BTree BT) if (BT) InOrder(BT-Lchild); Visit(BT); InOrder(BT-Rchild); 6-4-2-2.swf,后序遍历递归算法,void PostOrder(BTree BT) if (BT) PostOrder(BT-Lchild); PostOrder(BT-Rchild); Visit(BT); 6-4-2-3.swf,按层次遍历二叉树,按层次遍历该二叉树的序列为： ABCDEFGH,二叉树用链式存储结构表示时，按层遍历的算法实现 （1）访问根结点，并将根结点入队； （2）当队列不空时，重复下列操作： 从
15、队列退出一个结点； 若其有左孩子，则访问左孩子，并将其左孩子入队； 若其有右孩子，则访问右孩子，并将其右孩子入队；,void LevelOrder(BTree *BT) if (!BT) exit; InitQueue(Q); p=BT; /初始化 Visite(p); EnQueue( /处理右孩子 ,建立二叉树,void CreateBiTree(BiTree / 递归建(遍历)右子树 6-4-6.swf,统计二叉树中叶子结点的个数,void CountLeaf (BiTree T, int / if,求二叉树的深度,void BiTreeDepth(BiTree T, int level
16、, int 6-4-3求二叉树的深度 .swf,复制二叉树,生成一个二叉树的结点的算法： BiTNode *GetTreeNode(TElemType item,BiTNode *lptr, BiTNode *rptr)/ 生成一个其元素值为 item，左指针为 lptr，右指针为 rptr 的结点T = new BiTNode; T- data = item;T- Lchild = lptr; T- Rchild = rptr;return T;,后序遍历复制二叉树的操作为: BiTNode *CopyTree(BiTNode *T)/ 已知二叉树的根指针为 T，本算法返回它的复制品的根指针if (!T )return NULL; / 复制一棵空树 if (T-Lchild) newlptr = CopyTree(T-Lchild); / 复制(遍历)左子树else newlptr = NULL; if
