用C++语言编写数据结构树的问题

Question

核心：二叉树的顺序存储结构

题目：已知用户将一棵完全二叉树的n个结点（数据类型是整型）以自顶向下、从左到右顺序输入到一个一维数组中：
(1)编写算法 FindRelation (int i) 输出下标为 i 的结点的父结点和所有子女结点（如果有的话).

(2)打印这棵二叉树的所有节点：先打印二叉树的根、再打印左子
树、最后打印右子树.

要求:
(1)二叉树的结点数据需要用户输入，用户先输入有多少个结点，然后输入各个结点的数据，用-1表示某结点为空。
(2)主要函数需要给出完整注释。
(3)调试平台VC6.0。
用负一表示某结点为空

Answer 1

#include"stdio.h"
int n,tree[100];
void creat()//创建二叉树
{
int i=0,j;
for(i=0;i<100;i++)
tree[i]=-1;
printf("input the num of nodes\n");
scanf("%d",&n);//输入节点个数（包括空节点）
tree[0]=j=n;
printf("input the value of nodes(the null node is -1)\n");
i=0;
while(j--)//循环输入节点值
{
i++;
scanf("%d",&tree[i]);
}
}

int findreational(int i)//找第i节点的父节点、孩子节点
{
if(i<=0||i>n)
{
printf("\n下标越界\n");
return 0;
}
if(tree[i/2]==-1)//父节点
printf("没有父节点\n");
else printf("父节点：%d\n",tree[i/2]);

if(tree[2*i]==-1)//左孩子节点
printf("没有左孩子\n");
else printf("左孩子：%d\n",tree[2*i]);

if(tree[2*i+1]==-1)//右孩子节点
printf("没有右孩子\n");
else printf("右孩子：%d\n",tree[2*i+1]);
return 1;

}

int preorderprint(int i)//按先根输出，也就是先序排列
{
if(tree[i]!=-1)
printf("%d ",tree[i]);
else return 0;
preorderprint(i*2);//递归
preorderprint(i*2+1);

}

int main()
{
int i;
creat();
printf("input you the i:\n");
scanf("%d",&i);
findreational(i);
printf("\n先序排列：\n");
preorderprint(1);
printf("\n");
return 1;
}

Answer 2

写好了,我考虑的问题比较细,所以代码有点长
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>

/* The MAXSIZE number of node */
#define MAXSIZE 100
/* Save the content of node */
int Tree[MAXSIZE];
/* The number of node */
int number = 0;

void Initialize(int *);
void FindRelation (int *, int i);
void Display(int *);

void main()
{
/* The result of read from key buffer */
int iReadRlt = 0;
/* The suffix of node to search */
int search = 0;

/* Initialization */
memset(Tree, 0, MAXSIZE*sizeof(int));

/* Prompt user to input the number of node */
printf("请输入结点个数: ");
iReadRlt = scanf("%d", &number);

/* The input isn't a number or is illeagle */
while (0 >= iReadRlt || number < 0 || number > MAXSIZE)
{
/* Clear the key buffer */
while (10 != getchar())
{
continue;
}
printf("\n错误,请输入一个1-%d的数字: ", MAXSIZE);
iReadRlt = scanf("%d", &number);
}

/* Clear the key buffer */
while (10 != getchar())
{
continue;
}

/* Initialize the tree */
Initialize(Tree);

/* Prompt user to input the node */
printf("\n请输入你要查找的结点: ");
iReadRlt = scanf("%d", &search);

/* The input isn't a number */
while (0 >= iReadRlt)
{
/* Clear the key buffer */
while (10 != getchar())
{
continue;
}
printf("\n错误,请输入一个数字: ");
iReadRlt = scanf("%d", &search);
}

/* Clear the key buffer */
while (10 != getchar())
{
continue;
}

/* Display the node's parent and children */
FindRelation(Tree, search);

/* Display all the nodes of the tree */
printf("按前序遍历的顺序显示树的内容:\n\n");
Display(Tree+1);
printf("\n\n");
}

/* This function is to initialize the tree */
void Initialize(int * tree)
{
/* The counter of loop */
int count = 1;
/* The result of read form key buffer */
int iReadRlt = 0;
/* The first node don't save data */
tree[0] = -1;

for (; count <= number; count++)
{
/* Prompt user to input the content of node */
printf("\n请输入结点%d的内容: ",count);
iReadRlt = scanf("%d", &tree[count]);

/* The input isn't a number */
while (0 >= iReadRlt)
{
/* Clear the key buffer */
while (10 != getchar())
{
continue;
}
printf("\n错误,请输入一个数字: ");
iReadRlt = scanf("%d", &Tree[count]);
}

/* Clear the key buffer */
while (10 != getchar())
{
continue;
}
}
for (; count < MAXSIZE; count++)
{
tree[count] = -1;
}
}

/* This function is to get the parents and son nodes */
void FindRelation (int * tree, int i)
{
/* The node isn't exist */
if (i < 1 || i > number)
{
printf("\n该结点不存在!\n\n");
return;
}

/* The node is root */
if (1 == i)
{
printf("\n该结点是根结点,没有父结点.\n\n");
}
else
{
printf("\n该结点的父结点是: %d\n\n", tree[i/2]);
}

/* The node don't have child */
if (i+i > number)
{
printf("该结点没有子结点!\n\n");
}
else if (i+i+1 > number)
{
printf("该结点只有一个子结点: %d\n\n", tree[i+i]);
}
else
{
printf("该结点的子结点: %d, %d\n\n", tree[i+i], tree[i+i+1]);
}
}

void Display(int * root)
{
int suffix = 0;
/* The node is empty */
if (root > Tree+number)
{
return;
}

/* Display the root node */
printf("%d ", root[0]);

suffix = root - Tree;
/* Display the left subtree */
Display(Tree+suffix+suffix);

/* Display the right subtree */
Display(Tree+suffix+suffix+1);
}