C语言演示二叉树算法

Oracle 作者：ruisa 时间：2012-11-25 20:16:00 0 删除编辑

　二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i " 1个结点;深度为k的二叉树至多有2k " 1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

方法/步骤

1

首先打开VC++6.0
2

选择文件，新建
3

选择C++ source file 新建一个空白文档
4

首先声明头文件
5

定义树的结点结构

typedef struct TreeNode{
char data;/*树中结点的数据是一个字符*/
struct TreeNode *lchild;
struct TreeNode *rchild;
}TREENODE;
6

声明变量
int NodeNum = 0;/*统计数的结点数*/
int LeafNum = 0;/*统计数的叶子结点数*/
char ch[] = {'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' '};
int inc = 0;
7

用函数建立一个二叉树

int CreateBiTree(TREENODE **T)
/*按先序次序输入二叉树中结点的值,以空字符表示空树*/
{
char i;
if(ch[inc++]==' ')
*T = NULL;
else
{
printf("%c ",ch[inc-1]);
if(!(*T = (TREENODE *)malloc(sizeof(TREENODE))))
return -1;
(*T)->data = ch[inc-1];
printf("%c ",(*T)->data);
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
return 1;
}
8

先序遍历二叉树
int PreOderTraverse(TREENODE *T)
{
if(T)
{
printf("%c ",T->data);
PreOderTraverse(T->lchild);
PreOderTraverse(T->rchild);
}
return 1;
}
9

中序遍历二叉树
int InOderTraverse(TREENODE *T)
{
if(T)
{
InOderTraverse(T->lchild);
printf("%c ",T->data);
InOderTraverse(T->rchild);
}
return 1;
}
10

后序遍历二叉树
int BackOderTraverse(TREENODE *T)
{
if(T)
{
BackOderTraverse(T->lchild);
BackOderTraverse(T->rchild);
printf("%c ",T->data);
}
return 1;
}
11

利用先序遍历来计算树中的结点数
void CountNodeNum(TREENODE *T)
{
if(T)
{
NodeNum ++;
CountNodeNum(T->lchild);
CountNodeNum(T->rchild);
}
}
12

利用先序遍历计算叶子节点数
void CountLeafNum(TREENODE *T)
{
if(T)
{
if((!(T->lchild))&&(!(T->rchild)))
LeafNum ++;
CountLeafNum(T->lchild);
CountLeafNum(T->rchild);
}
}
13

主函数
int main()
{
TREENODE *T;
int i;
CreateBiTree(&T);
do
{

puts("**************************************************");
puts("* you can choose: *");
puts("* 1: Traverse the Binary tree by pre order *");
puts("* 2: Traverse the Binary tree by mid order *");
puts("* 3: Traverse the Binary tree by back order *");
puts("* 4: Count the node num of the Binary tree *");
puts("* 5: Count the leaf node num of the Binary tree*");
puts("**************************************************");
puts("please input your choice:");
scanf("%d",&i);
switch(i)
{
case 1:
printf("The preoder is: ");
PreOderTraverse(T);
printf(" ");
break;
case 2:
printf("The midoder is: ");
InOderTraverse(T);
printf(" ");
break;
case 3:
printf("The backoder is: ");
BackOderTraverse(T);
printf(" ");
break;
case 4:
CountNodeNum(T);
printf("The nodenum of the tree is:%d ",NodeNum);
break;
case 5:
CountLeafNum(T);
printf("The leafnum of the tree is:%d ",LeafNum);
break;
}
printf("please input any char to go on ");
getch();
}while((i>=1)&&(i<6));

getch();
return 1;
}
14

运行结果

END