C语言 数据结构 二叉树实现的疑问

Question

用递归方法先创建树根结点，然后分别创建左、右子树。在创建二叉树时，其结点数据的输入预先不确定，有键盘输入二叉树结点个数，然后再输入一个相应长度的字符串，将这个字符串临保存在字符串str中，最后再从字符串中去除数据，并分配给需要创建的二叉树结点。
#include<stdio.h>;
#include<string.h>
# define MAX 100
# define NULL 0
char *p;

typedef struct BiTNods{
char data;
struct BiTNods *lchild,*rchild;
}BiTNods,*BiTree;

void CreateTree(BiTree BTree)
{
(*BTree).data=*p;
if(*(p++)!=' '){
(*BTree).lchild=(BiTNods*)malloc(sizeof(BiTNods));
CreateTree((*BTree).lchild);
}
else
(*BTree).lchild=NULL;
if(*(p++)!=' '){
(*BTree).rchild=(BiTNods*)malloc(sizeof(BiTNods));
CreateTree((*BTree).rchild);
}
else
(*BTree).rchild=NULL;
}

void Preorder(BiTree T){
if(T){
printf("%d\t",(*T).data);
Preorder((*T).lchild);
Preorder((*T).rchild);
}
}

void main(){
char bt[MAX];
p=bt;
BiTree BTree;
printf("please input string:\n");
gets(bt);

if(bt==' '){
pirntf("NO element in the tree!");
}
else{
BTree=(BiTNods*)malloc(sizeof(BiTNods));
CreateTree(BTree);
}
Preorder(BTree);
getch();

}
我的算法思想是通过指针遍历字符串str,将非空格的元素由先序遍历方法存储进二叉树里面.请帮帮我

Answer 1

C语言 数据结构 二叉树实现的疑问
先敬仰一下楼主的勤奋！

我主要针对第二个算法说，我觉得上面这段话也是在讲第二个算法。其实两个算法差不太多。
1. 栈顶记录中的指针其实就是指栈顶，每次push()进去或者pop()出来的那个p。他代表的是正在访问的节点得下一个节点。比如，访问一个树t的左子树t->lchild时，栈顶就是t；访问t->lchild->lchild时，栈顶就是t->lchild。访问t->rchild时，栈顶为NULL；访问t->lchild->rchild时，栈顶为t；访问t->rchild->lchild时，栈顶也是t；访问t->rchild->rcchild时，栈顶仍为NULL。他的意义就是，在访问完了当前的子树之后，就会去访问栈顶记录的指针对应的节点的数据。
2. 关于“工作记录”那个词，我觉得还是别深究了。那段话意思是要仿照编译器把递归编译成迭代的思路来自己写迭代算法，可是实际上后面给出的算法里根本没有严格执行上述思路，写出来的算法并不是严格意义上的可以一般性替换递归的迭代算法。所以追究那个词也没意义，明白迭代遍历的算法怎么用就够了。等以后对递归有了更深刻的认识，自然就明白了。其实就是函数递归调用自身之前像中断那样保存自己的工作环境和进度。
3. （2）句并不矛盾。他说“指针为空时”和“指针指向的xxx”中间不是有句“退回上一层”么，那就表示pop()，于是原来那个在栈顶的空指针弹出去了，原来在第二位的指针现在到了栈顶。于是后面那句指的是对这个指针进行操作。

快购吧，时尚女人，时尚女装，乐蜂网时尚女装

Answer 2

首先敬仰一下楼主的勤奋！

我主要针对第二个算法说，我觉得上面这段话也是在讲第二个算法。其实两个算法差不太多。
1. 栈顶记录中的指针其实就是指栈顶，每次push()进去或者pop()出来的那个p。他代表的是正在访问的节点得下一个节点。比如，访问一个树t的左子树t->lchild时，栈顶就是t；访问t->lchild->lchild时，栈顶就是t->lchild。访问t->rchild时，栈顶为NULL；访问t->lchild->rchild时，栈顶为t；访问t->rchild->lchild时，栈顶也是t；访问t->rchild->rcchild时，栈顶仍为NULL。他的意义就是，在访问完了当前的子树之后，就会去访问栈顶记录的指针对应的节点的数据。
2. 关于“工作记录”那个词，我觉得还是别深究了。那段话意思是要仿照编译器把递归编译成迭代的思路来自己写迭代算法，可是实际上后面给出的算法里根本没有严格执行上述思路，写出来的算法并不是严格意义上的可以一般性替换递归的迭代算法。所以追究那个词也没意义，明白迭代遍历的算法怎么用就够了。等以后对递归有了更深刻的认识，自然就明白了。其实就是函数递归调用自身之前像中断那样保存自己的工作环境和进度。
3. （2）句并不矛盾。他说“指针为空时”和“指针指向的xxx”中间不是有句“退回上一层”么，那就表示pop()，于是原来那个在栈顶的空指针弹出去了，原来在第二位的指针现在到了栈顶。于是后面那句指的是对这个指针进行操作。
另外,虚机团上产品团购,超级便宜

Answer 3

#include<stdio.h>;

# define MAX 100
# define NULL 0

struct tree{
char info;
struct tree *left;
struct tree *right;
};

struct tree *ctree(struct tree *root,struct tree *r,char info)
{
if(!r){
r=(struct tree*)malloc(sizeof(struct tree));
if(!r){
printf("there is no memory\n");
exit(0);
}
r->left=NULL;
r->right=NULL;
r->info=info;
if(!root)return r;
if(info < root->info) root->left = r;
else root->right = r;
return r;
}
if(info < r->info)
ctree(r,r->left,info);
else
ctree(r,r->right,info);
return root;
}

void stree(struct tree *r)
{
if(r){
printf("%c\t",r->info);
stree(r->left);
stree(r->right);
}
}

main(){
char str[MAX]={0};
char *p=str;
struct tree *rt=NULL;
printf("please input string:\n");
gets(str);
while(*p)rt=ctree(rt,rt,*p++);
stree(rt);
}来自：求助得到的回答本回答被提问者采纳

Answer 4

随便看了下 说错了莫怪
1.if(*(p++)!=' '){ 你应该是想指向下一个字符 然后判断下一个字符是不是为空吧 不过这好像指向的是原来字符 是不是要改成if(*(++p)!=' ') 啊
2. 感觉你的方法是用空格来判断是否变换树的路径 但是如果要建立一个完整树的话 它要求的空格非常多 比如说二叉树
a
b c
d e f g
那么要建立一个这样的结构的话 需要的字符串应该是是abd e cf g 才7个元素就需要6个空格 感觉很不合理 不过貌似也没什么办法 因为需要在字符串存储是否变换方向的信息 呵呵 你自己考虑吧