遍历二叉树(BiTree)

设计思想

递归    

1. 定义一个二叉树结点类型的结构体，创建一个二叉树，定义一个输入的数是字符型的，当ch为空时，T就为空值，否则的话就分配空间给T，T就指向它的结点，然后左指针域指向左孩子，右指针指向右孩子，若还有，继续调用,依次循环下去，直到ch遇到空时，结束。最后要返回建立的二叉树T。注：此程序按先序递归创建二叉树。
2. 先序遍历规则：当T为非空时，先访问根节点，之后访问左子树，再访问右子树，依次进行下去直到遍历结束。
3. 中序遍历规则：当T为非空时，先左指针指向左孩子数据，然后输出结点处的数据，再右指针指向右孩子，依次进行下去直到遍历结束。
4. 后序遍历规则：当T为非空时，先左指针指向左孩子，然后右指针指向右孩子，最后输出结点处的数据，依次进行下去直到遍历结束。  

非递归  

1. 跟递归遍历二叉树的前提一样，首先应该创建一个二叉树，同样使用先序递归的方式创建二叉树。
2. 然后是中序，先序，后序非递归遍历二叉树。
3. 先序非递归遍历二叉树的思想是：首先建立一个栈，P是遍历指针指向根节点，当栈不空或者p不空时循环，当P不为空的时候，入栈访问根节点，遍历左子树，否则将栈顶元素出栈，然后访问右子树。重复操作，直到栈为空。
4. 中序非递归遍历二叉树的思想是：首先是根节点压栈，当根节点的左子树不是空的时候，左子树压栈。直到左子树为空的时候，不再压栈。将栈顶元素出栈，访问栈顶元素，并将栈顶的右子树进栈。当右子树的左子树不是空的时候，左子树一直进栈，直到左子树为空，则不再进栈。重复上面的操作，直到栈空的时候。
5. 后序非递归遍历二叉树的思想：首先是根节点进栈，当根节点的左子树不为空的时候，左子树进栈，直到左为空的时候，左子树不再进栈。指针指向的是右子树，当右子树为空的时候，直接访问根节点。当右子树不为空的时候，则右子树的指针进栈，当右子树的左子树不为空的时候，则左也进栈，直到左为空。重复上面的操作，直到栈为空的时候，则遍历树完成。

算法流程图

按先序序列创建二叉树流程图

按先序序列创建二叉树流程图.png

先序遍历(递归)流程图

先序遍历(递归)流程图.png

中序遍历(递归)流程图

中序遍历(递归)流程图.png

后序遍历(递归)流程图

后序遍历(递归)流程图.png

先序遍历(非递归)流程图

先序遍历(非递归)流程图.png

中序遍历(非递归)流程图

中序遍历(非递归)流程图.png

后序遍历(非递归)流程图

后序遍历(非递归)流程图.png

凹入法打印流程图

凹入法打印流程图.png

源代码

#include<iostream>
#include<stack>
#include<queue>
//封装好的栈和队列
using namespace std;

//二叉树结点
typedef struct BiTNode
{
    char data;  //数据
    struct BiTNode *lchild,*rchild;  //左右孩子指针
} BiTNode,*BiTree;

/********************** CreateBiTree 按先序序列创建二叉树**********************/
int CreateBiTree(BiTree &T)
{
    char data;
    //必须按先序次序输入二叉树中结点的值（一个字符），"#"表示空树
    scanf("%c",&data);
    if(data == '#')
    {
        T = NULL;     //加#是为了识别出#的双亲节点是叶子节点  也是递归的结束条件
    }
    else
    {
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = data;  //生成根结点
        CreateBiTree(T->lchild);  //递归构造左子树
        CreateBiTree(T->rchild);  //递归构造右子树
    }
    return 0;
}
/********************** Visit 输出**********************/
void Visit(BiTree T)
{
    if(T->data != '#')
    {
        printf("%c ",T->data);
    }
}
//先序遍历(递  归)
void PreOrderByRrecur(BiTree T)
{
    if(T != NULL)   // T = NULL 为递归的结束条件（叶子节点）
    {
        //访问根节点
        Visit(T);
        //访问左子结点
        PreOrderByRrecur(T->lchild);
        //访问右子结点
        PreOrderByRrecur(T->rchild);
    }
}
//中序遍历(递  归)
void InOrderByRrecur(BiTree T)
{
    if(T != NULL)
    {
        //访问左子结点
        InOrderByRrecur(T->lchild);
        //访问根节点
        Visit(T);
        //访问右子结点
        InOrderByRrecur(T->rchild);
    }
}
//后序遍历(递  归)
void PostOrderByRrecur(BiTree T)
{
    if(T != NULL)
    {
        //访问左子结点
        PostOrderByRrecur(T->lchild);
        //访问右子结点
        PostOrderByRrecur(T->rchild);
        //访问根节点
        Visit(T);
    }
}
//凹入法打印
void BiTreeHelp(BiTNode *T,string ss)
{
    if(T != NULL)
    {
        ss+="     ";
        BiTreeHelp(T->rchild,ss);
        cout<<ss<<T->data<<endl;
        BiTreeHelp(T->lchild,ss);
    }
}
/* 先序遍历(非递归)
   思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为当前T，出栈，再先序遍历T的右子树。
*/
void PreOrder(BiTree T)
{
    stack<BiTree> stack;
    //p是遍历指针
    BiTree p = T;
    //栈不空或者p不空时循环
    while(p || !stack.empty())
    {
        if(p != NULL)
        {
            //存入栈中
            stack.push(p);
            //访问根节点
            printf("%c ",p->data);
            //遍历左子树
            p = p->lchild;
        }
        else
        {
            //退栈
            p = stack.top();
            stack.pop();
            //访问右子树
            p = p->rchild;
        }
    }//while
}
/* 中序遍历(非递归)
   思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
         先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
*/
void InOrder(BiTree T)
{
    stack<BiTree> stack;
    //p是遍历指针
    BiTree p = T;
    //栈不空或者p不空时循环
    while(p || !stack.empty())
    {
        if(p != NULL)
        {
            //存入栈中
            stack.push(p);
            //遍历左子树
            p = p->lchild;
        }
        else
        {
            //退栈，访问根节点
            p = stack.top();
            printf("%c ",p->data);
            stack.pop();
            //访问右子树
            p = p->rchild;
        }
    }//while
}

