bitree.cpp

用C语言编写实现数据结构方面的例子

#include <stdio.h>
#include <malloc.h>

typedef struct BiTNode
{
	char data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;


BiTree BiTNodeCreateTree()//创建二叉树
//按先序遍历输入第个元素,若结点lchild,rchild为空,输入#号代替.
//如输入abd##e##cf### 先序输出结果为:abcecf
{
	char ch;
	BiTNode *t;
	scanf("%c",&ch);
	if(ch=='#') t=NULL;
	else
	{	
		t=(BiTNode *)malloc(sizeof(BiTNode));
		t->data=ch;
		t->lchild=BiTNodeCreateTree();
		t->rchild=BiTNodeCreateTree();
	}
	return t;
}

void BiTNodeVisit(BiTree t)
{
printf("  Address:  %#x,  Data:  %c,  Left Pointer:  %#x,  Right Pointer:  %#x\n",t,t->data,t->lchild,t->rchild);
}

void PreOrderTraverse(BiTree t)
{
	if (t)
	{
		BiTNodeVisit(t);
		PreOrderTraverse(t->lchild);
		PreOrderTraverse(t->rchild);
	}
}

void InOrderTraverse(BiTree t)
{
	if (t)
	{
		
		InOrderTraverse(t->lchild);
		BiTNodeVisit(t);
		InOrderTraverse(t->rchild);
	}
}

void PostOrderTraverse(BiTree t)
{
	if (t)
	{
		
		PostOrderTraverse(t->lchild);
		PostOrderTraverse(t->rchild);
		BiTNodeVisit(t);
	}
}
int BiTreeHight(BiTree t)//二叉树的高度
{
	int h;
	int lh,rh;
	if (t==NULL)
	{
		h=0;
	}
	else
	{
		lh=BiTreeHight(t->lchild);
		rh=BiTreeHight(t->rchild);
		h=(lh > rh ? lh:rh)+1;
	}	
	return h;
}

//int BiTreeHight(BiTree t)//二叉树的高度



int main()
{
	BiTree t; 
 
	int h;

    printf("\n   Please input TREE Data:\n");
    t=BiTNodeCreateTree();

	h=BiTreeHight(t);
	printf("二叉树的高度:%d\n",h);
    printf("先序遍历:\n");
	PreOrderTraverse(t);
	printf("\n");
    printf("中序遍历:\n");
	InOrderTraverse(t);
	printf("后序遍历:\n");
	PostOrderTraverse(t);


	return 0;
}