c语言数据结构 递归创建二叉树的函数如何输入退出？这个函数一直让输入 无论输入什么 都无法结束输入
递归创建二叉树的输入是有讲究的，可参考：网页链接中最后的输入示例：如果你用#作为结束，则对应输入：1 2 4 # 6 ###3 #5 #7 #8 ##
再给个递归创建二叉树的例子：
#include <stdio.h>
#include <stdlib.h>
typedef struct Tree {
int Val;
struct Tree* left;
struct Tree* right;
}Tree;
Tree * CreateBiTree(void)
{
Tree * T;
int val;
scanf("%d", &val);
if(val == 0)
T = NULL;
else
{
T = (Tree *)malloc(sizeof(Tree));
T -> Val = val;
T -> left = CreateBiTree();
T -> right = CreateBiTree();
}
return T;
}
void Print(Tree* root)
{
if (root != NULL)
{
Print(root->left);
printf("%d ", root->Val);
Print(root->right);
}
}
int main()
{
Tree* root = CreateBiTree();
Print(root);
return 0;
}
以上面的输入例子1 2 4 # 6 ###3 #5 #7 #8 ##为例，对应的输入为：1 2 3 0 6 0 0 0 3 0 5 0 7 0 8 0 0
运行结果：
当然也可以这样：
#include <stdio.h>
#include <stdlib.h>
typedef struct Tree {
int Val;
struct Tree* left;
struct Tree* right;
}Tree;
void CreateBiTree(Tree**T)
{
int val;
scanf("%d", &val);
if(val == 0)
*T = NULL;
else
{
*T = (Tree *)malloc(sizeof(Tree));
(*T)->Val = val;
CreateBiTree(&(*T)->left);
CreateBiTree(&(*T)->right);
}
}
void Print(Tree* root)
{
if (root != NULL)
{
Print(root->left);
printf("%d ", root->Val);
Print(root->right);
}
}
int main()
{
Tree* root;
CreateBiTree(&root);
Print(root);
return 0;
}
这里的输入示例为：1 2 4 0 6 0 0 0 7 0 0 0
运行结果：
C++ 版：
#include <iostream>
using namespace std;
typedef struct Tree {
int Val;
struct Tree* left;
struct Tree* right;
}Tree;
void CreateBiTree(Tree* & T)
{
int val;
cin >> val;
if(val == 0)
T = NULL;
else
{
T = new Tree;
T->Val = val;
CreateBiTree(T->left);
CreateBiTree(T->right);
}
}
void Print(Tree*root)
{
if (root != NULL)
{
Print(root->left);
cout << root->Val << ' ';
Print(root->right);
}
}
int main()
{
Tree* root;
CreateBiTree(root);
Print(root);
return 0;
}
看了一下你的递归部分的代码，是正确的，没问题。
您好 感谢您细致的回答 非常感谢~
这几天有事一直没看 一定要采纳啊 谢谢你
就是请问一下 为什么输入是隔几个数字就要输入一个或者几个#号呢？
不客气！
通过代码理解可知道，隔几个有效输入再输入一个#号可改变插入节点的为其父节点的右孩子(这里注意T->left在T->right前面，反之则为左孩子)，所以前面的输入如果不用#号结束输入，则会一直在往左子树中进行递归插入。当当前递归中接收到一个#时，T->left递归结束(此时的递归深度为左子树中节点个数)并在该层中进入到T->right的递归中，则之后插入的节点总是在前面递归结束时的节点的右子树中。当多次输入#号时，则后续的节点插入位置不断的往根的方向上升，直到#号的输入个数等于从根到当前节点深度时则输入全部结束。但注意，这种方式创建的二叉树不满足二叉树的条件，我们知道二叉树的条件是左孩子的值小于其父节点值，右孩子值大于其父节点值，但递归创建的二叉树却不一定满足这个条件，所以可以看到用中序遍历输出的结果并没有按由小到大的顺序排列出来。可能我讲得有些复杂，目前没想到更好的解释，有些抱歉！但多看代码理解和结合前面给出的链接中的最后输入示例部分(有对应的输入构造图)，应该就能明白了！
ps：感觉还是用实例说明更好。假如我们要按顺序插入[1 2 3 4 5 6 7] 并构造出一颗满二叉树形态的树，则应该这样(>>代表输入)：
>>1 --> 根节点
>>2 --> 1的左孩子
>>3 --> 2的左孩子
>># --> 退出当前T->l的递归 后面还有T->r
>># --> 退出T->r 后面没有代码 退回到前层递归 即节点值2那层
>>4 --> 2的右孩子
>># --> 退出当前T->l的递归 后面还有T->r
>># --> 退出T->r 后面没有代码 退回到前层递归 即节点值1 也就是根的节点那层中
>>5 --> 1的右孩子
>>6 --> 5的左孩子
>># --> 退出该层T->l 后面还有代码T->r
>># --> 退出T->r 后面没有代码 退回到前层递归 即节点值5那层
>>7 --> 5的右孩子
>># --> 退出T->r 后面没有代码 退回到前层递归 即节点值5那层
>># --> 退回前层 即根节点
输入结束，退出函数。
打印结果：
1
↙ ↘
2 5
↙ ↘ ↙ ↘
3 4 6 7
中序遍历:3 2 4 1 6 5 7
重点即要理解递归过程！
