数据结构(JAVA版)-课件·PPT.ppt

数据结构(JAVA版)
烟台职业学院精品课
第7章树和二叉树
树
1
二叉树
2
二叉树的存储结构
3
树转换成二叉树
5
线索二叉树
6
二叉树的遍历
4
树
树的定义
树是由一个或多个结点构成的有限集合。每棵树必有一个称做根的结点。根结点可以有零个以上的子结点,而各子结点也可为子树。
树的有关术语
根结点(root) 一棵树中没有父结点的结点
叶结点或终端结点(leaf node)没有子结点的结点
非终端结点(nonterminal) 除了叶结点以外的其他结点
父结点(parent)和子结点(child) 若结点X有一个以结点Y为树根的子树,则X为Y的父结点,而Y就是X的子结点
兄弟(sibling) 同一个父结点的结点
分支度(degree) 每个结点的子结点数
高度(height)或深度(depth) 一棵树中最大层数
祖先(ancestor) 由结点X到根结点路径上所有的结点
森林(forest) n≥0个树的集合
二叉树
二叉树(Binary tree)的递归定义 二叉树是有n个结点组成的有限集合,n=0时为空二叉树;n>0时,二叉树是由有一个根结点和两棵互不相交的、分别称为左子树和右子树构成。二叉树有一种有序树。 两棵不同的二叉树:
二叉树的性质
二叉树的第I 层上最多有2i-1个结点
在深度为k的二叉树中,最大结点数为2k-1个结点
二叉树中,若叶子结点数为n0,度为2的结点数为n2,则有n0=n2+1
若一棵完全二叉树有有n个结点,则其深度为k=∟log2n」+1
一棵深度为k的满二叉树是具有2k-1个结点的二叉树。
对满二叉树进行编号,从根结点开始,自上而下,自左到右编号。若一棵具有n个结点深度为k的二叉树,若每个结点都与深度为k的满二叉树编号为1~n一一对应,则称此二叉树为完全二叉树。
若将一棵具有n个结点的完全二叉树,对于编号为i的结点,有如下特点:
若i=1,则i为根结点,无双亲;否则i结点的双亲编号为i/2的结点。
若2i≤n,则i的左孩子编号为2i,否则i无左孩子。
若2i+1≤n,则i的右孩子编号为2i+1,否则i无右孩子。
二叉树的存储结构
二叉树的顺序存储结构(适合于完全二叉树)
非完全二叉树的顺序存储结构如下图
二叉树的存储结构
二叉树的链式存储结构
二叉链式存储结构的每个结点包含三个域:
Root指向二叉树的根结点。若二叉树为空,则root=null。
在一棵有n个结点的链式存储的二叉树中,有n+1个空链域。
data
leftChild
rightChild
二叉树的存储结构
(1)不带头结点的二叉树;(2)带头结点的二叉树
A
B
C
D
E
F
G
∧
∧
∧
∧
∧
∧
∧
∧
(a)
A
B
C
D
E
F
G
∧
∧
∧
∧
∧
∧
∧
∧
(b)
root
root
∧
二叉树的存储结构
声明二叉树类
二叉树的结点类
Package ds_java;
Public class treenodel
{
Public string data;
Public treenode1 left,right;
Public treenode1()
{
This(“?”);
}
Public treenode1(string d)
{
Data=d;
Left=right=null;
}
}
二叉树的遍历
遍历二叉树就是按照一定的规则访问二叉树中所有的结点,并且每个结点仅被访问一次。所谓的访问,是指对每个结点数据进行查询、修改等操作。
若对子树的访问按“先左后右”的次序进行,则遍历二叉树有三种方法:
先根遍历:访问根结点,先根遍历左子树,先根遍历右子树。
中根遍历:中根遍历左子树,访问根结点,中根遍历右子树。
后根遍历:后根遍历左子树,后根遍历右子树,访问根结点。