c++-叉树PPT课件课件.pptVIP

2.5树与二叉树;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(k≥1)个结点

性质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)。

②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点（显然也没有右子结点）。

③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点

;2.5.3二叉树的存储结构

1.二叉链表;;;;2.二叉链表的生成

STEP1输入根结点值;

STEP2若左子树不空,则输入左子树,否则输入一个结束符;

STEP3若右子树不空,则输入右子树,否则输入一个结束符。

例如FCA▲▲DB▲▲▲E▲GH▲▲P▲▲

其中▲表示结束符;二叉链表的生成

输入：二叉链表的头指针BT为空;根结点标志k=0

输出：二叉链表的头指针BT;#includestdio.h”

#includestdlib.h”

structbtnode

{intd;

structbtnode*lchild;

structbtnode*rchild;

};

structbtnode*creatbt(structbtnode*bt,intk)

{intb;

structbtnode*p,*t;

printf(inputb：);

scanf(%d,b);;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)

若二叉树为空,则结束返回。