二叉树的遍历-中序遍历非递归算法-蒲公英云

二叉树的遍历-中序遍历非递归算法

r囧r小猫 2022-05-26 11:00 245阅读 0赞

中序遍历的几种情况

分析1：什么时候访问根、什么时候访问左子树、什么访问右子树

   当左子树为空或者左子树已经访问完毕以后，再访问根
   访问完毕根以后，再访问右子树。

分析2：为什么是栈，而不是其他队列。

    先走到的后访问、后走到的先访问，显然是栈结构

分析3：结点所有路径情况

步骤1：结点的所有路径情况

如果结点有左子树，该结点入栈；

如果结点没有左子树，访问该结点；

分析3：路径所有情况

如果结点有右子树，重复步骤1；

如果结点没有右子树（结点访问完毕），回退，让栈顶元素出栈，访问栈顶元素，并访问右子树，重复步骤1

如果栈为空，表示遍历结束。

注意：入栈的结点表示，本身没有被访问过，同时右子树也没有被访问过。

分析4：有一个一直往左走入栈的操作

我的理解：先遍历到结点B，发现B没有左子树，故访问B,打印B;接着遍历看B的右子树，发现结点C，有左子树D，故C入栈，继续遍历D,发现结点D没有左子树，故访问D,打印D,接着发现结点D没有右子树，回退，让栈顶元素出栈，此时栈中有C，出栈，打印出来C,回退遍历到结点A,A有右子树，遍历结点E,E结点没有左子树，访问E,打印出来，E有右子树，遍历到F结点，F结点有左子树G,故F入栈，接着遍历到G结点，发现G有左子树H结点，故G入栈，遍历到H结点，H没有左子树，故访问H,打印出来H,H没有有右子树，回退，让栈顶元素出栈，也就是G。遍历I结点，因为I没有左子树，故访问I,打印出来I结点，I没有右子树，回退，让栈顶元素出栈，也就是F,栈中为NULL,表示遍历结束

#include <iostream>
using namespace std;
#include "stack"
//二叉链表示法
typedef struct BiTNode
{
    char data;//数据域
    struct BiTNode *lchild;//指针域,存放指向左孩子的指针
    struct BiTNode *rchild;//指针域,存放指向右孩子的指针
}BiTNode, *BiTree;
/*
步骤1：
如果结点有左子树，该结点入栈；
如果结点没有左子树，访问该结点；
步骤2：
如果结点有右子树，重复步骤1；
如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
如果栈为空，表示遍历结束。
*/
//一直往左边走,找到中序遍历的起点
BiTNode *goLeft(BiTNode *T, stack<BiTNode *> &s)
{
    if (NULL == T)
    {
        return NULL;
    }
    //判断T有没有左孩子,没有把T 返回
    //有,T入栈
    while (T->lchild !=NULL)
    {
        s.push(T);
        T = T->lchild;
    }
    return T;
}
void Inorder2(BiTNode *T)
{
    BiTNode *t = NULL;
    stack<BiTNode *> s;
    t = goLeft(T,s);
    while (t)
    {
        //如果结点没有左子树，访问该结点；打印该结点数据
        printf("%c ", t->data); 
        //如果t 有右子树 重复步骤1
        if (t->rchild !=NULL)
        {
            t = goLeft(t->rchild,s);//右子树中中序遍历的起点
        }
        else if (!s.empty())//如果t没有右子树 根据栈顶指示 回退
        {
            t = s.top();//获得栈顶元素
            s.pop();//将其弹出
        }
        else//如果t没有右子树 并且栈为空 
        {
            t = NULL;
        }
    }
}
void inOrder(BiTNode *root)
{
    if (root == NULL)
    {
        return;
    }
    //遍历左子树
    inOrder(root->lchild);
    printf("%c ", root->data);
    //遍历右子树
    inOrder(root->rchild);
}
void main()
{
    BiTNode A, B, C, D, E, F, G, H, I;
    memset(&A, 0, sizeof(BiTNode));
    memset(&B, 0, sizeof(BiTNode));
    memset(&C, 0, sizeof(BiTNode));
    memset(&D, 0, sizeof(BiTNode));
    memset(&E, 0, sizeof(BiTNode));
    memset(&F, 0, sizeof(BiTNode));
    memset(&G, 0, sizeof(BiTNode));
    memset(&H, 0, sizeof(BiTNode));
    memset(&I, 0, sizeof(BiTNode));
    A.data = 'A';
    B.data = 'B';
    C.data = 'C';
    D.data = 'D';
    E.data = 'E';
    F.data = 'F';
    G.data = 'G';
    H.data = 'H';
    I.data = 'I';
    //建立关系
    A.lchild = &B;
    A.rchild = &E;
    E.rchild = &F;
    F.lchild = &G;
    G.lchild = &H;
    G.rchild = &I;
    B.rchild = &C;
    C.lchild = &D;
    printf("\nolder inorder\n");
    inOrder(&A);
    printf("\n 非递归遍历\n");
    Inorder2(&A);
    printf("hello...\n");
    system("pause");
    return;
}