数据结构第六章树和二叉树.ppt

《数据结构第六章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章树和二叉树.ppt（62页珍藏版）》请在三一办公上搜索。

1、,第六章 树和二叉树,第一节 树的类型定义,A 为“根”T1、T2和T3都是一棵树，称为A的子树。称根和子树根之间的连线为“分支”结点分支的个数定义为“结点的度”，如结点B的度为2，D 的度为3。树中所有结点度的最大值定义为“树的度”。称度为零的结点为“叶子”或“终端结点”所有度不为零的结点被称作分支结点,基本定义,森林为 m(m0)棵互不相交的树的集合。树的深度定义为树中叶子结点所在最大层次数。称根结点为子树根的双亲。称子树根为根结点的孩子“根的所有子树根互为“兄弟”。有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,树的抽象数据类型：,

2、ADT Tree 数据对象：D是具有相同特性的数据元素的集合。数据关系：若 D 为空集，则称为空树；若 D 中仅含一个数据元素，则关系R为空集；否则 R=H，(1)在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱；(2)当n1时，其余数据元素可分为 m(m0)个互不相交的(非空)有限集 T1,T2,Tm,其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都是根 root 的后继，即 H,i=1,2,m。,基本操作：结构初始化InitTree(初始条件：树 T 存在。操作结果：销毁树 T。,引用型操作TreeEmpty(T);初始条件：树 T

3、 存在。操作结果：若 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 是T的非根结点，则返回它的双亲，否则返回空。LeftChild(T,cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：若 c

4、ur_e 是T的非叶子结点，则返回它的最左孩子，否则返回空。RightSibling(T,cur_e);初始条件：树 T 存在，cur_e 是 T 中某个结点。操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回空。TraverseTree(T,visit();初始条件：树T存在，visit 是对结点操作的应用函数。操作结果：按某种次序对 T 的每个结点调用函数 visit()一次且至多一次。一旦 visit()失败，则操作失败。,加工型操作Assign(T,cur_e,value);初始条件：树T存在，cur_e 是 T 中某个结点。操作结果：结点 cur_e 赋值为 value。

5、ClearTree(初始条件：树 T 存在，p 指向 T 中某个结点，1ip 指结点的度。操作结果：删除 T 中 p 所指结点的第 i 棵子树。ADT Tree,树和线性结构对照：,第二节 二叉树类型,定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。,二叉树的5种形态：,(a),(b),(c),(d),(e),6.

6、2.1 二叉树的类型定义,ADT BinaryTree 数据对象：D 是具有相同特性的数据元素的集合。数据关系：若 D 为空集，称 BinaryTree 为空二叉树；否则 关系 R=H：(1)在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱；(2)D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点，它是 root 的左后继(H)，如果右子树 R 不空，则必存在一个根结点 为 root 的右后继(H)。,基本操作P：结构初始化InitBiTree(初始条件

7、：二叉树 T 存在。操作结果：销毁二叉树 T。,引用型操作BiTreeEmpty(T);初始条件：二叉树 T 存在。操作结果：若T为空二叉树，则返回 TRUE，否则返回 FALSE。BiTreeDepth(T);初始条件：二叉树 T 存在。操作结果：返回 T 的深度。Root(T);初始条件：二叉树 T 存在。操作结果：返回 T 的根。Value(T,e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的值。,Parent(T,e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回空。LeftChild(T,e

8、);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的左孩子。若 e 无左孩子，则返回空。RightChild(T,e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的右孩子。若 e 无右孩子，则返回空。LeftSibling(T,e);初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：返回 e 的左兄弟。若 e 是其双亲的左孩子或无左兄弟，则返回空。,RightSibling(T,e);初始条件：二叉树 T 存在，e 是 T 的结点。操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟，则返回空。PreOrderTr

9、averse(T,visit();初始条件：二叉树 T 存在,visit 是对结点操作的应用函数。操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败，则操作失败。InOrderTraverse(T,vsit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit()失败，则操作失败。PostOrderTraverse(T,visit();初始条件：二叉树T存在，visit 是对结点操作的应用函数。操作结果：后序遍历 T，对每个结点调用函数 visit

10、一次且仅一次。一旦 visit()失败，则操作失败。,LevelOrderTraverse(T,visit();初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit()失败，则操作失败。加工型操作ClearBiTree(初始条件：二叉树 T 存在，e 是 T 中某个结点。操作结果：结点 e 赋值为 value。,InsertChild(初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。ADT B

11、inaryTree,6.2.2 二叉树的几个特性,一、在二叉树的第 i 层上至多有 2i-1 个结点(i1)。二、深度为k的二叉树中至多含有 2k-1 个结点，(k1)。三、对任何一棵二叉树 T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1,若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。假如一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为1至 n 的结点一、一对应，则称这类二叉树为完全二叉树。,第三节 二叉树的存储表示,6.3.1 顺序存储结构 二叉树的顺序存储结构的定义如下：const MAXSIZE=100;/暂定

12、二叉树中结点数的最大值为100typedef struct ElemType*data;/存储空间基址(初始化时分配空间)int nodeNum;/二叉树中结点数 SqBiTree;/二叉树的顺序存储结构,6.3.2 链式存储结构,二叉树的二叉链表存储表示typedef struct BiTNode ElemType data;struct BiTNode*Lchild,*Rchild;/左、右孩子指针*BiTree;,二叉树的三叉链表存储表示,typedef struct TriTNode ElemType data;struct BiTNode*Lchild,*Rchild;/左、右孩子指

13、针struct BiTNode*parent;/双亲指针*TriTree;,二叉树的双亲链表存储表示,typedef struct BPTNode/结点结构ElemType data;int*parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNode,第四节 二叉树的遍历,“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。由于二叉树中每个结点都有两个后继，则可以有三条搜索路径：1)先左(子树)后右(子树)；2)先右(子树)后左(子树)；3)按层次从上到下。,6.4.1 先左后右的遍历 6-4-1遍历.swf,G H,D E F,B C,A,先序序列：

14、ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA,先序遍历递归算法,void PreOrder(BTree BT)if(BT)Visit(BT);PreOrder(BT-Lchild);PreOrder(BT-Rchild);6-4-2-1.swf,中序遍历递归算法,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);PostOrde

15、r(BT-Rchild);Visit(BT);6-4-2-3.swf,按层次遍历二叉树,按层次遍历该二叉树的序列为：ABCDEFGH,二叉树用链式存储结构表示时，按层遍历的算法实现（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；,void LevelOrder(BTree*BT)if(!BT)exit;InitQueue(Q);p=BT;/初始化 Visite(p);EnQueue(/处理右孩子,建立二叉树,void CreateBiTree(BiTree/递归建

16、(遍历)右子树 6-4-6.swf,统计二叉树中叶子结点的个数,void CountLeaf(BiTree T,int/if,求二叉树的深度,void BiTreeDepth(BiTree T,int level,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=rpt

17、r;return T;,后序遍历复制二叉树的操作为:BiTNode*CopyTree(BiTNode*T)/已知二叉树的根指针为 T，本算法返回它的复制品的根指针if(!T)return NULL;/复制一棵空树if(T-Lchild)newlptr=CopyTree(T-Lchild);/复制(遍历)左子树else newlptr=NULL;if(T-Rchild)newrptr=CopyTree(T-Rchild);/复制(遍历)右子树else newrptr=NULL;newnode=GetTreeNode(T-data,newlptr,newrptr);/生成根结点return new

18、node;6-4-5后序遍历复制.swf,在二叉树上查询某个结点,void locate(BiTree T,ElemType x,BiTree,中序遍历（非递归）,InitStack(S);Push(S,T);/根入栈while(!StackEmpty(S)while(GetTop(S,p),表达式的二叉树,二叉树的线索链表,将在二叉树中每个结点（除第一个和最后一个外）的直接前驱和直接后继保存起来。这种信息是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。typedef enum PointerT

19、ype Link=0,Thread=1;/定义指针类型，以 Link 表示指针，Thread 表示线索typedef struct BiThrNodeElemType data;struct BiThrNode*Lchild,*Rchild;/左右指针PointerType LTag,RTag;/左右指针类型标志*BiThrTree;,在线索链表中添加了一个头结点，头结点的左指针指向二叉树的根结点，其右线索指向中序序列中的最后一个结点,以中序线索链表为存储结构的中序遍历,void InOrderTraverse_Thr(BiThrTree T,void(*Visit)(ElemType e)/

20、T 指向中序线索链表中的头结点，头结点的左指针 Lchild 指向二叉树的根结点，头结点的右线索 Rchild 指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历，对树中每个元素调用函数 Visit 进行访问操作p=T-Lchild;/p 指向二叉树的根结点while(p!=T)/空树或遍历结束时，p=Theadwhile(p-LTag=Link)p=p-Lchild;Visit(p-data);/访问其左子树为空的结点while(p-RTag=Thread/p 进至其右子树根,p=T-Lchild;/p 指向二叉树的根结点while(p!=T)/空树或遍历结束时，p=Theadwh

21、ile(p-LTag=Link)p=p-Lchild;Visit(p-data);/访问其左子树为空的结点while(p-RTag=Thread/p 进至其右子树根 6-5-1.swf,线索链表的生成,void InThreading(BiThrTree p，BiThrTree/对右子树进行线索化,void InOrderThreading(BiThrTree/建非空树的头结点的右线索 6-5-2.swf,树和森林的存储表示 1 树的双亲表示法,const MAX_TREE_SIZE=100;typedef struct/结点结构ElemType data;int parent;/双亲位置域

22、PTNode;typedef struct/树结构PTNode nodesMAX_TREE_SIZE;int r,n;/根的位置和结点数 PTree;,2 树的孩子表示法,树的孩子链表存储表示typedef struct CTNode/孩子结点int child;struct CTNode*next;*ChildPtr;typedef struct ElemType data;/结点的数据元素ChildPtr firstchild;/孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;,

23、3 树和森林的孩子兄弟表示法,存储表示 typedef struct CSNodeElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;firstchild 指向该结点的第一个子树根结点，nextsibling 指向它的下一个兄弟结点。,树的孩子-兄弟链表,森林的孩子-兄弟链表,森林和二叉树的转换,森林二叉树 6-6-1.swf,二叉树森林 6-6-2.swf,树的遍历,一、先根(次序)遍历树 若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树；ABEHIJCDFGK 6-7-3.swf,二、后根(次序

24、)遍历树若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点；HIJEBCFKGDA 6-7-4.swf,森林的遍历,一、先序遍历森林 若森林不空，则可依下列次序进行遍历(1)访问森林中第一棵树的根结点；(2)先序遍历第一棵树中的子树森林；(3)先序遍历除去第一棵树之后剩余的树构成的森林。二、中序遍历森林 若森林不空，则可依下列次序进行遍历：(1)中序遍历第一棵树中的子树森林；(2)访问森林中第一棵树的根结点；(3)中序遍历除去第一棵树之后剩余的树构成的森林。,求森林的深度,森林的深度=Max每一棵树的深度树的深度=其子树森林的深度+1int Depth_Tree(CSTree T)/T 是以孩子-兄弟链表存储的森林的头指针，返回该森林的深度if(!T)return 0;else dep=0;/初始化森林的深度为0p=T;/指针 p 指向第一棵树的根while(p)d=Depth_Tree(p-firstchild);/返回*p 的子树森林的深度if(d+1dep)dep=d+1;/求各棵树的深度的最大值 p=p-nextsibling;/指针 p 移向下一棵树的根 return dep;,