树和二叉树.ppt

C
E
D
F
C
D
C

D
F
E F 二叉链表
E
二叉树
三叉链表
三叉链表的静态结构
root data parent lchild rchild 0 1 2 3 4 5 A B C D E F -1 0 1 1 3 3 1 2 -1 4 -1 -1 -1 3 -1 5 -1 -1
A
B C E D F
0
1 3 7 8 9 4 5
2 6
4. 二叉树的存储结构
顺序表示
1
2 4 5 6 3 7 7 4 8 2 5 9 1 3 6 10 9
8 9 10
1 2 3 4 5 6 7 8 910
完全二叉树 的顺序表示
1 2 3 4 0 5 6 7 8 0 0 0 0 910
一般二叉树 的顺序表示
链表表示
第六章 树和二叉树




1. 2. 3. 4. 5. 6.
树的定义和基本术语 二叉树 遍历二叉树与线索二叉树 树与森林 赫夫曼树 及其应用 二叉树的计数
6.1 树的定义和基本术语
树的定义
树是由 n (n 0) 个结点组成的有限集合。如果 n = 0， 称为空树；如果 n > 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直 接后继，但没有直接前驱； 当n > 1，除根以外的其它结点划分为 m (m >0) 个互不 相交的有限集 T1, T2 ,…, Tm，其中每个集合Ti本身又是一 棵树，并且称为根的子树(SubTree)。
特点
每个结点至多只有两棵非空子树（二叉树中 不存在度大于2的结点）
2.五种形态

这里，若T为根指针，则遍历左右子树时，是分别遍历以 T->lchild 和T->rchild 为根指针旳子树。
因为各子树旳遍历和整个二叉树旳遍历方式相同，所以， 各子树旳遍历可递归调用二叉树旳遍历算法。
先序遍历递归算法如下：
void PreOrder ( BiTree *T) { if ( T )
设B为分支总数，则n=B+1 又：分支由度为1和度为2旳结点射出， B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1
两种特殊形式旳二叉树
满二叉树 —— 一棵深度为k且有2 k-个1结点旳二叉树
特点：每一层上旳结点数都是最大结点数
完全二叉树 —— 深度为k，有n个结点旳二叉树当且仅当其每一种结点 都与深度为k旳满二叉树中编号从1至n旳结点一一相应 特点： 叶子结点只可能在层次最大旳两层上出现 对任一结点，若其右分支下子孙旳最大层次为l，则其 左分支下子孙旳最大层次必为l 或l+1
D HJ M
I
C G
A
B E K
L F C G D H
M I J
(A (B(E(K , L) , F) , C(G) , D(H(M) , I , J)))
树和二叉树
6.1 树旳定义和基本术语 ☞ 6.2 二叉树
6.3 遍历二叉树 6.4 线索二叉树 6.5 树和森林 6.6 哈夫曼树
6.2 二叉树
b cd
a f
g
eh i
j
6.3 遍历二叉树
6.3.1 遍历二叉树
☞ 6.3.2 遍历二叉树旳递归算法
6.3.3 遍历二叉树旳非递归算法 6.3.4 递归算法旳应用（3个算法）

if((p=InsertR(17,q))==NULL){

}

printf("插入出错\n");

exit(0);

p=bt;

}

