树型结构的用途很广，其中二叉树尤为重要。
这里列出了几种基本的算法
（1）遍历二叉树。（先序遍历，递归方式，采用广义表的格式输出）
（2）求某节点的左、右孩子节点值
（3）求二叉树的深度（递归方式）
（4）求二叉树的宽度（类似层次遍历，用到队列）
（5）求二叉树的节点个数（递归）
（6）求二叉树叶子节点个数（递归）
代码里写的很明白了，上面的括号是下面的代码实现方式的简述。
#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
#include "algo7_1.h"
//---------------------------------------
void CreateBTNode(BTNode *&Bt,char str[])
{
BTNode *St[MaxSize],*p = NULL;
int top = 0,base = 0,k=0,j=0; //k:标志左右节点
char ch = str[j];
Bt = NULL;
while(ch != '\0')
{
switch (ch)
{
case '(':
St[top] = p;
top++;
k =1; //左结点
break;
case ')':
top--;
break;
case ',':
k = 2;
break;
default:
p = (BTNode *)malloc(sizeof(BTNode));
p->data = ch;
p->lchild = NULL;
p->rchild = NULL;
if (Bt == NULL)
{
Bt = p;
}
else
{
switch(k)
{
case 1:
St[top - 1]->lchild = p;
break;
case 2:
St[top - 1]->rchild = p;
break;
}
k = 0;
}
} //switch
j++;
ch = str[j];
} //while
}
//寻找指定结点
BTNode * FindNode(BTNode * Bt,ElemType e) //递归
{
BTNode *p = NULL;
if (Bt == NULL)
{
return NULL;
}
else if (Bt->data == e)
{
return Bt;
}
else
{
p=FindNode(Bt->lchild,e);
if ( p != NULL)
{
return p;
}
else
return FindNode(Bt->rchild,e);
}
}
//返回Bt指向的左结点
BTNode * LchildNode(BTNode *Bt)
{
if (!Bt)
{
return NULL;
}
else
return Bt->lchild;
}
//返回Bt指向的右结点
BTNode * RchildNode(BTNode *Bt)
{
if (!Bt)
{
return ERR;
}
else
return Bt->rchild;
}
//求二叉树Bt的深度
int BTNodeDepth(BTNode *Bt)
{
int lchildDep,rchildDep;
if (0 == Bt)
{
return 0;
}
else
{
lchildDep = BTNodeDepth(Bt->lchild);
rchildDep = BTNodeDepth(Bt->rchild);
return lchildDep>rchildDep?(lchildDep+1):(rchildDep+1);
}
}
//以广义表的方式输出二叉树
void DispBTNode(BTNode * Bt)
{
if (NULL == Bt)
{
return;
}
else
{
printf("%c",Bt->data);
if (Bt->lchild || Bt->rchild)
{
printf("(");
DispBTNode(Bt->lchild);
}
if (Bt->rchild)
{
printf(",");
DispBTNode(Bt->rchild);
printf(")");
}
}
}
//返回二叉树Bt的宽度
int BTWidth(BTNode * Bt)
{
struct
{
BTNode *p;
int lno;
} Que[MaxSize];
BTNode * Aux;
int front = 0,rear = 0;
int max = 0,lNum = 0;
struct
{
int lcur;
int lSumNum;
} lSum = {0,0};
if (!Bt)
{
return 0;
}
else
{
Que[rear].p = Bt;
Que[rear++].lno = 1;
while(rear != front) //层次遍历
{
if (lSum.lcur!=lNum)
{
max = max>lSum.lSumNum?max:lSum.lSumNum;
lSum.lcur = lNum; //新一层
lSum.lSumNum = 0; //重新开始计数
}
Aux = Que[front].p;
lNum = Que[front].lno;
front++;
if (Aux->lchild != NULL)
{
Que[rear].p = Aux->lchild;
Que[rear].lno = lNum +1;
rear++;
lSum.lSumNum++;
}
if (Aux->rchild != NULL)
{
Que[rear].p = Aux->rchild;
Que[rear].lno = lNum +1;
rear++;
lSum.lSumNum++;
}
} //while
return max;
}
}
//求二叉树Bt的结点个数
int Nodes(BTNode *Bt) //递归
{
int lchildNo,rchildNo;
if (!Bt)
{
return 0;
}
else
{
lchildNo = Nodes(Bt->lchild);
rchildNo = Nodes(Bt->rchild);
return(lchildNo + rchildNo + 1);
}
}
//求二叉树Bt的叶子结点个数
int LeafNodes(BTNode *Bt)
{
int lchildNo,rchildNo;
if (!Bt)
{
return 0;
}
else if (Bt->lchild == 0 && Bt->rchild == 0)
{
return 1;
}
else
{
lchildNo = LeafNodes(Bt->lchild);
rchildNo = LeafNodes(Bt->rchild);
return lchildNo +rchildNo;
}
}
//algo7_1.h
#define OK 1
#define ERR 0
#define TRUE 1
#define FALSE 0
#define NULL 0
typedef int BOOL;
#define MaxSize 100
typedef char ElemType;
typedef struct _node
{
ElemType data; //数据元素
struct _node * lchild; //左子树
struct _node * rchild; //右子树
}BTNode;
void CreateBTNode(BTNode * &Bt,char str[] ); //根据str串，用广义表的表现形式，来生成树
//寻找指定结点
BTNode * FindNode(BTNode * Bt,ElemType e); //递归
//返回Bt指向的左结点
BTNode * LchildNode(BTNode *Bt);
//返回Bt指向的右结点
BTNode * RchildNode(BTNode *Bt);
//求二叉树Bt的深度
int BTNodeDepth(BTNode *Bt);
//以广义表的方式输出二叉树
void DispBTNode(BTNode * Bt);
//返回二叉树Bt的宽度
int BTWidth(BTNode * Bt);
//求二叉树Bt的结点个数
int Nodes(BTNode *Bt); //递归
//求二叉树Bt的叶子结点个数
int LeafNodes(BTNode *Bt);
// Proj7_1.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "algo7_1.h"
#include "string.h"
int _tmain(int argc, _TCHAR* argv[])
{
BTNode *b,*p,*lp,*rp;
char str[100];
printf("Please input the generalized list of binary tree:\n");
// scanf_s("%s",str);
// strcpy_s(str, "A(B(C(D,E),F(G,H(I,J))),K(L,M(N,O(P(Q,R)))))");
strcpy_s(str, "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
CreateBTNode(b,str);
printf("(1)Output the binary tree:\n");
DispBTNode(b);
printf("\n");
printf("(2)The node of \'H\':\n");
p = FindNode(b,'H');
if (p)
{
lp = LchildNode(p);
if (lp)
{
printf("lchild is %c\n",lp->data);
}
rp = RchildNode(p);
if (rp)
{
printf("rchild is %c\n",rp->data);
}
}
printf("\n");
printf("(3)The binary tree's depth:%d\n",BTNodeDepth(b));
printf("(4)The binary tree's width:%d\n",BTWidth(b));
printf("(5)The binary tree's sum node:%d\n",Nodes(b));
printf("(6)The binary tree's leaf node:%d\n",LeafNodes(b));
return 0;
}
测试二叉树：
A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))
结果：
