二叉树如何建立
先序递归创建二叉树，并对其进行 先序、中序、后序遍历
#include // malloc()等
#include // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include // atoi()，exit()
#include // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
==============================
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemType;
typedef struct Btn{
TElemType data;
struct Btn *lchild,*rchild;
}BTN ,*BT;
int CreateBT(BT T) {
char ch;
getchar();
printf("\nplease input yuan su:\n"); /*输入二叉树的元素*/
scanf("%c",&ch);
if(ch=='*') T=NULL;
else {
if(!(T=(BTN *)malloc(sizeof(BTN)))) exit(OVERFLOW);
T->data=ch;
CreateBT(T->lchild);
CreateBT(T->rchild);
}
return OK;
} /*创建二叉树*/
int PreOrderT(BT
T )
{
if(T!=NULL) {
printf("%c \n", T -> data);
PreOrderT(T->lchild ) ;
PreOrderT(T->rchild ) ;
}
return OK;
} /*前序遍历二叉树 T：打印每个结点的数据域一次且仅一次*/
int InOrderT(BT T)
{
if (T != NULL) {
InOrderT( T -> lchild ) ;
printf("%c \n", T -> data);
InOrderT( T -> rchild ) ;
}
return OK;
} /*中序遍历二叉树 T：打印每个结点的数据域一次且仅一次*/
int PostOrderT(BT T) {
if (T != NULL) {
PostOrderT( T -> lchild ) ;
PostOrderT( T -> rchild ) ;
printf("%c \n", T -> data);
}
return OK;
} /*后序遍历二叉树 T：打印每个结点的数据域一次且仅一次*/
int BTdepth(BT T)
{
int rd,ld;
if(!T) return 0;
else { ld=BTdepth(T->lchild);
rd=BTdepth(T->rchild);
if(ld>rd) return rd+1;
else return ld+1;
}
} /*编写算法求二叉树T(二叉链表存储结构)的深度。*/
int main(){
BT T
TElemType e;
int Te,j;
while(j){
printf("input gong neng\n"); /*请输入你要的功能*/
printf("-----------\n");
printf("1:xian xu chuang jian shu\n"); /*按前序遍历规则创建二叉树*/
printf("2:xian xu bian li T\n"); /*前序遍历二叉树*/
printf("3:zhong xu bian li T\n"); /*中序遍历二叉树*/
printf("4:hou xu bian li T\n"); /*后序遍历二叉树*/
printf("5:shen du \n"); /*编写算法求二叉树T的深度*/
printf("6:ceng ci bian li \n"); /*按层次遍历二叉树*/
printf("0:exit\n"); /*退出程序*/
printf("-----------\n");
scanf("%d",&j);
switch(j){
case 1:CreateBT(T);break;
case 2:PreOrderT(T);break;
case 3:InOrderT(T);break;
case 4:PostOrderT(T);break;
case 5:BTdepth(T);break;
case 0:exit(1);
}
}
return 0;
}
=================================
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}