【算法练习七】顺序储存二叉树

树与二叉树:

什么是树呢?就是一个节点上会有很多分叉的数据结构。一般的,对于一棵树,我们需要的结构体为一个数据块和几个指针块,这就相当于很多个链表交织在了一起,实际上,链表也可以算是一种特殊的树,而我要讲的,也是一种特殊的树——二叉树。

对于树的各个节点,都有两个属性,称为度(degree),他的意思就是这个节点所拥有的子节点的数量。还有一个属性,称为深度(depth),指节点到根的距离。

什么是二叉树呢?顾名思义,就是度为二的树,它长这样:

如图所示,在链表中我们需要头(head),而在树中我们就需要根(root),A就是这棵二叉树的根,根据二叉树的定义,每个节点指向两个节点,于是B,C被称为A的孩子(child),我们称为子节点,A就是他们的父母(parent),可以称为父节点。因为DEFG后面不再有其他节点,所以我们称他们为叶节点(leaf)。

关于二叉树的其他概念:

一、斜树:就是斜着长的树,比如上图中只留下ABD或者ACG的话就是斜树了。

二、满二叉树:如果所有的节点都存在左子树和又子树,并且所有的叶的深度都相同,那么这个树被称为满二叉树。

三、完全二叉树:我们对二叉树进行编号,比如上图,编为A(1)B(2)C(3)D(4)E(5)F(6)G(7),可以发现,这棵树一共有7个节点(记为n),但是我们如果删除G,那么是6个节点,对于新的这棵树进行遍历,和当它满的时候各点的编号一样,则它是完全二叉树。但是如果拿掉的是F,那么就不是完全二叉树。满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。

二叉树的性质:

为什么说二叉树特殊呢?因为它有如下的性质:

一、在二叉树的第i层至多有2i-1个节点。

二、深度为k的二叉树最多有2k-1个节点。(注意与第一点的区别,一个是指数为i-1,一个指数为k但整体-1)

三、具有n个节点的完全二叉树的深度为[(log2n)]+1.[]表示取整.

四、对于任意一个编号为n的节点,如果它有子节点,它的左子节点编号为2n,右节点的编号为2n+1。(这条性质很重要,决定了二叉树可以用数组来表示)。

二叉树的遍历:

二叉树主要有三种遍历方法。

1、先序遍历:优先遍历根,然后优先遍历左节点。图中的二叉树先序遍历后的结果为ABDECFG

2、后序遍历:优先访问最底层的左节点,图中的二叉树后序遍历后的结果为DEBFGCA

3、中序遍历:先访问最下层的叶,并且由左子树到父节点到右子树的顺序遍历,图中二叉树中序遍历后的结果为DBEFCGA

二叉树的顺序存储方法:

对于图中的树,它的编号是这样的:A(1)B(2)C(3)D(4)E(5)F(6)G(7),利用性质四,就可以很轻松的建立一棵顺序二叉树。

我们可以把数组中的第一个位置舍弃,因为不方便。我们来看一下如何进行先序输入吧:

void get_tree(char *tree,int sub){
char t;
scanf(“%c”,&t);
tree[sub]=t;
if(t==’#’)
return;
get_tree(tree,2*sub);
get_tree(tree,2*sub+1);
}

输入#号表示该节点为空,不然的话,永远都输入不完啦!

那么先序输出也就简单了:

void print_tree(char *tree,int sub){
if(tree[sub]==’#’)
return;
printf(“%c”,tree[sub]);
print_tree(tree,2*sub);
print_tree(tree,2*sub+1);
}

代码很简洁方便,而且想要某个点的深度只要取该点下标,利用性质三就行了。由于math.h库里面没有log以2为底的函数,所以需要用到换底公式来操作,我就不再多说了。

总体的代码如下:

//二叉树的先序输入与输出
#include <stdio.h>
void get_tree(char*,int);
void print_tree(char*,int);
int main(){
char tree[1000];
get_tree(tree,1);
print_tree(tree,1);
return 0;
}
void get_tree(char *tree,int sub){
char t;
scanf(“%c”,&t);
tree[sub]=t;
if(t==’#’)
return;
get_tree(tree,2*sub);
get_tree(tree,2*sub+1);
}
void print_tree(char *tree,int sub){
if(tree[sub]==’#’)
return;
printf(“%c”,tree[sub]);
print_tree(tree,2*sub);
print_tree(tree,2*sub+1);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注