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

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

t522535261 · 2018-4-30 02:32:48

#include
#include
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);

  traverse(root->lchild);

  traverse(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);

}

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

1 个回复