《c++二叉树》PPT课件

2.5树与二叉树,2.5.1树的基本概念2.5.2二叉树及其基本性质2.5.3二叉树的存储结构2.5.4二叉树的遍历,2.5.1树的基本概念树是一种简单的非线性结构,在这种结构中所有数据元素之间具有明显的层次关系每个结点只有一个前件，称为父结点没有前件的结点称为根结点每个结点有多个后件，都称为该结点的子结点没有后件的结点称为叶子结点,根结点R叶子结点是哪些？,一个结点所拥有的后件个数称为结点的度所有结点中的最大度数称为树的度树的最大层次数称为树的深度以某结点的一个子结点为根构成的树为该结点的一颗子树,R、H、Y、S、T的度分别是多少？这棵树的度？树的深度？,表示原则表达式中的每一个运算符在树中对应一个结点,称为运算符结点运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右）运算对象中的单变量均为叶子结点表示同一个表达式的表达式树是不唯一的,用树表示算术表达式,a*(b+c/d)+e*h-g*f(s,t,x+y),该表达式的第一种表示,a*(b+c/d)+e*h-g*f(s,t,x+y),该表达式的第二种表示,树链表中的结点结构,2.5.2二叉树及其基本性质1.什么是二叉树非空二叉树只有一个根结点每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树,2.二叉树的基本性质性质1在二叉树的第k层上,最多有2k-1(k1)个结点性质2深度为m的二叉树最多有2m-1个结点性质3在任意一棵二叉树中,度为0的结点（即叶子结点）总是比度为2的结点多一个性质4具有n个结点的二叉树,其深度至少为log2n+1,其中log2n表示取log2n的整数部分,3.满二叉树与完全二叉树满二叉树除最后一层外，每一层上的所有结点都有两个子结点,完全二叉树除最后一层外，每一层上的结点数均达到最大值；最后一层只缺少右边的若干结点,性质5具有n个结点的完全二叉树的深度为log2n+1,性质6设完全二叉树共有n个结点。如果从根结点开始,按层序（每一层从左到右）用自然数1,2,n给结点进行编号,则对于编号为k(k=1,2,n)的结点有以下结论：若k=1,则该结点为根结点,它没有父结点;若k1,则该结点的父结点编号为INT(k/2)。若2kn,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点（显然也没有右子结点）。若2k+1n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点,2.5.3二叉树的存储结构1.二叉链表,#includestdlib.hstructbtnode/*定义结点类型*/ETd;/*数据域*/structbtnode*lchild;/*左指针域*/structbtnode*rchild;/*右指针域*/;,2.二叉链表的生成STEP1输入根结点值;STEP2若左子树不空,则输入左子树,否则输入一个结束符;STEP3若右子树不空,则输入右子树,否则输入一个结束符。例如FCADBEGHP其中表示结束符,二叉链表的生成输入：二叉链表的头指针BT为空;根结点标志k=0输出：二叉链表的头指针BT,PROCEDURECREATBT(BT,k)INPUTbIFb结束符THEN输入的不是结束符NEW(p)取一个新结点V(p)=b;L(p)=0;R(p)=0置新结点的值域为b及左右指针域IFk=0THENBT=p若是第一个值,则置二叉链表头指针IFk=1THENL(BT)=p链接到左子树IFk=2THENR(BT)=p链接到右子树CREATBT(p,1)输入左子结点值CREATBT(p,2)输入右子结点值RETURN,#includestdio.h”#includestdlib.h”structbtnodeintd;structbtnode*lchild;structbtnode*rchild;structbtnode*creatbt(structbtnode*bt,intk)intb;structbtnode*p,*t;printf(inputb：);scanf(%d,if(b!=0)/*输入的不是结束符*/p=(structbtnode*)malloc(sizeof(structbtnode);p-d=b;p-lchild=NULL;p-rchild=NULL;if(k=0)t=p;if(k=1)bt-lchild=p;/*链接到左子树*/if(k=2)bt-rchild=p;/*链接到右子树*/creatbt(p,1);/*输入左子结点值*/creatbt(p,2);/*输入右子结点值*/return(t);/*返回二叉链表头指针*/,#includestdio.h”#includestdlib.h”main()structbtnode*bt;bt=creatbt(bt,0);pretrav(bt);/前序遍历,2.5.4二叉树的遍历二叉树的遍历是指不重复的访问二叉树中的所有结点。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历和后序遍历。,1.前序遍历(DLR)若二叉树为空,则结束返回。否则：(1)访问根结点;(2)前序遍历左子树;(3)前序遍历右子树。,前序遍历：,F,C,A,D,B,E,G,H,P,输入：二叉链表的头指针BT。输出：以BT为头指针的二叉链表的前序序列。,PROCEDUREPRETRAV(BT)IFBT0THENOUTPUTV(BT)PRETRAV(L(BT)PRETRAV(R(BT)RETURN,#includestdio.hstructbtnodeintd;structbtnode*lchild;structbtnode*rchild;pretrav(structbtnode*bt)if(bt!=NULL)printf(%dn,bt-d);pretrav(bt-lchild);pretrav(bt-rchild);return;,2.中序遍历(LDR)若二叉树为空,则结束返回。否则：(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。,中序遍历：,A,C,B,D,F,E,H,G,P,输入：二叉链表的头指针BT。输出：以BT为头指针的二叉链表的中序序列,PROCEDUREINTRAV(BT)IFBT0THENINTRAV(L(BT)OUTPUTV(BT)INTRAV(R(BT)RETURN,#includestdio.hstructbtnodeintd;structbtnode*lchild;structbtnode*rchild;intrav(structbtnode*bt)if(bt!=NULL)intrav(bt-lchild);printf(%dn,bt-d);intrav(bt-rchild);return;,3.后序遍历(LRD)若二叉树为空,则结束返回。否则：(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。,后序遍历：,A,B,D,C,H,P,G,E,F,输入：二叉链表的头指针BT。输出：以BT为头指针的二叉链表的后序序列,PROCEDUREPOSTRAV(BT)IFBT0THENPOSTRAV(L(BT)POSTRAV(R(BT)OUTPUTV(BT)RETURN,#includestdio.hstructbtnodeintd;structbtnode*lchild;structbtnode*rchild;postrav(structbtnode*bt)if(bt!=NULL)postrav(bt-l