以下基本都是用递归实现
#include <stdio.h>
#include <stdlib.h>
#define Maxsize 20
typedef char datatype;
typedef struct BiNode
{
datatype data;
struct BiNode *lchild, *rchild;
}bitree;
//前序遍历的递归算法
void PreOrder( bitree *root)
{
if (root ==NULL) return;
else {
printf("%d ",root->data);
PreOrder( root->lchild);
PreOrder(root->rchild);
}
}
//中序遍历的递归算法
void InOrder (bitree *root)
{
if (root==NULL) return;
else {
InOrder(root->lchild);
printf("%d ",root->data);
InOrder(root->rchild);
}
}
//后序遍历的递归算法
void PostOrder(bitree *root)
{
if (root==NULL) return;
else {
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%d ",root->data);
}
}
//前序遍历的非递归算法
void PreOrder1( bitree *root )
{ bitree *p=root ;
bitree *s[Maxsize]; int top;
top= -1; //采用顺序栈,并假定不会发生上溢
while (p!=NULL || top!= -1)
{
while (p!= NULL)
{
printf("%d ",p->data);
s[++top]=p;
p = p->lchild;
}
if (top!= -1) {
p=s[top--];
p=p->rchild;
}
}
}
//以递归方式创建二叉树,如输入:ABD##E##C#FHJ##K##I## (按前中后序输入,空节点用#代替)
bitree * creatBitree()
{ bitree *root ;char ch;
ch=getchar();
if (ch == '#') root = NULL;
else {
root=(bitree*)malloc(sizeof(bitree));
root->data=ch;
root->lchild =creatBitree();
root->rchild= creatBitree();
}
return root;
}
//删除二叉树
bitree * deleteTree(bitree *root)
{ if( root!=NULL)
{
deleteTree(root->lchild);
deleteTree(root->rchild);
free(root);
}
root=NULL; //free只是释放了指针所指空间,并没有自动将指针root为空,需要手动置root为空。只有删除完所有结点置root为空,测试整颗二叉树上结点总数才为0
return root;
}
//计算二叉树的深度
int Depth(bitree *root)
{ int hl = 0, hr = 0;
if (root == NULL) return 0;
else {
hl= Depth(root ->lchild);
hr= Depth(root ->rchild);
return hl>=hr ? (hl+1) : (hr+1);
}
}
int count=0;
void CountNode(bitree *root) //n为结点总数
{
if (root) {
count++;
CountNode(root->lchild);
CountNode(root->rchild);
}
}
//计算叶子结点总数
int count=0;
void leafNum(bitree *root)
{
if (root) {
leafNum(root->lchild);
leafNum(root->rchild);
if(root->lchild==NULL&&root->rchild==NULL)
count++;
}
}
广义表表示 :L = (A (B (C, D), E ( , F) ) ) 可以得出
可以抽出基本代码:
若为空: 打印空格; 否则: 打印根; 若子不为空: 打印"("; 打印左子树; 打印“,”; 打印右子树; 打印“)”;
显然,存在递归,将需要递归的地方(打印左子树\打印右子树)改成递归即可
//以广义表的形式输出二叉树结构
void displayBitree(bitree *root)
{
if( root == NULL)
{
printf(" "); return ;
}
printf("%d", root->data);
if( root->lchild || root->rchild)
{
printf("\(");
displayBitree(root->lchild);
printf(",");
displayBitree(root->rchild);
printf("\)");
}
}