以下是一个可进行二叉树基本操作的演示程序
实现下列几种基本运算：（1）创建二叉树；（2）先序遍历二叉树；（3）中序遍历二叉树；（4）后序遍历二叉树；（5）层序遍历二叉树；（6）求度为1的结点的个数；（7）求叶子结点的个数；（8）求度为2的结点的个数。
二叉树以链式结构表示，主程序以菜单方式的用户界面。
//二叉树的基本操作
#include <iostream>
using namespace std;
typedef struct node //定义结点
{
char data;
struct node* lchild, * rchild;
} BinTNode;
typedef BinTNode* BinTree; //定义二叉树
void CreateBinTree(BinTree& T); //先序创建二叉树
void PreOrder(BinTree T); //先序遍历二叉树
void InOrder(BinTree T); //中序遍历二叉树
void PostOrder(BinTree T); //后序遍历二叉树
int onechild(BinTree T); //求度为1的结点的个数
int leafs(BinTree T); //求叶子结点的个数
int twochild(BinTree T); //度为2的结点的个数
void translevel(BinTree b); //层序遍历二叉树
int main()
{
int n;
BinTree T=0;
char ch1, ch2;
cout << "Welcome to enter the testing program for bintree basic operator" << endl;
cout << "Please Chose" << endl;
ch1 = 'y';
while (ch1 == 'y' || ch1 == 'Y')
{
cout << "A --------building \n";
cout << "B------PreOrder\n";
cout << "C------InOrder\n";
cout << "D-------PostOrder\n";
cout << "E------ - translevel\n";
cout << "F------onechild\n";
cout << "G-----twochild\n";
cout << "H------leafs\n";
cout << "X-------Quit\n";
cin >> ch2;
switch (ch2)
{
case 'a':
case 'A':
cout << "请输入按先序建立二叉树的结点序列：\n";
CreateBinTree(T);
break;
case 'b':
case 'B':
cout << "二叉树的先序遍历序列：\n";
PreOrder(T);
cout << endl;
break;
case 'c':
case 'C':
cout << "二叉树的中序遍历序列：\n";
InOrder(T);
cout << endl;
break;
case 'd':
case 'D':
cout << "二叉树的后序遍历序列：\n";
PostOrder(T);
cout << endl;
break;
case 'f':
case 'F':
cout << "二叉树的单孩子结点数：\n";
n = onechild(T);
cout << n << endl;
break;
case 'g':
case 'G':
cout << "二叉树的双孩子结点数：\n";
n = twochild(T);
cout << n << endl;
break;
case 'h':
case 'H':
cout << "二叉树的叶子结点数：\n";
n = leafs(T);
cout << n << endl;
break;
case 'e':
case 'E':
cout << "二叉树的层序遍历序列：\n";
translevel(T);
cout << endl;
break;
case 'x':
case 'X':
ch1 = 'x';
break;
}
}
}
void CreateBinTree(BinTree& T)
{
char ch;
cin >> ch;
if (ch == '0') T = NULL;
else
{
T = (BinTNode*)new BinTNode;
T->data = ch;
CreateBinTree(T->lchild);
CreateBinTree(T->rchild);
}
}
void InOrder(BinTree T)
{
if (T)
{
InOrder(T->lchild);
cout << T->data << " ";
InOrder(T->rchild);
}
}
void PostOrder(BinTree T)
{
if (T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
cout << T->data << " ";
}
}
void PreOrder(BinTree T)
{
if (T)
{
cout << T->data << " ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//层序遍历二叉树
//采用一个队列q，先将二叉树的根 结点入队列，然后退队列，输出该结点，若它有左子树，便将左子树根结点入队列，若它有右子树，便将右子树根结点入队列，如此直到队列空为止。
//因为队列的特点是先进先出，从而达到按层序遍历的目的。
#define MAXLEN 100
void translevel(BinTree b)
{
struct node
{
BinTree vec[MAXLEN];
int f, r;
}q; //定义队列q， f 表示队头指针，r队尾指针
q.f = 0; //置队列为空队列
q.r = 0;
if (b != NULL) cout << b->data << " ";
q.vec[q.r] = b; //结点指针进入队列
q.r = q.r + 1; //队尾指针后移
while (q.f < q.r) //队列不为空
{
b = q.vec[q.f]; //队头出队列
q.f = q.f + 1;
if (b->lchild != NULL) //输出左孩子，并入队列
{
cout << b->lchild->data << " ";
q.vec[q.r] = b->lchild;
q.r = q.r + 1;
}
if (b->rchild != NULL) //输出右孩子，并入队列
{
cout << b->rchild->data << " ";
q.vec[q.r] = b->rchild;
q.r = q.r + 1;
}
}
}
int onechild(BinTree T)
{
int num1, num2;
if (T == NULL) return 0;
else if (T->lchild == NULL && T->rchild != NULL || T->lchild != NULL && T->rchild == NULL)
return 1 + onechild(T->lchild) + onechild(T->rchild);
else
{
num1 = onechild(T->lchild);
num2 = onechild(T->rchild);
return num1 + num2;
}
}
int leafs(BinTree T)
{
int num1, num2;
if (T == NULL) return 0;
else if (T->lchild == NULL && T->rchild == NULL) return 1;
else
{
num1 = leafs(T->lchild);
num2 = leafs(T->rchild);
return num1 + num2;
}
}
int twochild(BinTree T)
{
int num1, num2;
if (T == NULL) return 0;
else
{
num1 = twochild(T->lchild);
num2 = twochild(T->rchild);
if (T->lchild != NULL && T->rchild != NULL)
return (num1 + num2 + 1);
else
return (num1 + num2);
}
}
//以下扩展树的深度+结点总数
int depth(BinTree T) //树的深度
{
int depl, depr;
if (T == NULL) return 0;
else
{ //计算左子树的深度
depl = depth(T->lchild);
//计算右子树的深度
depr = depth(T->rchild);
if(depl > depr) return depl + 1;
else return depr + 1;
}
}
int Nodes(BinTree T) // 结点总数
{
int nodesl, nodesr;
if(T == NULL) return 0;
else
{
nodesl = Nodes(T->lchild);
nodesr = Nodes(T->rchild);
return nodesl + nodesr + 1;
}
}以二叉树HDA00C0B00GF0E000为例，运行结果如下：
Welcome to enter the testing program for bintree basic operator
Please Chose
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
a
请输入按先序建立二叉树的结点序列：
HDA00C0B00GF0E000
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
b
二叉树的先序遍历序列：
H D A C B G F E
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
c
二叉树的中序遍历序列：
A D C B H F E G
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
d
二叉树的后序遍历序列：
A B C D E F G H
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
e
二叉树的层序遍历序列：
H D G A C F B E
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
f
二叉树的单孩子结点数：
3
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
g
二叉树的双孩子结点数：
2
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit
h
二叉树的叶子结点数：
3
A --------building
B------PreOrder
C------InOrder
D-------PostOrder
E------ - translevel
F------onechild
G-----twochild
H------leafs
X-------Quit