//后序遍历定义的带标志的节点
typedef struct BiTNodePost
{
    BiTree biTree;  //树节点
    char tag;    //标志
} BiTNodePost,*BiTreePost;

//后序遍历(非递归)
void PostOrder(BiTree T)
{
    stack<BiTreePost> stack;
    //p是遍历指针
    BiTree p = T;
    BiTreePost BT;
    //栈不空或者p不空时循环
    while(p != NULL || !stack.empty())
    {
        //P不为空则遍历左子树
        while(p != NULL)
        {
            BT = (BiTreePost)malloc(sizeof(BiTNodePost));
            BT->biTree = p;
            //访问过左子树
            BT->tag = 'L';
            stack.push(BT);
            p = p->lchild;
        }
        //左右子树访问完毕（栈不为空且tag=R 【即左右子树已经访问过】）访问根节点
        while(!stack.empty() && (stack.top())->tag == 'R')
        {
            BT = stack.top();
            //退栈
            stack.pop();
            printf("%c ",BT->biTree->data);
        }
        //栈不为空遍历右子树
        if(!stack.empty())
        {
            BT = stack.top();
            //访问过右子树
            BT->tag = 'R';
            p = BT->biTree;
            p = p->rchild;
        }
    }//while
}
  
int main()
{
    BiTree T;
    printf("Waiting：");
    CreateBiTree(T);
    printf("先序遍历(递  归)：");
    PreOrderByRrecur(T);
    printf("\n");
    printf("先序遍历(非递归)：");
    PreOrder(T);
    printf("\n");
    printf("中序遍历(递  归)：");
    InOrderByRrecur(T);
    printf("\n");
    printf("中序遍历(非递归)：");
    InOrder(T);
    printf("\n");
    printf("后序遍历(递  归)：");
    PostOrderByRrecur(T);
    printf("\n");
    printf("后序遍历(非递归)：");
    PostOrder(T);
    printf("\n");
    printf("凹入法打印：");
    printf("\n");
    BiTreeHelp(T,"");
    printf("\n");
    system("pause");
    return 0;
}

运行结果

递归与非递归的先序、中序、后序遍历二叉树的运行结果.png

遇到的问题及解决

问题1：由于后续遍历又本身的特殊性，左子树，右子树，中间节点这样的一个顺序，如果分开保存左子树和右子树，那么在遍历右子树后会丢失掉上次现场保留的中间节点，如果要像中序遍历一样的方法保存的话，那么每次弹出后遍历右节点也会丢失上次现场保留的中间节点。

解决方法：通过一个创建一个带标志的结点，在每次压栈的时候都给树标记下，由于都是先访问左子树，再访问右子树，也就是说每棵树都是访问两次。那么就可以通过判断树的标志而实现此时是否遍历左节点和右节点完成，从而输出中间节点。如下所示：

typedef struct BiTNodePost{  

    BiTree biTree;   

    char tag;    //标志  tag=L则访问过左子树   tag=R则访问过右子树，可以出栈打印根节点了

}BiTNodePost,*BiTreePost;

问题2：创建树的时候，根节点的左右子树可能有为空的时候，遇到的问题是编程时候，当遇到 空子树的时候没有做任何的操作，导致遍历树的时候出错。

解决方法：当遇到空子树时，将结点等于“#”。如下所示：

if(data == '#'){  

  T = NULL;    

  }

问题3：编写程序时有时候会出现编译错误。

解决方法：根据编译器错误提示进行改正。

问题4：编写程序时在思考非递归后序遍历二叉树时候不知道怎么正确实现，因为后序遍历规则是访问左子树再访问右子树最后访问根节点，应当如何解决途中经过根节点问题。

解决方法：根据课上学到的知识和浏览网络学习后序算法总结算法逻辑，结合所学到的编写程序并调试看是否正确。