//author: chby
//date: 2006-11-5
//description: 二叉树的递归操作
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char DataType;
typedef struct node
{
DataType data;
struct node *lchild,*rchild;
}BiTNode;
typedef BiTNode * BiTree;
//建立二叉树
void CreateBiTree(BiTree * T)
{
char c;
printf("进入 CreateBiTree...\n");
scanf("%c",&c);
getchar();
if(c == ' ')
{
printf("不产生子树。\n");
*T = NULL;
}
else
{
*T = (BiTNode *)malloc(sizeof(BiTNode)); //生成一个新节点
(*T)->data = c;
printf("产生左右子树。\n");
CreateBiTree(&(*T)->lchild); //生成左子树
CreateBiTree(&(*T)->rchild); //生成右子树
}
} //前序遍历
void Preorder(BiTNode * T)
{
if(T)
{
printf("%c\n",T->data);
Preorder(T->lchild); //遍历左子树
Preorder(T->rchild); //遍历右子树
}
} //中序遍历
void Inorder(BiTNode * T)
{
if(T)
{
Inorder(T->lchild);
printf("%c\n",T->data);
Inorder(T->rchild);
}
}
//后序遍历
void Postorder(BiTNode * T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c\n",T->data);
}
} void main()
{
BiTree T = NULL;
char j;
int flag = 1; //-------------程序解说---------------
printf("本程序实现二叉树的操作。\n");
printf("可以进行建立二叉树,递归先序、中序、后序遍历。\n");
printf("请将先序遍历二叉树的结果输入已建立二叉树。\n");
printf("对于叶子节点以空格表示。\n");
printf("例如:abc de g f (回车) 如下二叉树:\n");
printf(" a \n");
printf(" / \n");
printf(" b \n");
printf(" / \\ \n");
printf(" c d \n");
printf(" / \\ \n");
printf(" e f \n");
printf(" \\ \n");
printf(" g \n"); CreateBiTree(&T); //初始化树
while(flag)
{
printf("请选择: \n");
printf("1.递归先序遍历\n");
printf("2.递归中序遍历\n");
printf("3.递归后序遍历\n");
printf("4.退出程序\n");
scanf("%c",&j);
getchar();
switch(j)
{
case '1':
if(T)
{
printf("先序遍历二叉树:");
Preorder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '2':
if(T)
{
printf("中序遍历二叉树:");
Inorder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '3':
if(T)
{
printf("后序遍历二叉树:");
Postorder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
default:
flag=0;printf("程序运行结束,按任意键退出!\n");
}
}
}
//date: 2006-11-5
//description: 二叉树的递归操作
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef char DataType;
typedef struct node
{
DataType data;
struct node *lchild,*rchild;
}BiTNode;
typedef BiTNode * BiTree;
//建立二叉树
void CreateBiTree(BiTree * T)
{
char c;
printf("进入 CreateBiTree...\n");
scanf("%c",&c);
getchar();
if(c == ' ')
{
printf("不产生子树。\n");
*T = NULL;
}
else
{
*T = (BiTNode *)malloc(sizeof(BiTNode)); //生成一个新节点
(*T)->data = c;
printf("产生左右子树。\n");
CreateBiTree(&(*T)->lchild); //生成左子树
CreateBiTree(&(*T)->rchild); //生成右子树
}
} //前序遍历
void Preorder(BiTNode * T)
{
if(T)
{
printf("%c\n",T->data);
Preorder(T->lchild); //遍历左子树
Preorder(T->rchild); //遍历右子树
}
} //中序遍历
void Inorder(BiTNode * T)
{
if(T)
{
Inorder(T->lchild);
printf("%c\n",T->data);
Inorder(T->rchild);
}
}
//后序遍历
void Postorder(BiTNode * T)
{
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c\n",T->data);
}
} void main()
{
BiTree T = NULL;
char j;
int flag = 1; //-------------程序解说---------------
printf("本程序实现二叉树的操作。\n");
printf("可以进行建立二叉树,递归先序、中序、后序遍历。\n");
printf("请将先序遍历二叉树的结果输入已建立二叉树。\n");
printf("对于叶子节点以空格表示。\n");
printf("例如:abc de g f (回车) 如下二叉树:\n");
printf(" a \n");
printf(" / \n");
printf(" b \n");
printf(" / \\ \n");
printf(" c d \n");
printf(" / \\ \n");
printf(" e f \n");
printf(" \\ \n");
printf(" g \n"); CreateBiTree(&T); //初始化树
while(flag)
{
printf("请选择: \n");
printf("1.递归先序遍历\n");
printf("2.递归中序遍历\n");
printf("3.递归后序遍历\n");
printf("4.退出程序\n");
scanf("%c",&j);
getchar();
switch(j)
{
case '1':
if(T)
{
printf("先序遍历二叉树:");
Preorder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '2':
if(T)
{
printf("中序遍历二叉树:");
Inorder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '3':
if(T)
{
printf("后序遍历二叉树:");
Postorder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
default:
flag=0;printf("程序运行结束,按任意键退出!\n");
}
}
}
注意, 输入两个双引号内的部分, 在字母 f 后有一个空格, 不要掉了. 然后, 出现如下所示打印:
abc de g f
产生左右子树。
进入 CreateBiTree...
产生左右子树。
进入 CreateBiTree...
产生左右子树。
进入 CreateBiTree...
不产生子树。
进入 CreateBiTree...
不产生子树。
进入 CreateBiTree...
不产生子树。
进入 CreateBiTree...此时按一下空格, 回车
即出现如下打印:
不产生子树。
请选择:
1.递归先序遍历
2.递归中序遍历
3.递归后序遍历
4.退出程序接下来, 选择 1, 2, 3 或者 4