主题:二叉树(C程序)
这是我从别人那里拷来的,在MinGWStudioFullSetup-2_05下运行,运行之后不知道输入数据了,请有工具的朋友帮忙运行一下,看看怎么输入数据。。。
//example.h 伪代码的定义和常见的库函数
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <stdio.h>
#include <io.h>
#include <math.h>
#include <process.h>
#include<iostream.h>
#define TRUE1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
//二叉树的链式存储结构bitree.h
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//二叉树基本操作bitree.cpp
void CreateBiTree(BiTree &T)
{
int i;
scanf("%d",&i);
if (i==0) T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=i;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return;
}
void PreOrderTraverse(BiTree T)
{
if(T)
{
printf("%d ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return;
}
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%d ",T->data);
InOrderTraverse(T->rchild);
}
return;
}
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d ",T->data);
}
return;
}
/*void InitBiTree(BiTree &T)
{
T=NULL;
return;
}
void InsertRoot(BiTree &T,int root)
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data =root;
T->lchild =T->rchild =NULL;
return;
}
void SearchRoot(BiTree T,int root,BiTree &p)
{
if(T)
{
if(T->data==root) { p=T; return;}
SearchRoot(T->lchild ,root,p);
SearchRoot(T->rchild ,root,p);
}
return ;
}
int InsertChild(BiTree T,int root,int child,int flag)
{
BiTree p,s;
SearchRoot(T,root,p);
if (!p) return 0;
else
{
s=(BiTree)malloc(sizeof(BiTNode)); s->data =child; s->lchild =s->rchild =NULL;
if(flag) p->lchild =s;
else p->rchild =s;
return 1;
}
}
int n=0;*/
int CountNode(BiTree T)
{
if(T==0) return 0;
else
return CountNode(T->lchild )+CountNode(T->rchild )+1;
}/*
int Leaf(BiTree T)
{
if(!T) return 0;
if(!T->lchild && !T->rchild ) return 1;
return Leaf(T->lchild )+Leaf(T->rchild);
}
int OneChild(BiTree T)
{
if(!T) return 0;
if(T->lchild && !T->rchild || !T->lchild && T->rchild ) return 1+OneChild(T->lchild )+OneChild(T->rchild );
return OneChild(T->lchild )+OneChild(T->rchild );
}
int TwoChild(BiTree T)
{
if(!T) return 0;
if(T->lchild && T->rchild ) return 1+TwoChild(T->lchild )+TwoChild(T->rchild );
return TwoChild(T->lchild )+TwoChild(T->rchild );
}
BiTree swap(BiTree T)
{
BiTree B,b1,b2;
if(!T) B=NULL;
else
{
B=(BiTree)malloc(sizeof(BiTNode));
B->data=T->data ;
b1=swap(T->lchild );
b2=swap(T->rchild );
B->lchild=b2;
B->rchild =b1;
}
return B;
}*/
int level(BiTree T)
{
int num1,num2;
if(!T) return 0;
num1=level(T->lchild );
num2=level(T->rchild );
if(num1>=num2) return num1+1;
else return num2+1;
}
//验证基本操作正确性的主函数main_bitree.cpp
int main()
{
BiTree t;
printf("按先序遍历次序输入二叉树中元素:\n");
CreateBiTree(t);
printf("先序遍历二叉树的序列为:\n");
PreOrderTraverse(t);
printf("中序遍历二叉树的序列为:\n");
InOrderTraverse(t);
printf("后序遍历二叉树的序列为:\n");
PostOrderTraverse(t);
/*InitBiTree(t);
InsertRoot(t,1);
InsertChild(t,1,2,1);
InsertChild(t,1,3,0);
InsertChild(t,3,4,1);
InsertChild(t,4,5,0);
InsertChild(t,5,6,1);
InsertChild(t,5,7,0);
InsertChild(t,6,8,0);
InsertChild(t,7,9,1);
InsertChild(t,9,10,0);
InOrderTraverse(t);
printf("\n");*/
printf("二叉树共有%d层\n",level(t));
printf("二叉树中的结点数为:%d\n",CountNode(t));
/*printf("二叉树中的叶子结点数为:%d\n",Leaf(t));
printf("二叉树中的单孩子结点数为:%d\n",OneChild(t));
printf("二叉树中的双孩子结点数为:%d\n",TwoChild(t));
BiTree b;
b=swap(t);
InOrderTraverse(b);*/
printf("\n");
return 1;
}
//example.h 伪代码的定义和常见的库函数
#include <string.h>
#include <ctype.h>
#include <malloc.h>
#include <stdio.h>
#include <io.h>
#include <math.h>
#include <process.h>
#include<iostream.h>
#define TRUE1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
//二叉树的链式存储结构bitree.h
typedef struct BiTNode{
int data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//二叉树基本操作bitree.cpp
void CreateBiTree(BiTree &T)
{
int i;
scanf("%d",&i);
if (i==0) T=NULL;
else
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data=i;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return;
}
void PreOrderTraverse(BiTree T)
{
if(T)
{
printf("%d ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return;
}
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
printf("%d ",T->data);
InOrderTraverse(T->rchild);
}
return;
}
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%d ",T->data);
}
return;
}
/*void InitBiTree(BiTree &T)
{
T=NULL;
return;
}
void InsertRoot(BiTree &T,int root)
{
T=(BiTree)malloc(sizeof(BiTNode));
T->data =root;
T->lchild =T->rchild =NULL;
return;
}
void SearchRoot(BiTree T,int root,BiTree &p)
{
if(T)
{
if(T->data==root) { p=T; return;}
SearchRoot(T->lchild ,root,p);
SearchRoot(T->rchild ,root,p);
}
return ;
}
int InsertChild(BiTree T,int root,int child,int flag)
{
BiTree p,s;
SearchRoot(T,root,p);
if (!p) return 0;
else
{
s=(BiTree)malloc(sizeof(BiTNode)); s->data =child; s->lchild =s->rchild =NULL;
if(flag) p->lchild =s;
else p->rchild =s;
return 1;
}
}
int n=0;*/
int CountNode(BiTree T)
{
if(T==0) return 0;
else
return CountNode(T->lchild )+CountNode(T->rchild )+1;
}/*
int Leaf(BiTree T)
{
if(!T) return 0;
if(!T->lchild && !T->rchild ) return 1;
return Leaf(T->lchild )+Leaf(T->rchild);
}
int OneChild(BiTree T)
{
if(!T) return 0;
if(T->lchild && !T->rchild || !T->lchild && T->rchild ) return 1+OneChild(T->lchild )+OneChild(T->rchild );
return OneChild(T->lchild )+OneChild(T->rchild );
}
int TwoChild(BiTree T)
{
if(!T) return 0;
if(T->lchild && T->rchild ) return 1+TwoChild(T->lchild )+TwoChild(T->rchild );
return TwoChild(T->lchild )+TwoChild(T->rchild );
}
BiTree swap(BiTree T)
{
BiTree B,b1,b2;
if(!T) B=NULL;
else
{
B=(BiTree)malloc(sizeof(BiTNode));
B->data=T->data ;
b1=swap(T->lchild );
b2=swap(T->rchild );
B->lchild=b2;
B->rchild =b1;
}
return B;
}*/
int level(BiTree T)
{
int num1,num2;
if(!T) return 0;
num1=level(T->lchild );
num2=level(T->rchild );
if(num1>=num2) return num1+1;
else return num2+1;
}
//验证基本操作正确性的主函数main_bitree.cpp
int main()
{
BiTree t;
printf("按先序遍历次序输入二叉树中元素:\n");
CreateBiTree(t);
printf("先序遍历二叉树的序列为:\n");
PreOrderTraverse(t);
printf("中序遍历二叉树的序列为:\n");
InOrderTraverse(t);
printf("后序遍历二叉树的序列为:\n");
PostOrderTraverse(t);
/*InitBiTree(t);
InsertRoot(t,1);
InsertChild(t,1,2,1);
InsertChild(t,1,3,0);
InsertChild(t,3,4,1);
InsertChild(t,4,5,0);
InsertChild(t,5,6,1);
InsertChild(t,5,7,0);
InsertChild(t,6,8,0);
InsertChild(t,7,9,1);
InsertChild(t,9,10,0);
InOrderTraverse(t);
printf("\n");*/
printf("二叉树共有%d层\n",level(t));
printf("二叉树中的结点数为:%d\n",CountNode(t));
/*printf("二叉树中的叶子结点数为:%d\n",Leaf(t));
printf("二叉树中的单孩子结点数为:%d\n",OneChild(t));
printf("二叉树中的双孩子结点数为:%d\n",TwoChild(t));
BiTree b;
b=swap(t);
InOrderTraverse(b);*/
printf("\n");
return 1;
}