[C++知识库]二叉树建立 遍历时出现的问题c

二叉树创建并遍历
代码如下

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct  btnode
	  {
struct btnode*lchild,*rchild;
int data;
	   }NODE;
main()
{
	NODE *root=(NODE*)malloc(sizeof(NODE)),*q,n;
	NODE *create(NODE *p);
	void preorder();
	void inorder();
	void postorder();
    int t;
	q=&n;
	root=create(q);
	
	printf("At  the first,we create   a tree\n");
	printf("Please input nodes of tree\n");
	if  (root==NULL)    printf("It's  an empty  tree!\n");
	else
	   {
		printf("\n1.The preordetraverse  \n");
	    printf("  2.The inordertraverse \n");
	    printf("  3.The postordertraverse \n");
		printf("  Please choose  a  kind  of  order\n");
		scanf("%d",&t);
		switch   (t)
		   {
			case 1: preorder(root);  break;
			case 2: inorder(root);   break;
			case 3:postorder(root);   break;
			default: printf(" The error!");
		   }
		}
}

NODE  * create(NODE *p)    /*create the structure of binary tree */
 {
 char ch;
	
    scanf("%d",&ch);
	if(ch=='#')  p=NULL;
else{
	  p=(NODE*)malloc(sizeof(NODE));
	  p->data=ch;
	  create(p->lchild);
	  create(p->rchild);
}
return p;
 }
void preorder(NODE *root)   /*travel the tree using preorder */
 {
 if(root->data==NULL) return;
printf("%d",root->data);
preorder(root->lchild);
preorder(root->rchild);
 }
 
void   inorder (NODE *root)  /*travel  the tree using inorder */
 {
if(root->data==NULL) return;
inorder(root->lchild);
printf("%d",root->data);
inorder(root->rchild);
 }
 
void postorder(NODE *root)  /*travel the tree using  postorder */

{
if(root->data==NULL) return;
postorder(root->lchild);
postorder(root->rchild);
printf("%d",root->data);
}

主要问题
1.遍历创建二叉树时每次给p分配空间在return后数据无法传入上一层就会出现只有第一个根节点有值的情况

为解决这个问题我们将遍历创建语句改一下，例如

	p=(NODE*)malloc(sizeof(NODE));
	p->data=ch;
	p->lchild=create(p->lchild);
	p->rchild=create(p->rchild);

目的将下一层的指针指向的地址(包括结点值和它指向的所有结点)传给上一层，这样p就不会丢失结点。
(∩_∩)
2.在遍历时判断二叉树是否为空语句需要改进，例如

 if(root->data==NULL) return;

这句空返回语句看似没有问题，问题在于此函数是用 void定义，不能返回指针类型，返回就会出现
Segmentation fault (core dumped)
的错误，同样这个错误有时也会出现在指针分配空间出现问题上
为了不再重新改动函数定义类型，我们将判断语句修改一下，例如

	if(root)
 {
printf("%c",root->data);
preorder(root->lchild);
preorder(root->rchild);
}

直接判断此时指向的root指针是否为空即可。

以下是修改后全部代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef struct  btnode
	  {
struct btnode*lchild,*rchild;
int data;

	   }NODE;
int main()
{
	NODE *root,*q;
	NODE *create(NODE *p);
	void preorder();
	void inorder();
	void postorder();
    int t;
	q=(NODE*)malloc(sizeof(NODE));;
	
	printf("At  the first,we create   a tree\n");
	printf("Please input nodes of tree\n");
	root=create(q);
	
	if  (root==NULL)    printf("It's  an empty  tree!\n");
	else
	   {
		printf("\n1.The preordetraverse  \n");
	    printf("  2.The inordertraverse \n");
	    printf("  3.The postordertraverse \n");
		printf("  Please choose  a  kind  of  order\n");
		scanf("%d",&t);
		switch   (t)
		   {
			case 1: preorder(root);  break;
			case 2: inorder(root);   break;
			case 3:postorder(root);   break;
			default: printf(" The error!");
		   }
		}
}

NODE  * create(NODE *p)    /*create the structure of binary tree */
 {
	
 char ch;
    scanf("%c",&ch);
	if(ch=='#')  {p=NULL;
	//printf("%c",ch);
	}
else{
    
	p=(NODE*)malloc(sizeof(NODE));
	p->data=ch;
	//printf("p的值为%c",p->data);
	p->lchild=create(p->lchild);
	p->rchild=create(p->rchild);
	
}

return p;
 }
void preorder(NODE *root)   /*travel the tree using preorder */

 {
 	if(root)
 {
printf("%c",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
 }
void   inorder (NODE *root)  /*travel  the tree using inorder */

 {
	if(root){
inorder(root->lchild);
printf("%c",root->data);
inorder(root->rchild);
}
 }
void postorder(NODE *root)  /*travel the tree using  postorder */

{
    if(root){
postorder(root->lchild);
postorder(root->rchild);
printf("%c",root->data);
}
}

运行结果