链式二叉树（测试）
#include"stdio.h"
#include"string.h"
#define Max 20
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode;
typedef BinTNode *BinTree;
int NodeNum,leaf;
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL);
else{
T=(BinTNode *)malloc(sizeof(BinTNode));
T->data=ch;
T->lchild=CreatBinTree();
T->rchild=CreatBinTree();
return(T);
}
}
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild);
hr=TreeDepth(T->rchild);
max=hl>hr? hl:hr;
NodeNum=NodeNum+1;
if(hl==0&&hr==0) leaf=leaf+1;
return(max+1);
}
else return(0);
}
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p;
cq[1]=T;
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front];
printf("%c",p->data);
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild;
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild;
}
}
}
void main()
{
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:");
root=CreatBinTree();
do {
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n");
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i);
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root);
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root);
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root);
break;
case 4: depth=TreeDepth(root);
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root);
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
//二叉树递归算法。。。。结构
typedef struct Btree{
ElemType data; //先假设为 int
struct Btree *lchild, *rchild;
}Btree;
recrusive递归
先序
void preorder(Btree *bt){
printf(\"%d\\t\", bt->data);
preoder(bt->lchild);
preorder(bt->rchild)
return;;
}
中序
void midorder(Btree *bt){
midorder(bt->lchild);
printf(\"%d\\t\", bt->data);
midorder(bt->rchild);
return;
}
后序
void postorder(Btree *bt){
postorder(bt->lchild);
postorder(bt->rchild);
printf(\"%d\\t\", bt->data);
return;
}
将二叉树的左右子树位置调换
void exchange(Btree *bt){
Btree *temp;
if(bt!=NULL){
temp=bt->lchild;
bt->lchild=bt->rchild;
bt->rchild=temp;
exchange(bt->lchild);
exchange(bt->rchild);
}
}
TAG:
