【问题描述】
二叉树采用二叉链表作存储结构，编程实现二叉树的如下基本操作：
1. 按先序序列构造一棵二叉链表表示的二叉树T；
2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历序列，分别输出结点的遍历序列；
3. 求二叉树的深度/结点数目/叶结点数目；
4. 将二叉树每个结点的左右子树交换位置。
【数据描述】
//- - - - - - 二叉树的二叉链表存储表示 - - - - - - -
typedef struct BiTNode{
TElemType data;
Struct BiTNode * lchild, * rchild; //左右孩子指针
}BiTNode, * BiTree;
【算法描述】
1. 建立一棵二叉树
Status CreateBiTree(BiTree &T)
//按先序次序输入二叉树中结点的值（一个字符），＃字符表示空树，
//构造二叉链表表示的二叉树T。
scanf(&ch);
if (ch=='＃') T=NULL;
else {
if (!(T=(BiTNode *) malloc(sizeof(BiTNode)))) exit (OVERFLOW);
T->data = ch; //生成根结点
CreateBiTree(T->lchild); //生成左子树
CreateBiTree(T->rchild); //生成右子树
}
return OK;
}//CreateBiTree
2. 先序遍历二叉树递归算法
Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数，
//先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。
//一旦visit()失败，则操作失败。
if (T){
if (Visit(T->data))
if (PreOrderTraverse(T->rchild，Visit)) return OK;
return ERROR;
}else return OK;
}// PreOrderTraverse
3. 中序遍历的递归算法
Status InOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){
if (T){
if (Visit(T->data))
if (InOrderTraverse(T->rchild，Visit)) return OK;
return ERROR;
}else return OK;
}// InOrderTraverse
4. 后序遍历递归算法
Status PostOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){
if (T){
if (Visit(T->data))
if (PreOrderTraverse(T->rchild，Visit)) return OK;
return ERROR;
}else return OK;
}// PreOrderTraverse
5. 中序遍历非递归算法之一
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)) {
InitStack(S);
Push(S,T); //根指针进栈
While (!StackEmpty(S)) {
While (GetTop(S,p) && p) Push(S,p->lchild); //向左走到尽头
Pop(S,p); //空指针退栈
If (!StackEmpty(S)) { //访问结点，向右一步
Pop(S,p);
If (!Visit(p->data)) return ERROR;
Push(S,p->rchild);
}//if
}//while
return OK;
}//InOrderTraverse
6. 中序遍历非递归算法之二
Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)) {
//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。
//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。
InitStack(S);
p=T;
While (p‖!StackEmpty(S)) {
if (p) {Push(S,p); p=p->lchild;} //根指针进栈，遍历左子树
else { //根指针退栈，访问根结点，遍历右子树
Pop(S,p);
if (!Visit(p->data)) return ERROR;
p=p->rchild);
}//else
}//while
return OK;
}//InOrderTraverse
7． 层次遍历二叉树的非递归算法
Status LevelOrder(BiTree T){
//按层次遍历二叉树T， Q为队列
InitQueue(Q);
If (T!=NULL){// 若树非空
EnQueue(Q,T);//根结点入队列
While (!QueueEmpty(Q)){
DeQueue(Q,b); //队首元素出队列
Visit(b->data); //访问结点
If (b->lchild!=NULL) EnQueue(Q,b->lchild);//左子树非空，则入队列
If (b->rchold!=Null) EnQueue(Q,b->rchild);//右子树非空，则入队列
}//while
}//if
}LevelOrder
8． 求二叉树的深度
int depth(BiTree T){
//若T为空树，则深度为0，否则其深度等于左子树或右子树的最大深度加1
if (T==NULL) return 0;
else {dep1=depth(T->lchild);
dep2=depth(T->rchild);
return dep1>dep2?dep1+1:dep2+1;
}
}
【C源程序】
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define NULL 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree *T){
char ch;
ch=getchar();
if (ch=='#') (*T)=NULL; /* #代表空指针*/
else {
(*T)=(BiTree) malloc(sizeof(BiTNode));/*申请结点 */
(*T)->data=ch; /*生成根结点 */
CreateBiTree(&(*T)->lchild) ; /*构造左子树 */
CreateBiTree(&(*T)->rchild) ; /*构造右子树 */
}
return 1;
}
void PreOrder(BiTree T){
if (T) {
printf("%2c",T->data); /*访问根结点，此处简化为输出根结点的数据值*/
PreOrder(T->lchild); /*先序遍历左子树*/
PreOrder(T->rchild); /*先序遍历右子树*/
}
}
void LevleOrder(BiTree T){
/*层次遍历二叉树T，从第一层开始，每层从左到右*/
BiTree Queue[MAX],b; /*用一维数组表示队列，front和rear分别表示队首和队尾指针*/
int front,rear;
front=rear=0;
if (T) /*若树非空*/
{Queue[rear++]=T; /*根结点入队列*/
while (front!=rear){ /*当队列非空*/
b=Queue[front++]; /*队首元素出队列，并访问这个结点*/
printf("%2c",b->data);
if (b->lchild!=NULL) Queue[rear++]=b->lchild; /*左子树非空，则入队列*/
if (b->rchild!=NULL) Queue[rear++]=b->rchild; /*右子树非空，则入队列*/
}
}
}//LevelOrder
int depth(BiTree T){ /*求二叉树的深度*/
int dep1,dep2;
if (T==NULL) return 0;
else {dep1=depth(T->lchild);
dep2=depth(T->rchild);
return dep1>dep2?dep1+1:dep2+1;
}
}//depth
main(){
BiTree T=NULL;
printf("/nCreate a Binary Tree/n");
CreateBiTree(&T); /*建立一棵二叉树T*/
printf("/nThe preorder is:/n");
PreOrder(T); /*先序遍历二叉树*/
printf("/nThe level order is:/n");
LevleOrder(T); /*层次遍历二叉树*/
printf("/nThe depth is:%d/n",depth(T));
}
【测试数据】
1. 输入：#↙，建立一棵空树，
先序遍历和层次遍历没有输出，树的深度输出为0；
2. 输入：A↙
先序和层次遍历输出均为A；
深度输出为：1
3. 输入：ABC##DE#G##F###↙，
先序输出为： A B C D E G F
层次遍历输出为：A B C D E F G
深度输出为： 5
【说明】
1. 按先序次序输入二叉树中结点的值，用'#'表示空树，对每一个结点应当确定其左右子树的值（为空时必须用特定的空字符占位），故执行此程序时，最好先在纸上画出你想建立的二叉树，每个结点的左右子树必须确定，若为空，则用特定字符标出，然后再按先序输入这棵二叉树的字符序列；
2. 为了简化程序的书写量，以及程序的清晰性，对结点的访问以一条输出语句表示，若有更复杂的或多种访问，可以将结点的访问编写成函数，然后通过函数指针进行函数的调用。读者若有兴趣，可自行编写。