我本仁慈，奈何苍天不许
分类： LINUX
2013-10-23 23:08:41
/*本程序是创建二叉树，同时是一先序遍历的方式输入，节点后面没有时，输入-1代表空，本程序可以以三种方式输出：先序遍历，中序遍历和后续遍历，还可以交换左右子树的位置*/
#include
#include
typedef int datatype;
typedef struct node
{
datatype data;
struct node *lchild, *rchild;
}btree,*btreelink;
void creat_btree(btreelink *bt);
void preorder(btreelink bt);
void preorder2(btreelink bt);
void inorder(btreelink bt);
void postorder(btreelink bt);
void exchange_lr_child(btreelink bt);
void out(btreelink bt);
void creat_btree(btreelink *bt)
{
int c;
scanf("%d",&c);
if(c == -1)
*bt = NULL;
else
{
*bt = (btreelink)malloc(sizeof(btree));
(*bt)->data = c;
creat_btree(&(*bt)->lchild);
creat_btree(&(*bt)->rchild);
}
}
//先序遍历
void preorder(btreelink bt)
{
if(bt != NULL)
{
printf("%d,",bt->data);
preorder(bt->lchild);
preorder(bt->rchild);
}
}
//中序遍历
void inorder(btreelink bt)
{
if(bt != NULL)
{
inorder(bt->lchild);
printf("%d,",bt->data);
inorder(bt->rchild);
}
}
//后续遍历
void postorder(btreelink bt)
{
if(bt != NULL)
{
postorder(bt->lchild);
postorder(bt->rchild);
printf("%d,",bt->data);
}
}
/*
根节点入栈
while（栈不空）
{
出栈；
访问元素；
如果右子树不空，右子树入栈；
如果左子树不空，左子树入栈；
}
*/
void preorder2(btreelink bt)
{
btreelink stack[10], p = NULL;
int top = 0;
if(bt)
{
top++;
stack[top] = bt;
}
while(top > 0)
{
p = stack[top];
top--;
printf("%d,",p->data);
if(p->rchild)
{
top++;
stack[top] = p->rchild;
}
if(p->lchild)
{
top++;
stack[top] = p->lchild;
}
}
}
/*交换左右子树*/
void exchange_lr_child(btreelink bt)
{
btreelink tmp = NULL;
if(bt)
{
if(bt->lchild || bt->rchild)
{
tmp = bt->lchild;
bt->lchild = bt->rchild;
bt->rchild = tmp;
}
exchange_lr_child(bt->lchild);
exchange_lr_child(bt->rchild);
}
}
/*以先序，中序，后续三种遍历方式输出*/
void out(btreelink bt)
{
preorder(bt);
putchar('\n');
inorder(bt);
putchar('\n');
postorder(bt);
putchar('\n');
}
int main (int argc, char *argv[])
{
btreelink tree;
creat_btree(&tree);
out(tree);
exchange_lr_child(tree);
out(tree);
return 0;
}
