2xpaixu.cpp

二叉排序C++实现

#include "stdafx.h" 
#include "math.h" 
#include "stdlib.h" 
#include "stdio.h" 


#define MAXSIZE 200 
int leaf_num; 
int node_num; 

typedef struct tnode 
{ 
int data; 
struct tnode *lchild,*rchild; 
}TNODE; 

TNODE *creatbt(int T[],int n,int i); //函数声明 
void freetree(TNODE *bt); 
void leaf_sum(TNODE *bt); 
void node_sum(TNODE *bt); 
void exchage(TNODE *bt); 
void leveltrav(TNODE * bt); 
void preorder(TNODE *bt); 
void inorder(TNODE *bt); 
void postorder(TNODE *bt); 


main() {
      int t_array[14]={8,11,2,3,9,15,6,-1,-1,-1,10, 
-1,-1,13}; //-1表示空 
int x; 
printf("数组："); 
for (x=0;x<=13;x++) 
printf("%d ",t_array[x]); 
struct tnode *root; 
root=creatbt(t_array,14,0); 
printf("\n先序遍历："); 
preorder(root); 
printf("\n中序遍历："); 
inorder(root); 
printf("\n后序遍历："); 
postorder(root); 
freetree(root); 
getchar(); 

} 


TNODE *creatbt(int T[],int n,int i) //递归 创建二叉树程序 
{ 
TNODE *r; 
if (i>n-1||T[i]==-1) //-1表示空 总计n个数存储在 0-n-1 
return (NULL); 
r=(TNODE *)malloc(sizeof(TNODE)); 
r->data=T[i]; 
r->lchild=creatbt(T,n,2*i+1); 
r->rchild=creatbt(T,n,2*i+2); 
return(r); 
} 

void freetree(TNODE *bt)//释放二叉树的所有结点，只能后序遍历，因为其他会把子树的根释放，这样就没办法释放孩子结点了 
{ 
if (bt!=NULL) 
{ 
freetree(bt->lchild); 
freetree(bt->rchild); 
free(bt); 
} 
} 





void leaf_sum(TNODE *bt) //叶子结点个数的递归算法 先要设置全局变量int leaf_num 
{ 
//static int leaf_num; 
if (bt!=NULL) 
{ 

if (bt->lchild==NULL&&bt->rchild==NULL) 

leaf_num++; //全局变量 
leaf_sum(bt->lchild); 
leaf_sum(bt->rchild); 
} 

} 


void node_sum(TNODE *bt) //先序遍历统计结点总数，就是用先序遍历实现其非递归 
{ 
if (bt!=NULL) 
{ 
node_num++; 
node_sum(bt->lchild); 
node_sum(bt->rchild); 
} 
} 

void exchage(TNODE *bt)//二叉树所有结点的左右子树交换 
{ 
TNODE *p; 
if (bt!=NULL) 
{ 
p=bt->lchild; 
bt->lchild=bt->rchild; 
bt->rchild=p; 
exchage(bt->lchild); //也可以exchage(bt->rchild);在前 exchage(bt->lchild);在后 
exchage(bt->rchild); 


} 
} 



void leveltrav(TNODE * bt)//层次遍历，使用队列 
{ 
TNODE *queue[MAXSIZE]; //队列 
int rear=0,front=0; 
if (bt!=NULL) 
printf("%d\n",bt->data); 
rear=(rear+1)%MAXSIZE; 
queue[rear]=bt; 
while(rear!=front) //队列不空则循环 
{ 
front=(front+1)%MAXSIZE; 
bt=queue[front]; 
if (bt->lchild!=NULL) 
{ 
printf("%d\n",bt->lchild->data); 
rear=(rear+1)%MAXSIZE; 
queue[rear]=bt->lchild; 
} 
if (bt->rchild!=NULL) 
{ 
printf("%d\n",bt->rchild->data); 
rear=(rear+1)%MAXSIZE; 
queue[rear]=bt->rchild; 
} 
} 
} 



void preorder(TNODE *bt) //先序遍历 
{ 

if (bt!=NULL) 
{ 
printf(" %3d",bt->data); 
preorder(bt->lchild); 
preorder(bt->rchild); 
} 
} 

void inorder(TNODE *bt) //中序遍历 
{ 
if(bt!=NULL) 
{ 
inorder(bt->lchild); 
printf(" %3d",bt->data); 
inorder(bt->rchild); 
} 
} 
void postorder(TNODE *bt) //后序遍历 
{ 

if(bt!=NULL) 
{ 
postorder(bt->lchild); 
postorder(bt->rchild); 
printf(" %3d",bt->data); 
} 
}