《清华大学》ppt课件
清华大学 黄维通 设计制作,1,第14章 二叉树及其应用,清华大学 黄维通 设计制作,2,本章主要内容,树的概念 关于树的一些术语及特性 二叉树的特点与数学性质 二叉树的基本操作及其实现 二叉树的应用,清华大学 黄维通 设计制作,3,树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。,14.1 树的概念,清华大学 黄维通 设计制作,4,清华大学 黄维通 设计制作,5,结点的度：一个结点的子结点的个数称为该结点的度。一棵树的度是指该树中结点的最大度数。,终端结点：树中度为零的结点称为终端结点，树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。,14.2 关于树的一些术语及特性,清华大学 黄维通 设计制作,6,路径：如果存在树中的一个结点序列K1,K2,Kj，使得结点Ki是结点Ki+1的父结点(1ij)，则称该结点序列是树中从结点K1到结点Kj的一条路径或道路。,结点高度：树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。树的高度是指根结点的高度。,清华大学 黄维通 设计制作,7,层：从树根到任一结点n有惟一的一条路径，这条路径的长度称为结点n的深度或层数。,有序树：树的定义在某些结点之间确定了父子关系（可延拓为祖先子孙关系）。但是树中兄弟结点之间就没有祖先子孙关系。若在树的每一组兄弟结点之间定义一个从左到右的次序，则得到一棵有序树；否则称为无序树,清华大学 黄维通 设计制作,8,14.3 二叉树的特点与数学性质,二叉树的定义 二叉树是一种特殊的树型结构，其每个节点最多只有两个子树 二叉树是结点的有限集合，该集合或是空集，或是一个根 特点： 每一个结点至多有两个后继结点，且有左右之分，不能任意交换，这些结点分别称为左子树，右子树。,清华大学 黄维通 设计制作,9,14.3.1 二叉树的特点,清华大学 黄维通 设计制作,10,(a)只有左子树,(b)只有右子树,清华大学 黄维通 设计制作,11,14.3.2 两种特殊形态的二叉树,满二叉树,一棵高度为n0且有2n+1-1个结点的二叉树称为满二叉树,清华大学 黄维通 设计制作,12,近似满二叉树,若一棵二叉树至多只有最下面的两层结点的度数小于2，并且最下面一层结点都集中在该层的最左边，则称这种二叉树为近似满二叉树(有时也称为完全二叉树)。,清华大学 黄维通 设计制作,13,非近似满二叉树,在近似满二叉树中，若某个结点没有左儿子，则它一定没有右儿子，即该结点是一个叶结点,清华大学 黄维通 设计制作,14,14.3.3 二叉树的数学性质,高度为n0的二叉树至少有n+1个结点 高度不超过n(0)的二叉树至多有2n+1-1个结点 含有n1个结点的二叉树的高度至多为n-1，至少为lg(n),清华大学 黄维通 设计制作,15,14.4二叉树的基本操作及其实现,清华大学 黄维通 设计制作,16,二叉树的常用操作如下： InitTree(&T)：构造一棵空二叉树； DestroyTree(&T)：销毁一棵二叉树； Parent(T, e)：返回二叉树T中e结点的父结点，若不存在则返回“空”； LeftChild(T,e)：返回二叉树T中e结点的左儿子结点，若不存在则返回“空”； RightChild(T,e)：返回二叉树T中e结点的右儿子结点，若不存在则返回“空”； Value(T,e)：返回二叉树T中e结点的值； Root(T)：返回二叉树T的根结点。,14.4.1 二叉树的基本操作,清华大学 黄维通 设计制作,17,1 二叉树的顺序存储结构,#define MAXLENGTH 255 #define TYPE int struct TTree int nTreeSize; TYPE nodeMAXLENGTH; ; typedef struct TTree Tree;,14.4.2 二叉树基本操作的实现,清华大学 黄维通 设计制作,18,顺序存储结构实现ADT二叉树的操作: void InitTree(Tree *T) /构造空树 int i; T-nTreeSize = 0; for(i=0; inodei = 0; void DestroyTree(Tree *T) /销毁树 int i; T-nTreeSize = 0; for(i=0; inodei = 0; ,清华大学 黄维通 设计制作,19,TYPE Parent(Tree T, int e) /返回父结点 if(e0) return T.node(e-1)/2; else return 0; TYPE LeftChild(Tree T, int e) /返回二叉树T中e结点的左儿子结点 if(e*2+1MAXLENGTH) return T.nodee*2+1; else return 0; ,清华大学 黄维通 设计制作,20,TYPE RightChild(Tree T, int e) /返回二叉树T中e结点的右儿子结点 if(e*2+2 =0 ,清华大学 黄维通 设计制作,21,2 二叉树的链式存储结构,#define TYPE int struct TNode TYPE element; struct TNode * left; struct TNode * right; ; typedef struct TNode Node; typedef struct TNode *Tree;,清华大学 黄维通 设计制作,22,带有指向其父结点指针的二叉树的结构定义如下： #define TYPE int struct TNode TYPE element; struct TNode * parent; struct TNode * left; struct TNode * right; ; typedef struct TNode Node; typedef struct TNode * Tree;,有时需要在二叉树中进行parent操作,清华大学 黄维通 设计制作,23,二叉树的存储表示方法：,A,B,C,D,单分支的二叉链表,清华大学 黄维通 设计制作,24,多分支的二叉链表,清华大学 黄维通 设计制作,25,由于二叉树结构本身的定义是递归的，因此对于二叉树的访问也必然是递归的。 先序遍历，先访问结点，然后遍历左结点、遍历右结点。 中序遍历，先遍历左结点，然后访问该结点，最后遍历右结点。 后序遍历，先遍历左结点，然后遍历右结点，最后访问该结点。,14.5 二叉树的应用,清华大学 黄维通 设计制作,26,10.7 二叉树的应用举例,用二叉树表示表达式 a*(b-c)+d/e,+,/,×,a,d,b,c,e,清华大学 黄维通 设计制作,27,当二叉树生成后，用中序遍历对二叉树进行遍历，就得到一个由小到大的顺序序列，那么什么是中序遍历呢？ 实际上，遍历有三类，它都是对树中全部节点逐一进行某种处理的方法，只是顺序不同 先序(根)遍历树 中序(根)遍历树 后序(根)遍历树 用LDR（L：Left,D：Data,R：Right)分别表示左子树，根节点，右子树则有六种排列方案，若限定先左后右，则只有三种。,先序 DLR： -+a*b-cd/ef 中序 LDR： a+b*c-d-e/f 后序 LRD： abcd-*+ef/-,清华大学 黄维通 设计制作,28,生成二叉排序树的方法,向二叉排序树中插入一个新结点 struct tree *inserttree(root,p) struct tree *root,*p; if(root=NULL) root=p; else if(root-infop-info) root-left=inserttree(root-left,p); else root-right=inserttree(root-right,p); return(root); ,清华大学 黄维通 设计制作,29,遍历二叉树的算法 中序遍历二叉树,inorder(root) struct tree *root; if(!root) return; inorder(root-left); printf(“%c“,root-info); inorder(root-right); ,清华大学 黄维通 设计制作,30,二叉树的遍历算法 先序遍历二叉树,preorder(root) struct tree *root; if(!root) return; printf(“%c“,root-info); preorder(root-left); preorder(root-right); ,清华大学 黄维通 设计制作,31,二叉树的遍历算法 后序遍历二叉树,postorder(root) struct tree *root; if(!root) return; postorder(root-left); postorder(root-right); printf(“%c“,root-info); ,清华大学 黄维通 设计制作,32,清华大学 黄维通 设计制作,33,【例】从键盘读入一组数据并创建一个二叉树，数据插入时按照左结点小于等于该结点，右结点大于该结点的规则。例如，用户输入： 8 6 4 5 7 3 1 2 请建立二叉树，并用先序、中序和后序遍历 #include #include struct Tnode /二叉树存储结构 int data; struct TNode * left; struct TNode * right; ;,清华大学 黄维通 设计制作,34,typedef struct TNode *Tree; void Insert(Tree *t, int value) /插入结点 struct TNode *tmp; Tree T =*t; if(T = NULL) tmp=(struct TNode *)malloc (sizeof(struct TNode); tmp-data = value; /初始化结点 tmp-left = NULL; tmp-right = NULL; *t = tmp; ,清华大学 黄维通 设计制作,35,else if( value data) /插入右子树 if(T-left != NULL) Insert( ,清华大学 黄维通 设计制作,36,else if(T-right != NULL) /插入左子树 Insert( ,清华大学 黄维通 设计制作,37,void PreOrder(Tree T) /先序遍历 if(T = NULL) return; else printf(“%dt“,T-data); PreOrder(T-left); PreOrder(T-right); ,清华大学 黄维通 设计制作,38,void MidOrder(Tree T) /中序遍历 if(T = NULL) return; else MidOrder(T-left); printf(“%dt“,T-data); MidOrder(T-right); ,清华大学 黄维通 设计制作,39,void PostOrder(Tree T) /后序遍历 if(T = NULL) return; else PostOrder(T-left); PostOrder(T-ri
