本文共 2867 字，大约阅读时间需要 9 分钟。

二叉树的基本操作

• 编程实现二叉树的先序、中序、后序和层序遍历
• 编程实现非递归中序遍历
• 编程实现：求二叉树的高度和叶子结点个数

代码如下：

#include 
   
    using namespace std;typedef struct BiTNode{       char data;    struct BiTNode *lchild,*rchild;} BiTNode,*BiTree;typedef struct StackNode{       BiTree data;    struct StackNode *next;}StackNode,*LinkStack;int idx = 0;//创建二叉树void CreateBiTree(BiTree &T,char *treeSeq){       if(treeSeq[idx]=='#')    {           T=NULL;        ++idx;    }    else    {           T=new BiTNode;        T->data=treeSeq[idx++];        CreateBiTree(T->lchild,treeSeq);	//递归创建左子树        CreateBiTree(T->rchild,treeSeq);	//递归创建右子树    }}//前序遍历void PreOrderTraverse(BiTree T){       if(T)    {           cout<
    
     data;        PreOrderTraverse(T->lchild);        PreOrderTraverse(T->rchild);    }}//中序遍历void InOrderTraverse(BiTree T){       if(T)    {           InOrderTraverse(T->lchild);        cout<
     
      data;        InOrderTraverse(T->rchild);    }}//后序遍历void PostOrderTraverse(BiTree T){       if(T)    {           PostOrderTraverse(T->lchild);        PostOrderTraverse(T->rchild);        cout<
      
       data;    }}//层序遍历void LevelOrderTraverse(BiTree T){       int i,j;    BiTree p[100];    i = j = 0;    if (T)        p[j++] = T;    while(i
       
        data;        if (p[i]->lchild)            p[j++] = p[i]->lchild;        if (p[i]->rchild)            p[j++] = p[i]->rchild;        i++;    }}//销毁二叉树void DestroyBiTree(BiTree &T){       if(T)    {           DestroyBiTree(T->lchild);        DestroyBiTree(T->rchild);        delete T;    }}//求二叉树结点总数int NodeCount(BiTree T){       if(T == NULL )        return 0;    else        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;}//求叶子结点的个数int LeafCount(BiTree T){       if(T==NULL) 	//如果是空树返回0        return 0;    if (T->lchild == NULL && T->rchild == NULL)        return 1; //如果是叶子结点返回1    else        return LeafCount(T->lchild) + LeafCount(T->rchild);}//求二叉树的深度int Depth(BiTree T){       if (T==NULL)        return 0;    else    {           int m=Depth(T->lchild);        int n=Depth(T->rchild);        if (m>=n)            return m+1;        else            return n+1;    }}void Push(LinkStack &S,BiTree p){       StackNode *q = new StackNode;    q->data = p;    q->next = S;    S = q;}bool Pop(LinkStack &S,BiTree &p){       if (S==NULL)        return false;    p = S->data;    StackNode *q = S;    S = S->next;    delete q;    return true;}//非递归中序遍历void InOrderTraverse_NonRecursive ( BiTree T){       LinkStack S = NULL;    BiTree p=T;    BiTree q;    while ( p || S!=NULL )    {           if ( p)        {               Push( S, p );            p=p->lchild ;//根指针进栈，遍历左子树        }        else        {               Pop( S, q ); // 退栈            cout<
        
         data;//访问根结点 p=q->rchild;//遍历右子树 } }}int main(){ char treeSeq[20]="ABC##DE#G##F###"; BiTree T; CreateBiTree(T,treeSeq); cout<<"前序遍历："; PreOrderTraverse(T); cout<