c++二叉树PPT课件

1、.,2.5 树与二叉树,2.5.1 树的基本概念 2.5.2 二叉树及其基本性质 2.5.3 二叉树的存储结构 2.5.4 二叉树的遍历,.,2.5.1 树的基本概念 树是一种简单的非线性结构,在这种结构中所有数据元素之间具有明显的层次关系 每个结点只有一个前件，称为父结点 没有前件的结点称为根结点 每个结点有多个后件，都称为该结点的子结点 没有后件的结点称为叶子结点,.,根结点R 叶子结点是哪些？,.,一个结点所拥有的后件个数称为结点的度 所有结点中的最大度数称为树的度 树的最大层次数称为树的深度 以某结点的一个子结点为根构成的树为该结点的一颗子树,.,R、H、Y、S、T的度分别是多少？ 这

2、棵树的度？ 树的深度？,.,.,.,表示原则 表达式中的每一个运算符在树中对应一个结点,称为运算符结点 运算符的每一个运算对象在树中为该运算符结点的子树（在树中的顺序为从左到右） 运算对象中的单变量均为叶子结点 表示同一个表达式的表达式树是不唯一的,用树表示算术表达式,.,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

3、.二叉树的基本性质 性质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个结点。如果从根结点开始

4、,按层序（每一层从左到右）用自然数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.二叉链表,#include stdlib.h struct btnode /*定义结点类型*/ ET d; /*数据域*/ struct btnode *lchild; /*左指针域*

5、/ struct btnode *rchild; /*右指针域*/ ;,.,.,.,.,2.二叉链表的生成 STEP1 输入根结点值; STEP2 若左子树不空,则输入左子树,否则输入一个结束符; STEP3 若右子树不空,则输入右子树,否则输入一个结束符。 例如FCADBEGHP 其中表示结束符,.,二叉链表的生成 输入：二叉链表的头指针BT为空;根结点标志k=0 输出：二叉链表的头指针BT,PROCEDURE CREATBT(BT,k) INPUT b IF b结束符 THEN 输入的不是结束符 NEW(p) 取一个新结点 V(p)=b; L(p)=0; R(p)=0 置新结点的值域为b及

6、左右指针域 IF k=0 THEN BT=p 若是第一个值,则置二叉链表头指针 IF k=1 THEN L(BT)=p 链接到左子树 IF k=2 THEN R(BT)=p 链接到右子树 CREATBT(p,1) 输入左子结点值 CREATBT(p,2) 输入右子结点值 RETURN,.,#include stdio.h” #include stdlib.h” struct btnode int d; struct btnode *lchild; struct btnode *rchild; ; struct btnode *creatbt(struct btnode *bt, int k)

7、int b; struct btnode *p, *t; printf(input b ：); scanf(%d,.,if (b!=0) /*输入的不是结束符*/ p=(struct btnode *)malloc(sizeof(struct btnode); 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); /*输入右子结点值*/

8、return(t); /*返回二叉链表头指针*/ ,.,#include stdio.h” #include stdlib.h” main() struct btnode *bt; bt = creatbt( bt , 0); pretrav ( bt ); /前序遍历 ,.,2.5.4 二叉树的遍历 二叉树的遍历是指不重复的访问二叉树中的 所有结点。 在先左后右的原则下，根据访问根结点的次 序，二叉树的遍历可以分为三种：前序遍历、 中序遍历和后序遍历。,.,1.前序遍历(DLR) 若二叉树为空,则结束返回。否则： (1)访问根结点; (2)前序遍历左子树; (3)前序遍历右子树。,.,前序遍

9、历：,F,C,A,D,B,E,G,H,P,.,输入：二叉链表的头指针BT。 输出：以BT为头指针的二叉链表的前序序列。,PROCEDURE PRETRAV(BT) IF BT0 THEN OUTPUT V(BT) PRETRAV(L(BT) PRETRAV(R(BT) RETURN,.,#include stdio.h struct btnode int d; struct btnode *lchild; struct btnode *rchild; ; pretrav(struct btnode * bt) if (bt !=NULL) printf(%dn,bt-d); pretrav(b

10、t-lchild); pretrav(bt-rchild); return; ,.,2.中序遍历(LDR) 若二叉树为空,则结束返回。否则： (1)中序遍历左子树; (2)访问根结点; (3)中序遍历右子树。,.,中序遍历：,A,C,B,D,F,E,H,G,P,.,输入：二叉链表的头指针BT。 输出：以BT为头指针的二叉链表的中序序列,PROCEDURE INTRAV(BT) IF BT0 THEN INTRAV(L(BT) OUTPUT V(BT) INTRAV(R(BT) RETURN,.,#include stdio.h struct btnode int d; struct btnod

11、e *lchild; struct btnode *rchild; ; intrav(struct btnode * 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为头指针的二叉链表的后序序列,PROCEDURE POSTRAV(BT) IF BT0 THEN POSTRAV(L(BT) POSTRAV(R(BT) OUTPUT V(BT) RETURN,.,#include stdio.h struct btnode int d; struct btnode *lchild; struct btnode *rchild; ; postrav(struct btnode * bt) if (bt!=NULL) postr