爱华网 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i ? 1个结点;深度为k的二叉树至多有2k ? 1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。
C语言演示二叉树算法 1、
首先打开VC++6.0
C语言演示二叉树算法 2、
选择文件，新建
C语言演示二叉树算法 3、
选择C++ source file 新建一个空白文档
C语言演示二叉树算法_二叉树
C语言演示二叉树算法 4、
首先声明头文件
C语言演示二叉树算法 5、
定义树的结点结构
typedef struct TreeNode{
char data;/*树中结点的数据是一个字符*/
struct TreeNode *lchild;
struct TreeNode *rchild;
}TREENODE;
C语言演示二叉树算法 6、
声明变量
int NodeNum = 0;/*统计数的结点数*/
int LeafNum = 0;/*统计数的叶子结点数*/
char ch[] = {'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e', 'f', ' ', ' ', 'g', ' ', ' '};
int inc = 0;
C语言演示二叉树算法_二叉树
C语言演示二叉树算法 7、
用函数建立一个二叉树
int CreateBiTree(TREENODE **T)
/*按先序次序输入二叉树中结点的值,以空字符表示空树*/
{
char i;
if(ch[inc++]==' ')
*T = NULL;
else
{
printf("%cn",ch[inc-1]);
if(!(*T = (TREENODE *)malloc(sizeof(TREENODE))))
return -1;
(*T)->data = ch[inc-1];
printf("%cn",(*T)->data);
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
return 1;
}
C语言演示二叉树算法 8、
先序遍历二叉树
int PreOderTraverse(TREENODE *T)
{
if(T)
{
printf("%c ",T->data);
PreOderTraverse(T->lchild);
PreOderTraverse(T->rchild);
}
return 1;
}
C语言演示二叉树算法 9、
中序遍历二叉树
int InOderTraverse(TREENODE *T)
{
if(T)
{
InOderTraverse(T->lchild);
printf("%c ",T->data);
InOderTraverse(T->rchild);
}
return 1;
}
C语言演示二叉树算法_二叉树
C语言演示二叉树算法 10、
后序遍历二叉树
int BackOderTraverse(TREENODE *T)
{
if(T)
{
BackOderTraverse(T->lchild);
BackOderTraverse(T->rchild);
printf("%c ",T->data);
}
return 1;
}
C语言演示二叉树算法 11、
利用先序遍历来计算树中的结点数
void CountNodeNum(TREENODE *T)
{
if(T)
{
NodeNum ++;
CountNodeNum(T->lchild);
CountNodeNum(T->rchild);
}
}
C语言演示二叉树算法 12、
利用先序遍历计算叶子节点数
void CountLeafNum(TREENODE *T)
{
if(T)
{
if((!(T->lchild))&&(!(T->rchild)))
LeafNum ++;
CountLeafNum(T->lchild);
CountLeafNum(T->rchild);
}
}
C语言演示二叉树算法_二叉树
C语言演示二叉树算法 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:n");
PreOderTraverse(T);
printf("n");
break;
case 2:
printf("The midoder is:n");
InOderTraverse(T);
printf("n");
break;
case 3:
printf("The backoder is:n");
BackOderTraverse(T);
printf("n");
break;
case 4:
CountNodeNum(T);
printf("The nodenum of the tree is:%dn",NodeNum);
break;
case 5:
CountLeafNum(T);
printf("The leafnum of the tree is:%dn",LeafNum);
break;
}
printf("please input any char to go onn");
getch();
}while((i>=1)&&(i<6));
getch();
return 1;
}
C语言演示二叉树算法 14、
运行结果
