Question

求一个完整的二叉树遍历的程序

C或C++编写的都行，尽量不要出错，谢谢

Answer 1

#include<stdio.h>
#include<malloc.h>
int i = 0;
typedef struct treeNODE
{
char data;
struct treeNODE *lchild , *rchild , *parent ;
}treenode , *tree;

/////////////////////////////////////////////////////////////////////////////////
//////二叉树的建立

tree creat(tree root)
{
char ch;
ch = getchar();
if(ch == '#')
root = NULL;
else
{
root = (treenode*)malloc(sizeof(treenode));
root->data = ch;
root->lchild = creat(root->lchild);
root->rchild = creat(root->rchild);
}
return root;
}
/////////////////////////////////////////////////////////////////////////////////
/////中序遍历
void traverse(tree root)
{
if(root)
{

traverse(root->lchild);
printf(" %c ",root->data);
traverse(root->rchild);
}
}

/////////////////////////////////////////////////////////////////////////////////
/////先序遍历

void traverse1(tree root)
{
if(root)
{
printf(" %c ",root->data);

traverse1(root->lchild);

traverse1(root->rchild);
}
}

////////////////////////////////////////////////////////////////////////////////
/////后序遍历

void traverse2(tree root)
{
if(root)
{

traverse(root->lchild);

traverse(root->rchild);
printf(" %c ",root->data);
}
}

//////////////////////////////////////////////////////////////////////////////////
///////计算叶子数

int leaf(tree root )
{
int num1 = 0 , num2 = 0;
if(root == NULL)

return 0;

if(root->lchild ==NULL && root->rchild == NULL)
return 1;
else
{num1++;
leaf(root->lchild );
num2++;
leaf(root->rchild );
return num1+num2;
}

}

/////////////////////////////////////////////////////////////////////////////////
//////结点数

int node(tree root)
{
int num1 , num2;
if(!root)
return 0;
if(root->lchild == NULL &&root->rchild ==NULL)
return 1;

else
{

num1 = node(root->lchild);

num2 = node(root->rchild);
}
return num1+num2 +1 ;
}

/////////////////////////////////////////////////////////////////////////////////
///////复制二叉树

tree copy(tree root)
{
tree root1;
// root1 = (treenode*)malloc(sizeof(treenode));
if(!root)
return NULL;

{
root1 = (treenode*)malloc(sizeof(treenode));
root1->data = root->data;
root->lchild = root1->lchild = copy( root->lchild );
root->rchild = root1->rchild = copy( root->rchild );

return root1;
}

}

////////////////////////////////////////////////////
////左右子树交换
void chage(tree p)
{
tree t;
if(p==NULL)
return ;
else
{
chage(p->lchild);
chage(p->rchild);
t = p->lchild;
p->lchild = p->rchild;
p->rchild = t;
}

}
///////////////////////////

void main()
{
tree t=NULL , node1;

printf("输入树的数据\n");
t = creat(t);
printf("中序遍历\n");
traverse(t);
printf("\n");
printf("先序遍历\n");
traverse1(t);
printf("\n");
printf("后序遍历\n");
traverse2(t);
printf("\n");

printf("叶子数 %d \n",leaf(t));
printf("节点数%d\n",node(t));
node1 = copy(t );
traverse(node1);
printf("\n");
chage(t);
traverse(t);

}