[C++知识库]2013年数据结构第五题（C/C++) —— 非递归测量二叉树的高度

首先我将这个题用递归方法先实现一下，再改成非递归

递归编程实现：

#include<iostream>
using namespace std;

#define TElemType char
typedef struct BiTNode{
 TElemType data;
 struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T)//先序遍历的顺序建立二叉链表
{
 TElemType ch;
 cin>>ch;
 if(ch=='#')T=NULL;
 else
 {
  T=new BiTNode;
  T->data=ch;
  CreateBiTree(T->lchild);
  CreateBiTree(T->rchild);
 }
}

int Depth(BiTree &T)//递归计算二叉树的深度
{
 int m,n;
 if(T==NULL)return 0;
 else
 {
  m=Depth(T->lchild);
  n=Depth(T->rchild);
  if(m>n)return (m+1);
  else return (n+1); 

 }
}

void DestroyTree(BiTree &T)//销毁二叉树
{
 if(T!=NULL)
 {
  DestroyTree(T->lchild);
  DestroyTree(T->rchild);
  printf("销毁结点: %c\n",T->data);
  delete T;
  T=NULL; 
 }
 return;
}

int main()
{
  BiTree T=NULL;
  printf("先序建立二叉树:\n");
  CreateBiTree(T);
  printf("\n此二叉树深度为:\n%d\n",Depth(T));
  DestroyTree(T);//销毁二叉树
  printf("\n成功销毁二叉树!\n");
  return 0; 
}

现在在此基础上，写出非递归的代码：

#include<iostream>
using namespace std;

#define TElemType char
typedef struct BiTNode{
  TElemType data;
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree; //二叉树的二叉链表存储表示

void CreateBiTree(BiTree &T)//先序建立二叉树
{
 char ch;
 cin>>ch;
 if(ch=='#')T=NULL;
 else
 {
  T=new BiTNode;
  T->data=ch;
  CreateBiTree(T->lchild);
  CreateBiTree(T->rchild);
 }
}

#define MAXQSIZE 100
#define QElemType BiTNode*
typedef struct
{
 QElemType *base;
 int front;
 int rear;
}SqQueue;  //队列的顺序存储结构(循环队列)

bool InitQueue(SqQueue &Q) //循环队列初始化
{
  Q.base=new QElemType[MAXQSIZE];
  if(!Q.base)exit(EOVERFLOW);
  Q.front=Q.rear=0;
  return true;
}

int QueueLength(SqQueue Q) //求循环队列的长度
{
  return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

bool EnQueue(SqQueue &Q,QElemType e) //入队操作
{
  if((Q.rear+1)%MAXQSIZE==Q.front)return false;
  Q.base[Q.rear]=e;
  Q.rear=(Q.rear+1)%MAXQSIZE;
  return true;
}

bool DeQueue(SqQueue &Q,QElemType &e) //出队操作
{
  if(Q.front==Q.rear)return false;
  e=Q.base[Q.front];
  Q.front=(Q.front+1)%MAXQSIZE;
  return true;
}

int DepthTree(BiTree &T)//用非递归的方法求出二叉树的高度，即为本题解答
{
  SqQueue Q;
  InitQueue(Q);
  int high=0;
  BiTNode* p=T;
  QElemType e;
  
  if(p)EnQueue(Q,p);
  
  while(Q.front!=Q.rear)
  {
    high++;
    int length=QueueLength(Q);
    for(int i=0;i<length;i++)
    {
       DeQueue(Q,e);
       if(e->lchild)EnQueue(Q,e->lchild);
       if(e->rchild)EnQueue(Q,e->rchild);
    }
  }
  delete Q.base;
  Q.base=NULL;
  return high;
}

void DestroyTree(BiTree &T)//销毁二叉树
{
 if(T!=NULL)
 {
  DestroyTree(T->lchild);
  DestroyTree(T->rchild);
  printf("销毁结点: %c\n",T->data);
  delete T;
  T=NULL; 
 }
 return;
}


int main()
{
  BiTree T=NULL;
  printf("先序建立二叉树:\n");
  CreateBiTree(T);
  printf("\n此二叉树深度为:\n%d\n",DepthTree(T));
  DestroyTree(T);//销毁二叉树
  printf("\n成功销毁二叉树!\n");
  return 0; 
}

我的算法思想：利用队列实现非递归，首先将每一层所有结点的地址作为元素入队，之后逐个出队并将其左右孩子入队，直到队列中都是下一层的元素，上述操作大多是在函数中的while循环内完成的（祖先结点地址入队除外），而在循环的一开始首先要判读队列是否为空，如果不为空表明队列中加入了新的一层，那么层数就要加一，最后的层数即为树的高度。

给出后一种非递归算法的运行截图：