/*
2012年12月9日21:29:35
输入节点建立二叉树,
遍历递归的先中後序,
非递归的先中後序,
计算出深度
结点数
*/
# include <stdio.h>
# include <stdlib.h>
typedef char TElemType;
TElemType Nil = ' ';//字符型以空格符为空
# define form "%c"//输入输出的格式为%c
typedef struct BiTNode
{
TElemType data;
BiTNode * lchild, * rchild;//左右孩子指针
}BiTNode, * BiTree;
//操作结果：构造空的二叉树T
void InitBiTree(BiTree * T)
{
* T = NULL;
}
//按先序次序输入二叉树中结点的值（可为字符型或整型）
//构造二叉链表表示的二叉树T，变量Nil表示空（子）树
void CreateBiTree(BiTree * T)
{
TElemType ch;
scanf(form,&ch);
if (ch == Nil)//空
* T = NULL;
else
{
* T = (BiTree)malloc(sizeof(BiTNode));//生成根结点
if (! T)
exit(-1);
(* T)->data = ch;
CreateBiTree(&(* T)->lchild);//构造左子树
CreateBiTree(&(* T)->rchild);//构造右子树
}
}
//初始条件：二叉树T存在，Visit是对结点操作的应用函数
//操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
void PreOrderTraverse(BiTree T,void(* Visit)(TElemType))
{
if (T)//T不空
{
Visit(T->data);//先访问根结点
PreOrderTraverse(T->lchild,Visit);//再先序遍历左子树
PreOrderTraverse(T->rchild,Visit);//最后先序遍历右子树
}
}
//初始条件：二叉树T存在，Visit是对结点操作的应用函数
//操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次
void InOrderTraverse(BiTree T,void(* Visit)(TElemType))
{
if (T)
{
InOrderTraverse(T->lchild,Visit);//先中序遍历左子树
Visit(T->data);//再访问根结点
InOrderTraverse(T->rchild,Visit);//最后中序遍历右子树
}
}
//初始条件：二叉树T存在，Visit是对结点操作的应用函数
//操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
void PostOrderTraverse(BiTree T,void(* Visit)(TElemType))
{
if (T)//T不空
{
PostOrderTraverse(T->lchild,Visit);//先后序遍历左子树
PostOrderTraverse(T->rchild,Visit);//再后序遍历左子树
Visit(T->data);//最后访问根结点
}
}
//先序非递归
void PreOrder(BiTNode* b)
{
BiTNode *stack[100], *p;
int top = -1;
if (b != NULL)
{
top++;
stack[top] = b;
while (top > -1)
{
p = stack[top];
top--;
printf("%c ", p->data);
if (p->rchild != NULL)
{
top++;
stack[top] = p->rchild;
}
if (p->lchild != NULL)
{
top++;
stack[top] = p->lchild;
}
}
printf("\n");
}
}
//非递归中序
void InOrder(BiTNode* b)
{
BiTNode *stack[100], *p;
int top = -1;
if (b != NULL)
{
p = b;
while (top > -1 || p != NULL)
{
while (p != NULL)
{
top++;
stack[top] = p;
p = p->lchild;
}
if (top > -1)
{
p = stack[top];
top--;
printf("%c ", p->data);
p = p->rchild;
}
}
}
printf("\n");
}
//非递归后序
void PostOrder(BiTNode * b)
{
BiTNode *stack[100], * p;
int sign, top = -1;
if (b != NULL)
{
do
{
while (b != NULL)
{
top++;
stack[top] = b;
b = b->lchild;
}
p = NULL;
sign = 1;
while (top != -1 && sign)
{
b = stack[top];
if (b->rchild == p)
{
printf("%c ", b->data);
top--;
p = b;
}
else
{
b = b->rchild;
sign = 0;
}
}
}
while (top != -1);
printf("\n");
}
}
//初始条件：二叉树T存在
//操作结果：返回T的深度
int BiTreeDepth(BiTree T)
{
int i,j;
if (! T)
{
return 0;//空树的深度为0
}
if (T->lchild)
{
i = BiTreeDepth(T->lchild);//i为左子树的深度
}
else
{
i = 0;
}
if (T->rchild)
{
j = BiTreeDepth(T->rchild);//j为右子树的深度
}
else
{
j = 0;
}
return i > j ? i+1 : j+1;//T的深度为其左右子树的深度中的大者加1
}
//统计结点个数
int Node_Count(BiTree t)
{
if(t == NULL)
return 0;
int left=0,right=0;
if(t->lchild != NULL)
left = Node_Count(t->lchild);
if(t->rchild != NULL)
right = Node_Count(t->rchild);
return left+right+1;
}
void visitT(TElemType e)
{
printf(form" ",e);
}
int main(void)
{
BiTree T;
InitBiTree(&T);
printf("请先序输入二叉树(如:ab三个空格表示a为根节点，b为左子树的二叉树)\n");
CreateBiTree(&T);
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visitT);
printf("\n先序非递归遍历二叉树:\n");
PreOrder(T);
printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T,visitT);
printf("\n中序非递归遍历二叉树:\n");
InOrder(T);
printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T,visitT);
printf("\n后序非递归遍历二叉树:\n");
PostOrder(T);
printf("\n二叉树的深度是%d\n",BiTreeDepth(T));
printf("\n二叉树的结点个数是%d\n",Node_Count(T));
printf("\n");
return 0;
}
/*
结果：
------------------------
请先序输入二叉树(如:ab三个空格表示a为根节点，b为左子树的二叉树)
ab c
先序递归遍历二叉树:
a b c
先序非递归遍历二叉树:
a b c
中序递归遍历二叉树:
b a c
中序非递归遍历二叉树:
b a c
后序递归遍历二叉树:
b c a
后序非递归遍历二叉树:
b c a
二叉树的深度是2
二叉树的结点个数是3
Press any key to continue
------------------------------
*/
