文档介绍：第七章基础树状结构
树状结构是一个或多个节点所构成之有限集合。
每一棵树必有一特定的节点,称作根节点
(root),根节点之下可以有零个以上的子节点
(可以没有),而各子节点也可为子树,拥有自
己的子节点。
(1)根节点
棵树中没有父节点的节点,称为根节点。
(2)叶节点或终端节点
棵树中没有子节点的节点,称为叶节点
(3)非终端节点
除了叶节点以外的其他节点,称为非终端节点。
(4)父节点和子节点
若节点x有一个以y为树根的子树,则x为y的父节点
而y为x的子节点
(5)兄弟
同一个父节点之节点,称为兄弟。
(6)分支度
每个节点所拥有的子节点个数。而一棵树中最大的分
支度值,即为该树的分支度。
(7)阶层
阶层为节点之特性值,将根节点之阶层设为1,其子
节点为2,以此类推。
(8)高度或深度
棵树中的最大阶层值,称为树的高度或深度
(9)祖先
由某节点x到根节点之路径上的所有节点,均称为x之
祖先。
(10)树林
0棵以上的树的集合称为树林。若将一棵树的根节点
移去,所剩就是一树林。
721何谓二叉树
二叉树是树的一种,二叉树中树的节点最多只有两个子节
点
二叉树的定义如下
(1)由有限个节点所构成之集合,此集合可以为空的。
(2)二又树的根节点下可分成两个子树,称为左子树和右子树,
左子树和右子树亦称二叉树。
722二叉树和树的比较
(1)二又树可为空,而树不可以(至少要有根节点)
(2)二又树的子树有顺序关系,而树没有
(3)二又树的分支度必为0、1、2,而树的分支度可大于2
(1)歪斜树
在一棵树中,若所有节点的左分支均不存在,则此树为右歪斜树,
反之,所有节点的右分支均不存在,则此树为左歪斜树。
(2)满二叉树
棵树中所有叶节点均在同一阶层,而其他非终端节点之分支度
均为2,则此树为一满二叉树。
(3)完全二叉树
棵树除掉最大阶层那层后为一满二叉树,而阶层最大那层的节
点均向左靠齐,则该二叉树称为完全二叉树。
(4)二又树中的第层,最多有2-1个节点
(5)高度为h的二叉树,最多有2h-1个节点
(6)对任一个非空的二叉树而言,若分支度为i的节点有n2个,则
二叉树节点的标识法,常用的有下列3种方法
(1)二叉树数组表示法
(2)二叉树结构数组表示法
(3)二叉树链表表示法
其中“数组表示法”和“结构数组表示法”是属
于静态内存空间分配,而“链表表示法”是利用
列表结构的方式,属于动态内存分配。
731二叉树数组表示法
总体思路
二叉树中,可对各阶层的节点由低阶层到高阶
层,由左到右,从1开始依序编号,再根据编
号存入相对应索引编号之数组中。若该数组不
为满二叉树,也可对各节点编成在满二叉树中
相同位置之节点编号值。
程序实例:
依序输入元素值,以数组方式建立二叉树,并输出节点内容。
#inc lude iostream. h>
void create btree (int *b tree, int *nodelist, int len
int 1
int level
b tree [1]=nodelist[1
for(i=2: i<=len; i++)
level=1
while(b tree llevell! =0)
if (nodelist[i]<b tree[level])
evel=level=2
level=level*2+1
b tree[level]=nodelist[i]
int i, inde
int data
int b tree[16
int nodelist[16
cout <<endl<< Please input the eler
f binary tree(Exit for 0): <<endl
index=1
cin>>dat
while(data!=0)
nodelist Lindex]=data
index-index+1
cln
for (i=index i<16 i++)
nodelist li]=o
for(i=1;i<16:i+)
b trees=0
create btree(b tree, nodelist, index)
cout<end] the binary tree is:<<end1
for(i=1;i<16;i++)
cout<<i<<:[<<b tree[