2.5 树与二叉树树与二叉树n2.5.1 树的基本概念树的基本概念n2.5.2 二叉树及其基本性质二叉树及其基本性质n2.5.3 二叉树的存储结构二叉树的存储结构n2.5.4 二叉树的遍历二叉树的遍历n2.5.1 树的基本概念树的基本概念树是一种简单的树是一种简单的非线性结构非线性结构,在这种结构中所有在这种结构中所有数据元素之间具有明显的数据元素之间具有明显的层次关系层次关系每个结点只有一个前件，称为每个结点只有一个前件，称为父结点父结点没有前件的结点称为没有前件的结点称为根结点根结点每个结点有多个后件，都称为该结点的每个结点有多个后件，都称为该结点的子结点子结点没有后件的结点称为没有后件的结点称为叶子结点叶子结点根结点根结点R叶子结点是哪些？叶子结点是哪些？一个结点所拥有的后件个数称为一个结点所拥有的后件个数称为结点的度结点的度所有结点中的最大度数称为所有结点中的最大度数称为树的度树的度树的最大层次数称为树的最大层次数称为树的深度树的深度以某结点的一个子结点为根构成的树为该结点以某结点的一个子结点为根构成的树为该结点的一颗的一颗子树子树R、H、Y、S、T的度分别是多少？的度分别是多少？这棵树的度？这棵树的度？树的深度？树的深度？n表示原则表示原则表达式中的每一个表达式中的每一个运算符运算符在树中对应一个结点在树中对应一个结点,称为运算符结点称为运算符结点运算符的每一个运算符的每一个运算对象运算对象在树中为该运算符结在树中为该运算符结点的子树（在树中的顺序为从左到右）点的子树（在树中的顺序为从左到右）运算对象中的运算对象中的单变量单变量均为叶子结点均为叶子结点表示同一个表达式的表示同一个表达式的表达式树表达式树是是不唯一不唯一的的用树表示算术表达式用树表示算术表达式na*(b+c/d)+e*h-g*f(s,t,x+y)该表达式的第一种表示该表达式的第一种表示na*(b+c/d)+e*h-g*f(s,t,x+y)该表达式的第二种表示该表达式的第二种表示树链表中的结点结构树链表中的结点结构n2.5.2 二叉树及其基本性质二叉树及其基本性质1.什么是二叉树什么是二叉树n非空二叉树只有非空二叉树只有一个根结点一个根结点n每一个结点最多有每一个结点最多有两棵子树两棵子树,且分别称为该且分别称为该结点的左子树与右子树结点的左子树与右子树2.二叉树的基本性质二叉树的基本性质n性质性质1 1 在二叉树的第在二叉树的第k层上层上,最多有最多有2k-1 (k1)个结点个结点n性质性质2 2 深度为深度为m的二叉树最多有的二叉树最多有2m-1个结点个结点n性质性质3 3 在任意一棵二叉树中在任意一棵二叉树中,度为度为0的结点的结点 （即叶子结点）总是比度为（即叶子结点）总是比度为2的结点多一个的结点多一个n性质性质4 4 具有具有n个结点的二叉树个结点的二叉树,其深度至少其深度至少为为log2n+1,其中其中log2n表示取表示取log2n的整数部分的整数部分3.满二叉树与完全二叉树满二叉树与完全二叉树n满二叉树满二叉树除最后一层外，每一层上的除最后一层外，每一层上的所有结点都有所有结点都有两个子结点两个子结点n完全二叉树完全二叉树除最后一层外，每一层上除最后一层外，每一层上的结点数均达到最大值；最后一层只缺少右的结点数均达到最大值；最后一层只缺少右边的若干结点边的若干结点n性质性质5 具有具有n个结点的完全二叉树的深度个结点的完全二叉树的深度为为log2n+1n性质性质6 设完全二叉树共有设完全二叉树共有n个结点。如果从根结个结点。如果从根结点开始点开始,按层序（每一层从左到右）用自然数按层序（每一层从左到右）用自然数1,2,n给结点进行编号给结点进行编号,则对于编号为则对于编号为k(k=1,2,n)的结点有以下结论：的结点有以下结论：若若k=1,则该结点为根结点则该结点为根结点,它没有父结点它没有父结点; 若若k1,则该结点的父结点编号为则该结点的父结点编号为INT(k/2)。若若2kn,则编号为则编号为k的结点的左子结点编号为的结点的左子结点编号为2k;否否则该结点无左子结点（显然则该结点无左子结点（显然也没有右子结点也没有右子结点）。）。若若2k+1n,则编号为则编号为k的结点的右子结点编号为的结点的右子结点编号为2k+1;否则该结点无右子结点否则该结点无右子结点n2.5.3 二叉树的存储结构二叉树的存储结构1.二叉链表二叉链表#include stdlib.h struct btnode /*定义结点类型定义结点类型*/ ET d; /*数据域数据域*/ struct btnode *lchild; /*左指针域左指针域*/ struct btnode *rchild; /*右指针域右指针域*/;n2.二叉链表的生成二叉链表的生成STEP1 输入根结点值输入根结点值;STEP2 若左子树不空若左子树不空,则输入左子则输入左子树树,否则输入一个结束符否则输入一个结束符;STEP3 若右子树不空若右子树不空,则输入右子则输入右子树树,否则输入一个结束符。否则输入一个结束符。n例如例如FCADBEGHPn其中其中表示结束符表示结束符n二叉链表的生成二叉链表的生成输入：二叉链表的头指针输入：二叉链表的头指针BT为空为空;根结点标志根结点标志k=0输出：二叉链表的头指针输出：二叉链表的头指针BTPROCEDURE CREATBT(BT,k)INPUT b IF b结束符结束符 THEN 输入的不是结束符输入的不是结束符 NEW(p) 取一个新结点取一个新结点 V(p)=b; L(p)=0; R(p)=0 置新结点的值域为置新结点的值域为b及左右指针域及左右指针域 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) int b; struct btnode *p, *t; printf(input b ：); scanf(%d,&b); 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); /*输入右子结点值输入右子结点值*/ return(t); /*返回二叉链表头指针返回二叉链表头指针*/#include stdio.h”#include stdlib.h”main()struct btnode *bt;bt = creatbt( bt , 0);pretrav ( bt ); /前序遍历前序遍历2.5.4 二叉树的遍历二叉树的遍历 二叉树的遍历是指二叉树的遍历是指不重复的不重复的访问二叉树中的访问二叉树中的所有结点所有结点。 在在先左后右先左后右的原则下，根据的原则下，根据访问根结点的次访问根结点的次序序，二叉树的遍历可以分为三种：，二叉树的遍历可以分为三种：前序前序遍历、遍历、中序中序遍历和遍历和后序后序遍历。遍历。1.前序遍历前序遍历(DLR)n若二叉树为空若二叉树为空,则结束返回。否则：则结束返回。否则：(1)访问根结点访问根结点;(2)前序遍历左子树前序遍历左子树;(3)前序遍历右子树。前序遍历右子树。FCD00B00E0P0G0H0前序遍历：前序遍历：0A0F,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.hstruct btnode int d; struct btnode *lchild; struct btnode *rchild;pretrav(struct btnode * bt) if (bt !=NULL) printf(%dn,bt-d); pretrav(bt-lchild); pretrav(bt-rchild); return;n2.中序遍历中序遍历(LDR)若二叉树为空若二叉树为空,则结束返回。否则：则结束返回。否则：n(1)中序遍历左子树中序遍历左子树;n(2)访问根结点访问根结点;n(3)中序遍历右子树。中序遍历右子树。FCD00B00E0P0G0H0中序遍历：中序遍历：0A0A,C,B,D,F,E,H,G,Pn输入：二叉链表的头指针输入：二叉链表的头指针BT。n输出：以输出：以BT为头指针的二叉链表的中序序列为头指针的二叉链表的中序序列PROCEDURE INTRAV(BT) IF BT0 THEN INTRAV(L(BT) OUTPUT V(BT) INTRAV(R(BT) RETURN#include stdio.hstruct btnode int d; struct btnode *lchild; struct btnode *rchild;intrav(struct btnode * bt) if (bt !=NULL) intrav(bt-lchild); printf(%dn,bt-d); intrav(bt-rchild); return;3.后序遍历后序遍历(LRD)n若二叉树为空若二叉树为空,则结束返回。否则：则结束返回。否则：(1)(1)后序遍历左子树后序遍历左子树; ;(2)(2)后序遍历右子树后序遍历右子树; ;(3)(3)访问根结点。访问根结点。FCD00B00E0P0G0H0后序遍历：后序遍历：0A0A,B,D,C,H,P,G,E,Fn输入：二叉链表的头指针输入：二叉链表的头指针BT。n输出：以输出：以BT为头指针的二叉链表的后序序列为头指针的二叉链表的后序序列PROCEDURE POSTRAV(BT) IF BT0 THEN POSTRAV(L(BT) POSTRAV(R(BT) OUTPUT V(BT) RETURN#include stdio.hstruct btnode int d; struct btnode *lchild; struct btnode *rchild;postrav(struct btnode * bt) if (bt!=NULL) postrav(bt-lchild); postrav(bt-rchild); printf(%dn,bt-d); return;下节课：实验下节课：实验p 顺序、链式存储结构线性表的建立、顺序、链式存储结构线性表的建立、插入及删除的基本运算方法。插入及删除的基本运算方法。p 选一种存储结构用选一种存储结构用C/C+语言描述这语言描述这些算法，上机调试运行。些算法，上机调试运行。 作业：作业： 2.10 写出逆转线性单链表的算法。写出逆转线性单链表的算法。2.21 已知二叉树的前序序列和中序序已知二叉树的前序序列和中序序列，求后序序列。列，求后序序列。