for(i=1;i<10;i++){

p=bt->LChild;

if((p=InsertL(i,p))==NULL){
printf("-------The Print Tree-------\n");
nodetype *DeleteL(nodetype *bt,nodetype *Parent); //5、在二叉树bt中删除结点Parent的左子 树
nodetype *DeleteR(nodetype *bt,nodetype *Parent); //6、在二叉树bt中删除结点Parent的右子 树
§7、树与二叉树
1．树和二叉树的基本概念
（1）树：树是n个结点的有限集，有且仅有一个根，其余结点为互不相 交的子集。
（2）度：一个结点拥有的子树数。一棵树中最大的接点度数为这棵树 的度。
（3）叶子：度为0的结点，又称端结点。 （4）孩子：除根结点外，每个结点都是其前驱结点的孩子。 （5）双亲：对应孩子结点的上层结点称为这些结点的双亲。 （6）兄弟：同一孩子的孩子。 （7）结点的层次：从根结点开始算起，根为第一层，根的直接后继结
点为第二层，其余各层依次类推。 （8）深度：树中结点的最大层次数。 （9）森林：是m（m≥0）棵互不相交的树的集合。 （10）路径：树中存在结点系列，使得Ki是Ki+1的双亲（1≤i≤n-1）。 （11）路径长度：从树根到树中每一结点的路径长度之和。

《树和二叉树》PPT课件
"树和二叉树"是计算机科学中重要的数据结构。本课件将详细介绍树和二叉树 的概念、存储结构、遍历方式、二叉搜索树、平衡树等内容。让我们一起探 索这个精彩领域吧！
概念介绍
树的定义及特点
树是由节点和边组成的非线性数据结构，具有分层结构和简洁性。
二叉树的定义及特点
二叉树是一种特殊的树，每个节点最多有两个子节点。
二叉搜索树是一种有序二叉树，左子树节点 都小于根节点，右子树节点都大于根节点。
2 插入和删除节点
通过比较节点值，插入或删除符合条件的节 点，保持二叉搜索树的有序性。
3 查找节点
通过比较节点值，快速定位目标节点。
4 遍历
二叉搜索树支持前序、中序和后序遍历。
平衡树
AVL树
AVL树是一种自平衡的二叉搜索树，通过旋转操作 保持树的平衡。
二叉树的遍历方式
1 先序遍历
先访问根节点，然后按先序遍历左子树，再 按先序遍历右子树。
2 中序遍历
先按中序遍历左子树，然后访问根节点，最 后按中序遍历右子树。
3 后序遍历
先按后序遍历左子树，然后按后序遍历右子 树，最后访问根节点。
4 层序遍历
按层级顺序逐层访问二叉树节点。
二叉搜索树
1 定义及性质
二叉树的分类
根据子节点的数量和排列方式，二叉树可分为满二叉树、完全二叉树和平衡二叉树。
树和二叉树的存储结构
双亲链表存储
使用数组存储节点，并在节点 中保存父节点信息。
孩子链表存储
使用链表存储节点，并在节点 中保存子节点信息。
孩子兄弟链表存储
使用链表存储节点，并在节点 中保存第一个孩子节点和下一 个兄弟节点的信息。

有两归个纳孩基子：结点i =，1则层每时一，层只均有比一上个一根层结的点结，点个数多一
倍。
2i-1 = 20 = 1；
归纳假设：假设对所有的 j，1≤ j i，命题成立;
按照归等纳比证数明列：的二定叉义树，上每每一个项结都点可至以多看有作两是棵相子应树每，一则层第
上的结点个数，i 则层，的a结i=点ai*数qi-1=22i-1i-2 2 = 2i-1 。
Dl，Dr
(3)若Dl ， Dr都不为空集，则Dl ， Dr本身又是一棵符 合
本定义的二叉树，称为根root的左右子树。
基本操作P：(见教材)
17
} ADT BinaryTree
二叉树的5种基本形态
二叉树的定义
A
A
A
A
B
B
BC
(a)
(b)
(c)
(d)
(e)
空二叉树
根和空的 根和左子树 根和右子树 左右子树
线性表和广义表 栈和队列 数组和广义表
树
……
线性表 广义表
栈
队列 ……
8
树的定义
树的定义
树是由n (n 0)个结点组成的有限集合。 如果n = 0，称为空树； 如果n > 0，则:
有一个特定的称之为根(root)的结点，它只有后继，但没有前
驱；
除根以外的其它结点划分为m(m>0)个互不相交的有限集合T1, T2, …, Tm。
10
树的定义
抽象数据类型树的定义
ADT Tree { 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 否则: (1) 在D中存在唯一的称为根的数据元素root, (2) 当n>1时，其余结点可分为m (m>0)个互

限集T1,T2,…,Tm,其中Ti是一棵树，称为根结点子树 例:(a)是只有一个根结点的树.(b)是有13个结点的树，A
是根，其余结点分成三个互不相交的子集： T1=(B,E,F,K,L);T2=(C,G);T3=(D,H,I,J,M).T1,T2,T都 是根A的子树，本身也是一棵树
A
A
T1
(a)只有根结
DeleteChild(&T,&P,i); 初始条件：树T存在,p指向T中某个结点，1<=i<=P指结点
的度 操作结果：删除T中P所指结点的第i棵子树
TraverseTree(T,Visit()); 初始条件：树T存在,Visit是对结点操作的应用函数 操作结果：按某种次序树对T的每个结点调用函数visit()一
二叉树的基本操作
InitBiTree(&T); 操作结果：构造空二叉树T
DestroyBiTree(&T); 初始条件：二叉树T存在 操作结果：销毁二叉树T
CreatBiTree(&T,definition); 初始条件：definition给出二叉树T的定义 操作结果：按definition树构造二叉树T
例下图，D是A的子树T3的根，则D是A的孩子， 而A则是D的双亲，同一个双亲的孩子之间互称兄弟。 结点的层次从根开始定义起，根为第一层，根的孩子为第二层。
A
T1 B
C T2
T3 D
EFGຫໍສະໝຸດ HIJK
L
M
有序树：将树中结点的各子树看成从左到右是有 次序的（不能互换），称该树为有序树。
无序树：将树中结点的各子树看成从左到右是无 次序的（不能互换），称该树为无序树。
树的基本操作
基本操作P: InitTree(&T); 操作结果：构造空树T

由于这些分支都是由度为1和2的结点射出的，所有有： B＝n1+2*n2 N＝B＋1＝n1＋2×n2＋1 （6－2) 由式（6－1）和（6－2）得到： n0+n1+n2=n1+2*n2+1 n0＝n2＋1 下面介绍两种特殊形态的二叉树：满二叉树和完全二 叉树。 一棵深度为k且由2k-1个结点的二叉树称为满二叉树。 图6.9就是一棵满二叉树，对结点进行了顺序编号。
6.2.3 二叉树的存储结构
1.顺序存储结构 它是用一组连续的存储单元存储二叉树的数 据元素。因此，必须把二叉树的所有结点安排成 为一个恰当的序列，结点在这个序列中的相互位 置能反映出结点之间的逻辑关系，用编号的方法： #define max-tree-size 100 Typedef telemtype sqbitree[max-tree-size]; Sqbitree bt 从树根起，自上层至下层，每层自左至右的 给所有结点编号缺点是有可能对存储空间造成极 大的浪费，在最坏的情况下，一个深度为H且只 有H个结点的右单支树确需要2h-1个结点存储空 间。而且，若经常需要插入与删除树中结点时， 顺序存储方式不是很好！
按后序遍历,其后序序列为： abcd-*+ef/b 人喜欢中缀形式的算术 表达式,对于计算机,使 c d 用后缀易于求值 图 （1）
a * e
/
f
TREENODE *creat_tree() { TREENODE *t; char c; c=getchar(); if(c= =„#‟) return(NULL); else{ t=(TREENODE *)malloc(sizeof(TREENODE)) t – >data=c; t –>lchild=create_tree(); t –>rchild=create –tree(); } return(t); }