第七章 二叉树及其应用.ppt

文档介绍：☞ 二叉树的概念
二叉树的存储
二叉树的遍历
线索二叉树
二叉树的应用1—基本算法
二叉树的应用2—哈夫曼树
二叉树的应用3—二叉排序树
二叉树的应用3—堆和堆排序
第7章二叉树及其应用
☞ 什么是二叉树
特殊的二叉树
二叉树的性质
二叉树的概念
二叉树的定义
二叉树是由n(n≥0)个结点组成的有限集合,其中:
①当n=0时为空树;
②当n>0时,有且仅有一个特定的结点,称为二叉树的根,其余结点可分为2个互不相交的子集,其中每一个子集本身又是一棵二叉树,分别称为左子树和右子树。
A
B
C
D
E
F
G
H
I
J
二叉树的形态
空树
单结点二叉树
A
Ø
右子树不空的二叉树
Ø
左子树不空的二叉树
左右子树均不空的二叉树
二叉树的基本术语:
父结点:若一个结点有子树,则该结点为父结点(也称
双亲结点)。
孩子结点:若某结点有左子树,则其左子树的根为该结点的左孩子;若其有右子树,则其右子树的根为该结点的右孩子。
A
B
C
D
E
F
G
H
I
J
结点A为结点B、C的父结点
B为A的左孩子,
C是A的右孩子;
兄弟结点:同一个结点的孩子。
延伸父子关系可得到祖先结点和后代结点关系。
层次:根结点的层次为1,其余结点的层次是其父结点
的层次加1。
高度(深度):二叉树中结点的最大层次数。
A
B
C
D
E
F
G
H
I
J
该二叉树的深度为4;
度:一个结点的孩子数目是这个结点的度。
叶子结点:度为0的结点。
二叉树的度:二叉树中结点的最大的度。
A
B
C
D
E
F
G
H
I
J
A、B、C的度均为2;
E、F、G的度均为1;
D、H、I、J的度为0.
注意:对于结点数>1的二叉树,有且仅有一个结点为二叉树的根,其余结点均为孩子结点,且有左右之分——左孩子、右孩子。
例:具有三个结点的二叉树
A
B
C
B
A
C
A
B
C
A
B
C
C
A
B
总结:二叉树的逻辑结构
(1)二叉树中任一结点(除根结点外)只有一个父结点;
(2)二叉树中任一结点(除叶子结点外)最多有2个孩子结点;
(3)结点间为非线性关系。
什么是二叉树
☞ 两种特殊的二叉树
二叉树的性质
二叉树的概念