示例代码:
主要有二叉树的遍历(递归和非递归)，创建树，按树状打印树，以及统计叶子结点的数量,计算树的高度。
/*************************************************************************
> File Name: erchashu.c
> Author:
> Mail:
> Created Time: 2018年10月30日 星期二 17时37分28秒
************************************************************************/
#include<stdio.h>
#include<unistd.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 100
typedef struct Node
{
char data;
struct Node *Lchild;
struct Node *Rchild;
}BiTNode,*BiTree;
typedef struct stack
{
BiTree data[MAXSIZE];
int top;
}Seqstack;
int count=0;//计算树中叶子结点的全局变量
//初始化栈
Seqstack *InitStack()
{
Seqstack *s;
s=(Seqstack *)malloc(sizeof(Seqstack));
s->top=-1;
return s;
}
//判断栈是否为空
int IsEmpty(Seqstack *s)
{
if(s->top == -1)
return 1;
else
return 0;
}
//入栈
int Push(Seqstack *s,BiTree root)
{
if(s->top == MAXSIZE-1)
return 0;
else
{
s->top++;
s->data[s->top]=root;
return 1;
}
}
//出栈
int Pop(Seqstack *s,BiTree *root)
{
if(IsEmpty(s))
return 0;
else
{
*root=s->data[s->top];
s->top--;
}
return 1;
}
//获取栈顶元素
int Top(Seqstack*s,BiTree *root)
{
if(IsEmpty(s))
return 0;
else
{
*root=s->data[s->top];
}
return 1;
}
//扩展先序遍历序列创建二叉树
void creat(BiTree *root)
{
char ch;
ch=getchar();
if(ch=='#') //若读入的结点为‘＃’,则当前树置空.
*root=NULL;
else //申请结点空间，存入结点数据
{
*root=(BiTree)malloc(sizeof(BiTNode));
(*root)->data=ch;
creat(&((*root)->Lchild));
creat(&((*root)->Rchild));
}
}
//求二叉树的高度即层次
int Treedepth(BiTree root)
{
int h1,hr,h;
if(root==NULL)
return 0;
else
{
h1=Treedepth(root->Lchild);
hr=Treedepth(root->Rchild);
h=(h1>hr?h1:hr)+1;
return h;
}
}
//按树状打印二叉树
void PrintTree(BiTree root,int h)
{
if(root==NULL)
return;
PrintTree(root->Rchild,h+1);
for(int i=0;i<h;i++)
printf(" ");
printf("%c\n",root->data);
PrintTree(root->Lchild,h+1);
}
//中序遍历输出二叉树中叶子结点的个数
void InOrderleaf(BiTree root)
{
if(root)
{
InOrderleaf(root->Lchild);
if(root->Lchild==NULL&&root->Rchild==NULL) //如果是叶子节点，全局变量count++.
{
count++;
}
InOrderleaf(root->Rchild);
}
}
//先序递归遍历二叉树
void PreOrder(BiTree root)
{
if(root)
{
printf("%c",root->data);
PreOrder(root->Lchild);
PreOrder(root->Rchild);
}
}
//中序非递归遍历二叉树
void InOrder(BiTree root)
{
Seqstack *s;
BiTree p;
s=InitStack();
p=root;
while(p!=NULL||!IsEmpty(s))
{
while(p!=NULL)
{
Push(s,p);
p=p->Lchild;
}
if(!IsEmpty(s))
{
Pop(s,&p);
printf("%c",p->data);
p=p->Rchild;
}
}
}
//后序非递归遍历二叉树
void PostOrder(BiTree root)
{
Seqstack *s;
BiTree p,q;
s=InitStack();
p=root;
q=NULL;
while(p!=NULL||!IsEmpty(s))
{
while(p!=NULL)
{
Push(s,p);
p=p->Lchild;
}
if(!IsEmpty(s))
{
Top(s,&p);
if((p->Rchild==NULL)||(p->Rchild==q))
{
Pop(s,&p);
printf("%c",p->data);
q=p;
p=NULL;
}
else
p=p->Rchild;
}
}
}
int main()
{
BiTree root;
printf("请输入先序序列，创建二叉树:\n");
creat(&root);
printf("所建树如下:\n");
PrintTree(root,1);
InOrderleaf(root);
printf("树的高度为: %d\n",Treedepth(root));
printf("树中叶子结点数目为: %d\n",count);
printf("先序遍历序列(递归)如下:\n");
PreOrder(root);
printf("\n中序遍历序列如下(非递归):\n");
InOrder(root);
printf("\n后序遍历序列(非递归)如下:\n");
PostOrder(root);
printf("\n");
}
这块主要说一下按树状打印二叉树:
如上建立的二叉树形状如下:
运行结果为是横向显示了二叉树，也就是上图绕根结点逆时针旋转90度，就出现以下结果。
请输入先序序列，创建二叉树:
ABC##DE#G##F###
所建树如下:
A
F
D
G
E
B
C
貌似，看起来还是很不明了。
首先呢，这种树形打印格式要求先打印右子树，再打印根，最后打印左子树,即按先右后左的策略中序遍历二叉树(即逆中序),然后，结点的横向位置由结点在树中的层次决定，那个参数h就是表示层次的。这样能控制结点的输出位置，保证同一层的在同一竖行例如： **我们传入PrintTree(root,1)这里层h为１，这里无右子树，所以打印根结点，根据for循环则打印根结点时在它的前面打印一个空格，然后是打印左子树B,这时传入参数为B这个结点和层h+1,即为下一层，对于B依然是右中左的顺序，所以先看D,这时层为h+1+1,依然是右中左，我们先要看F这时层为h+1+1+1,而F没有右孩子,所以我们可以打印F依据for循环，打印h+1+1+1个空格,依次类推，就得到了树状。所以，我们可以得到,根节点，一定是最前面的，因为它的层高为１，前面为一个空格。其他的都比它空格多，还有，树中同一层的结点在同一列打印。
//按树状打印二叉树
void PrintTree(BiTree root,int h)
{
if(root==NULL)
return;
PrintTree(root->Rchild,h+1);
for(int i=0;i<h;i++)
printf(" ");
printf("%c\n",root->data);
PrintTree(root->Lchild,h+1);
}