二叉树的生成(一) 层次遍历序列
由层次遍历的字符串序列生成对应的二叉树,其中数据均为个位的正整数,以#表示空。
如:
输入“1234567#8####9#####”
输出
分析:
第一步是根据序列生成一个二叉树节点的数组,装入每个节点的数据
第二步是循环,手动模拟一下生成树的过程,不难发现只要使用两个下标this_pos和son_pos就可以把数组中各个节点的子节点依次加入。
规律:this_node进行循环,每次+1,若当前位置是空,那么对应的son_pos的位置不变。否则son_pos是this_node的左子,son_pos+1是这个位置的右子,录入以后son_pos+=2;
用例:
1234567#8####9#####
1234567########
73914#####5#6##
代码
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
biTree* initBiTree(char* data);
struct biTree
{
int data;
biTree* leftSon;
biTree* rightSon;
};
biTree* initBiTree(char* data)
{
if(NULL == data)
return NULL;
int i = 0;
//生成 数组(树)
for(i;data[i]!='\0';i++);
biTree* arry_tree = (biTree*) malloc (sizeof(biTree) * i); //c语言中的数组和头指针
for(i=0;data[i]!='\0';i++)
{
if(data[i] == '#')
arry_tree[i].data = 0;
else
arry_tree[i].data = data[i] - '0';
}
//操作指针添加关系
int son_pos = 1;
int this_pos = 0;
for(this_pos=0,son_pos=1;son_pos<i;this_pos++,son_pos +=2 )
{
if(arry_tree[this_pos].data == 0)
{
son_pos -= 2;
}
if(arry_tree[son_pos].data != 0)
arry_tree[this_pos].leftSon = &(arry_tree[son_pos]);
else
arry_tree[this_pos].leftSon = NULL;
if(arry_tree[son_pos+1].data != 0)
arry_tree[this_pos].rightSon =&(arry_tree[son_pos+1]);
else
arry_tree[this_pos].rightSon = NULL;
}
return &(arry_tree[0]);
}