Question

C语言递归创建二叉树 不能得到正确结果

以下为该递归创建二叉树的C代码，但是我输入相应的数据时，虽然能运行成功，但就是结果不对，并且它还无故多出了很多循环，好像是在递归创建结点的时候创建的，这时对递归过程不知道是怎么执行的，单步也没有调试出原因，就是不能得到正确结果，我也参照过其他的递归代码，感觉也没有错啊（本人是在VC++6.0上调试的）。代码不多，但是问题还没有解决，请各位帮忙看哈，小弟先谢谢了！

#include <stdio.h>
#include <malloc.h>
#include <process.h>

#define OK 0
#define NULL 0
#define OVERFLOW 0
typedef int TElemType ;
typedef int Status ;

typedef struct BinaryTree
{
TElemType data;
BinaryTree *left;
BinaryTree *right;
}BinaryTree,*BTree;

Status CreatBinaryTree(BinaryTree *T)
{

TElemType dt;
scanf("%d",&dt);
if(dt==100) T=NULL;
else
{
if(!(T=(BinaryTree *)malloc(sizeof(BinaryTree))))
exit(OVERFLOW);
T->data=dt;
printf("你输入的数为：%d\n",T->data);
CreatBinaryTree(T->left);
CreatBinaryTree(T->right);

}
return OK;
}

int main()
{
BinaryTree *T;
T=(BinaryTree *)malloc(sizeof(BinaryTree));
CreatBinaryTree(T);
return OK;
}

Answer 1

问题出在：每建立一个节点都是放在新建立的父节点下面的，你根本没有返回最新的节点，试问你这些新建节点挂在何处？程序改好了：
你输入树的时候应该按照先序进行输入 （这里你用的100代替#）
如这个树：
a
/ \
b #
/ \
# #
应该输入：ab###

二楼的答的不太对吧,你的树应该为：
a
/ \
b c
/ \ / \
# # # #
如果是那样的树应该输入：
ab##c##

我知道你的意思，你递归是分成好几路的，对于这样的递归如果把过程画出来就是一棵树，而递归的结束是需要在最后的每个叶结点结束，而你这个递归的一个结束点就是输入‘#’，但你如果随便输入几个‘#’就不一定在该结束的地方结束，当然如果你输入树不复杂的话就输入一串#################，基本会把该结束的递归结束的，（当然最好你自己画一个二叉树按照你的要求画出来，不然没有意思，这样该输入几个#你就可以确定了。）好好看看递归的过程。

#include <stdio.h>
#include <malloc.h>
#include <process.h>

#define OK 0
#define NULL 0
#define OVERFLOW 0
typedef int TElemType ;
typedef int Status ;

typedef struct BinaryTree
{
TElemType data;
BinaryTree *left;
BinaryTree *right;
}BinaryTree,*BTree;

BTree CreatBinaryTree()
{

TElemType dt;
printf("请输入节点数据：(输入多个100结束)");
scanf("%d",&dt);
BTree current;
if(dt==100) current=NULL;
else
{
if(!(current=(BinaryTree *)malloc(sizeof(BinaryTree))))
exit(OVERFLOW);
current->data=dt;
printf("你输入的数为：%d\n",current->data);
current->left = CreatBinaryTree();
current->right = CreatBinaryTree();

}
return current;
}
void inorder(BTree p)
{
if(p != NULL)
{
printf("%d\n",p->data);
inorder(p->left);
inorder(p->right);
}
}

int main()
{
BTree root;
root = CreatBinaryTree();
printf("先序遍历二叉树：\n");
inorder(root);
return OK;
}

Answer 2

我这没VC 只是粗看了你的代码 貌似构思上没问题 写的也正确

理论上应该是 程序一运行 输入根节点的数据 并输出显示

然后开始不断的添加左节点 每输入一个数据 就在上一层的基础上在添加一个左节点

直到你输入100 这时的最下层节点设为A 它没有左孩子节点

再输入100 说明A没孩子节点 给一个数据 则给最下面一层的那个左节点A加上了一个兄弟右节点B

然后 如果输入数据 则给B不断地一层一层加左节点 同上
如果输入100 则B没有左节点----在次情况下在输入100，则B没有孩子节点，这时才向上返回一层 继续对A B 的父节点的兄弟节点进行操作

如此循环 构建二叉树的方式是最左深度优先遍历