首页 大杂烩正文

二叉树中序遍历、中序遍历、后序遍历迭代以及非递归算法介绍以及代码结合

原创
小哥 3年前 (2022-11-16) 阅读数 10 #大杂烩

引文

因为某些书籍上对这类算法，写的非常笼统，所以，这里将从树的链式存储开始，结合整个 链表、栈、队列等结构来完成对树的学习，当然，这里也将会完美的列出所用的栈、队列等结构，直接复制代码即可运行。
说明：下面代码 在定义的时候可能不会遵循一般的编程规范，比如这些愚蠢的结构体的名字(因为这就是为了考试用的)。请已经工作了的童鞋理解(虽然我自己都非常想吐槽)

文章目录

二叉树的链式存储结构体

#include 
#include 
#define MaxSize 50
typedef int ElemType;

//链式存储二叉树
typedef struct BiTNode{
    ElemType  data;
    struct BiTNode *lchild,* rchild;
} BiTNode,*BiTree;

上面的代码应该非常好理解，typdef所声明的结构体，BiTree是个指针类型，这里只是为了某些考试中方便指代。来区分，结点的创建以及整个树的传递。

构建一颗普通的二叉树

这部分代码在考试中是基本用不上的，但是为了方便代码执行，所以，这里给出以层序遍历形式来构建一颗二叉树，我这里代码就简单化了，只是在以层序遍历形式给二叉树来添加结点的基础上加了循环。
在构建之前，我们要用到层序遍历，这个意思就是从上往下，从左往右遍历一颗二叉树罢了，我们要用的是他的思想。
首先死记忆，它需要用到队列。因此，我们需要重新定义出来队列的结构体，以及入队和出队的操作。请跟着写一遍。

下面会使用循环队列，如果这个简单的数据结构不清楚，那。。请百度。
有很多人好奇c++这个传值，SqQueue &Q，我建议某些考试，直接是用&这个符号，就是按照引用传递，比如我修改Q的内容，那么，在上一级的函数中的Q也会修改。

队列结构体

//构建顺序队列结构体
typedef struct{
    BiTree data[MaxSize];
    int front,rear;
} SqQueue;

初始化队列以及入队出队

void initQueue(SqQueue &Q){
    Q.front =0;
    Q.rear =0;
}
//判断队列是否为空
bool isEmpty(SqQueue &Q){
    return Q.rear==Q.front;
}
//入队
bool enQueue(SqQueue &Q,BiTree & value){
    if((Q.rear+1)%MaxSize == Q.front){
        return false;
    }
    Q.data[Q.rear] = value;
    Q.rear = (Q.rear+1)%MaxSize;
    return true;
}
//出队
bool deQueue(SqQueue &Q,BiTree &value){
    if(Q.rear==Q.front){
        return false;
    }
    value = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return true;
}

给一颗二叉树添加结点(层序)

添加思想：准备一个队列，参数传递一颗二叉树，根结点入队，然后进入循环：
队中结点出队
判断该结点是否有左孩纸
有则直接入队
无则说明这个结点的左孩纸可以添加元素了，直接添加结点，添加之后直接跳出
判断该结点是否有右孩纸
有则直接入队
无则说明这个结点的右孩纸可以添加元素了，直接添加结点，添加之后直接跳出

直到队中无结点。 可以想象一下，是用队列保证了我们的层序性，必然是按照从上往下，从左到右，然后只需要判断，当前出队结点是否有左右孩纸即可找到我们需要插入的位置。

//给一个二叉树以层序遍历的方式插入结点
void addNode(BiTree &T,ElemType value){

    BiTree innerTree = NULL;
    BiTNode *node = (BiTNode *) malloc(sizeof(BiTNode));
    node->data = value;
    node->lchild = NULL;
    node->rchild = NULL;
    if(T==NULL){
        T = node;
        return;
    }
    SqQueue Q;
    initQueue(Q);
    enQueue(Q,T);
    while (deQueue(Q,innerTree)){
        if(innerTree->lchild!=NULL){
            enQueue(Q,innerTree->lchild);
        } else{
            innerTree->lchild = node;
            break;
        }
        if(innerTree->rchild!=NULL){
            enQueue(Q,innerTree->rchild);
        } else{
            innerTree->rchild = node;
            break;
        }
    }
}

开始构建二叉树

有了添加结点，那么构建将会变得无比简单

BiTree initBiTree(ElemType value[],int n){
    BiTree T =NULL;
    for (int i=0;idata);
        if(innerTree->lchild!=NULL){
            enQueue(Q,innerTree->lchild);
        }
        if(innerTree->rchild!=NULL){
            enQueue(Q,innerTree->rchild);
        }
    }
    printf("

"); }

我们将其让main函数调用

int main(){
    BiTree T = getBiTree();
    printTree(T);
    printf("

");

    return 0;
}

调用之后，看到结果

1 2 3 4 5 6 7 8 9

前序遍历(递归和非递归)

栈

在学习前序非递归之前，还要构建一个栈。这里一样使用顺序栈，方便些。

//------------------栈开始------------
//是用顺序栈
typedef struct{
    BiTree data[MaxSize];
    int top;
} SqStack;
//初始化
void initSqStack(SqStack &Stack){
    Stack.top = -1;
}
bool isEmpty(SqStack &Stack){
    return Stack.top==-1;
}

//入栈
bool push(SqStack &Stack,BiTree& T){
    if(Stack.top==MaxSize-1){
        return false;
    }
    Stack.data[++Stack.top] = T;
    return true;
}

//出栈
bool pop(SqStack &Stack,BiTree& T){
    if(Stack.top==-1){
        return false;
    }
    T = Stack.data[Stack.top--];
    return true;
}
//获取栈顶元素
bool getStackTop(SqStack &Stack,BiTree &T){
    if(Stack.top==-1){
        return false;
    }
    T = Stack.data[Stack.top];
    return true;
}

//---------------栈结束---------------

前序非递归

我从非递归讲起，感觉更容易理解递归
首先，什么是前序遍历
前序遍历：根 左 右
先访问根结点，然后 左孩纸，然后右 孩纸
比如下面这个，前序遍历的结果就是：
A B D F G H I E C

非递归算法需要树的遍历中(除了层序)基本要用到栈的思想，因为都采用 深度遍历的思想。

下面使用一个基本的例子来进行构建
就拿 1 2 3 4 5 6 7 8 9这个二叉树
前序遍历的结果应该是
1 2 4 8 9 5 3 6 7

前序遍历 先访问这个根结点，如果这个根结点有左孩纸的话就访问左孩纸(相当于左子树了)，左子树访问完成，就访问右子树了，一层一层过。然思考一下是用栈的思想。
思路：
我们需要一个指针p去保存当前访问结点，需要一个栈去保存访问信息。
当p不为空时，那么就访问这个p，然后将其入栈。令 p指向p的左孩纸。
否则，直接出栈，然后令p 指向这个出栈结点的右孩纸。
这样就能满足先访问根结点，然后访问左孩纸，最后访问右。
如果还不能理解这种题目最简单的方式是是拿最简单的例子然后穷举。在明确是用栈的情况下，看下面这个例子

明确使用栈，我们必须要一个工作指针p去存放变量，这个p在一开始的时候指向这个树的根。然后这种围绕着栈的算法，必然又是一个while（栈不是空）这种条件，一开始这个栈是空，为了进入循环，那么得加上while(栈不是空 || p!=NULL)。至于循环中的内容。
一开始p指向根(这里p指向1)，必然有两种结果 一个是 p!=NULL一个是 p==NULL
1.p!=NULL的话，为了满足根左右，直接访问。1结点被访问。然后入栈，然后必然要改变p的指向，因为是根左右，所以必然指向左边， p = p->lchild。此时p指向2。然后进入下一次循环，重复1步骤，会导致访问了2，2入栈。 p = p->lchild。此时p 已经指向了空，因为2没有左孩纸。继续下次循环， p==NULL 了。
2.p==NULL的话，我们要看p的双亲结点(栈顶元素2)是否有右孩纸，有的话也需要入栈，但是这个右孩纸可能是一个子树，是一个新的二叉树，所以呢，干脆，利用p!=NULL那段代码去解决就好了，将这个右孩纸当成根结点就好啦。于是，只要我们弹出这个2(2已经被访问了，没有价值了)，然后将p指向它。等着下一步跑到1步骤就完事啦。
此时 p还是指向NULL,哈哈。会继续走步骤2，然后栈顶元素1出栈，p 指向了1的右孩纸3。然后进入步骤1 ，p 指向了3的左孩纸NULL，栈顶元素是3，然后继续循环走向步骤2，弹出了栈顶3，p指向了3的右孩纸NULL，此时 栈空并且p也是NULL啦，跳出循环。结束遍历。

//非递归算法 前序遍历
void preOrder2(BiTree T){
    SqStack Stack;
    initSqStack(Stack);
    BiTNode * p = T;
    while (p!=NULL||!isEmpty(Stack)){
        if(p!=NULL){
            printf("%d ",p->data);
            push(Stack,p);
            p = p->lchild;
        } else{
            pop(Stack,p);
            p = p->rchild;
        }
    }
}

前序递归

凡是递归的题目，非常简单。
首先，确定递归的最后一个层级，也就是递归的边界条件。前序无非就是 根 左 右。
从根结点开始，访问自己，然后直接左孩纸调用自己(也就是入栈)，等到左孩纸为空了，那么自然应该返回，然后接着右孩纸入栈。因此，递归的边界条件是这个结点不为空。代码如下：

void preOrder(BiTree T){
    if(T!=NULL){
        printf("%d ",T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

中序递归和非递归

中序非递归

中序非递归算法和前序基本一致，换了下访问的顺序罢了，中序是 左 根 右，只需要在 左孩纸全部入栈的时候 也就是弹栈的时候开始访问就好了。
代码如下：

//非递归算法中序遍历
void inOrder2(BiTree &T){
    SqStack Stack;
    initSqStack(Stack);
    BiTNode * p = T;
    while (p!=NULL || !isEmpty(Stack)){
        if(p!=NULL){
            push(Stack,p);
            p = p->lchild;
        } else{
            pop(Stack,p);
            printf("%d ",p->data);
            p =p->rchild;
        }
    }
}

中序递归

中序递归算法更简单了，在此不再叙述。

//-----中序遍历------
void inOrder(BiTree &T){
    if(T!=NULL){
        inOrder(T->lchild);
        printf("%d ",T->data);
        inOrder(T->rchild);
    }
}

后序递归和非递归

后序非递归

后序非递归算法有点不同，我借用王道上的一句话，然后进行补充：
后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。后序遍历的非递归实现是三种遍历方法中最难的。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。
后序非递归遍历算法的思路分析:从根结点开始,将其入栈，然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点，但是此时不能出栈并访问，因为如果其有右子树，还需按相同的规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空，要么右子树刚被访问完（此时左子树早己访问完)，这样就保证了正确的访问顺序。

王道上面这样说，没问题，我们在前序遍历的基础上对代码进行改进，假如这个右子树已经访问完了，再后面此时我们需要访问的是根结点，但是，我们把工作指针p指向这个根结点，我们也完全不清楚这个根结点的右孩纸有木有访问过，所以必须使用另外一个指针r,去保存这个右孩纸，如果p->rchild!=r的时候，就代表这个右孩纸没有被访问。

因此就衍生出了下面的逻辑：

算法思想:后序非递归遍历二叉树是先访问左子树，再访问右子树，最后访问根结点。结合图5.7来分析:沿着根的左孩子，依次入栈，直到左孩子为空。此时栈内元素依次为AB D。读栈顶元素:若其右孩子不空且未被访问过，将右子树转执行①;否则，栈顶元素出栈并访问。栈顶D的右孩子为空，出栈并访问，它是后序序列的第一个结点;栈顶B的右孩子不空且未被访问过，E入栈，栈顶E的左右孩子均为空,出栈并访问;栈顶B的右孩子不空但已被访问，B出栈并访问;栈顶A的右孩子不空且未被访问过,C入栈。栈顶C的左右孩子均为空，出栈并访问;栈顶A的右孩子不空但已被访问，A出栈并访问。由此得到后序序列DEBCA。

算法思想:后序非递归遍历二叉树是先访问左子树，再访问右子树，最后访问根结点。结合图5.7来分析:沿着根的左孩子，依次入栈，直到左孩子为空。此时栈内元素依次为AB D。读栈顶元素:若其右孩子不空且未被访问过，将右子树转执行①;否则，栈顶元素出栈并访问。栈顶D的右孩子为空，出栈并访问，它是后序序列的第一个结点;栈顶B的右孩子不空且未被访问过，E入栈，栈顶E的左右孩子均为空,出栈并访问;栈顶B的右孩子不空但已被访问，B出栈并访问;栈顶A的右孩子不空且未被访问过,C入栈。栈顶C的左右孩子均为空，出栈并访问;栈顶A的右孩子不空但已被访问，A出栈并访问。由此得到后序序列DEBCA。
得到代码

//非递归后序遍历
void postOrder2(BiTree& T){
    SqStack Stack;
    initSqStack(Stack);
    BiTNode * p = T,*r =NULL;
    while (p!=NULL||!isEmpty(Stack)){
        if(p!=NULL){
            push(Stack,p);
            p = p->lchild;
        } else{
            getStackTop(Stack,p);
            if(p->rchild!=NULL&&p->rchild!=r){
                p =  p->rchild;
            } else{
                //访问结点
                pop(Stack,p);
                printf("%d ",p->data);
                r = p;
                p=NULL;
            }
        }
    }
}

后序递归

后序递归就简单了

void postOrder(BiTree& T){
    if(T!=NULL){
        postOrder(T->lchild);
        postOrder(T->rchild);
        printf("%d ",T->data);
    }
}

所有代码

#include 
#include 
#define MaxSize 50
typedef int ElemType;

//构建顺序树
struct TreeNode{
    ElemType  value;
    bool isEmpty;
};
typedef TreeNode SqTree[MaxSize] ;

void initTreeFromZero(SqTree &T){
    for (int i =0;i

是否为空: "); for (int i =0;i<MaxSize;i++){ printf("%d ",T[i].isEmpty); } } void printTreeFromOne(SqTree &T){ printf("值为 :"); for (int i =1;i<MaxSize;i++){ printf("%d ",T[i].value); } printf(" 是否为空: "); for (int i =1;i<MaxSize;i++){ printf("%d ",T[i].isEmpty); } }

//链式存储二叉树
typedef struct BiTNode{
    ElemType  data;
    struct BiTNode *lchild,* rchild;
} BiTNode,*BiTree;

//--------------------------队列操作-----------------------

//构建顺序队列结构体
typedef struct{
    BiTree data[MaxSize];
    int front,rear;
} SqQueue;

void initQueue(SqQueue &Q){
    Q.front =0;
    Q.rear =0;
}

bool isEmpty(SqQueue &Q){
    return Q.rear==Q.front;
}
//入队
bool enQueue(SqQueue &Q,BiTree & value){
    if((Q.rear+1)%MaxSize == Q.front){
        return false;
    }
    Q.data[Q.rear] = value;
    Q.rear = (Q.rear+1)%MaxSize;
    return true;
}
//出队
bool deQueue(SqQueue &Q,BiTree &value){
    if(Q.rear==Q.front){
        return false;
    }
    value = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return true;
}

//------------------------队列操作结束-----------------------

//------------------栈开始------------
//是用顺序栈
typedef struct{
    BiTree data[MaxSize];
    int top;
} SqStack;
//初始化
void initSqStack(SqStack &Stack){
    Stack.top = -1;
}
bool isEmpty(SqStack &Stack){
    return Stack.top==-1;
}

//入栈
bool push(SqStack &Stack,BiTree& T){
    if(Stack.top==MaxSize-1){
        return false;
    }
    Stack.data[++Stack.top] = T;
    return true;
}

//出栈
bool pop(SqStack &Stack,BiTree& T){
    if(Stack.top==-1){
        return false;
    }
    T = Stack.data[Stack.top--];
    return true;
}
//获取栈顶元素
bool getStackTop(SqStack &Stack,BiTree &T){
    if(Stack.top==-1){
        return false;
    }
    T = Stack.data[Stack.top];
    return true;
}

//---------------栈结束---------------

void printTree(BiTree &T){
    //层序遍历方式
    SqQueue Q;
    initQueue(Q);
    enQueue(Q,T);
    BiTree innerTree = NULL;
    while (deQueue(Q,innerTree)){
        //访问
        printf("%d ",innerTree->data);
        if(innerTree->lchild!=NULL){
            enQueue(Q,innerTree->lchild);
        }
        if(innerTree->rchild!=NULL){
            enQueue(Q,innerTree->rchild);
        }
    }
    printf("

"); }

//给一个二叉树以层序遍历的方式插入结点
void addNode(BiTree &T,ElemType value){

    BiTree innerTree = NULL;
    BiTNode *node = (BiTNode *) malloc(sizeof(BiTNode));
    node->data = value;
    node->lchild = NULL;
    node->rchild = NULL;
    if(T==NULL){
        T = node;
        return;
    }
    SqQueue Q;
    initQueue(Q);
    enQueue(Q,T);
    while (deQueue(Q,innerTree)){
        if(innerTree->lchild!=NULL){
            enQueue(Q,innerTree->lchild);
        } else{
            innerTree->lchild = node;
            break;
        }
        if(innerTree->rchild!=NULL){
            enQueue(Q,innerTree->rchild);
        } else{
            innerTree->rchild = node;
            break;
        }
    }
}

BiTree initBiTree(ElemType value[],int n){
    BiTree T =NULL;
    for (int i=0;ij){
                i = (i-1)/2;
            } else{
                j = (j-1)/2;
            }
        }
        return i;
    }
}
void findCommonAncestorMain(){
    SqTree T;
    initTreeFromZero(T);
    printf("公共结点的序号是%d", findCommonAncestor(T,3,4));
}

//-----------------

//------------初始化二叉树 (以层序遍历的方式)-----------
BiTree getBiTree(){
    ElemType type[] = {1,2,3,4,5,6,7,8,9};
    BiTree T = initBiTree(type, sizeof(type) / sizeof(ElemType));
    return T;
}

//------ 前序遍历-----
//递归
void preOrder(BiTree T){
    if(T!=NULL){
        printf("%d ",T->data);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

//非递归算法 前序遍历
void preOrder2(BiTree T){
    SqStack Stack;
    initSqStack(Stack);
    BiTNode * p = T;
    while (p!=NULL||!isEmpty(Stack)){
        if(p!=NULL){
            printf("%d ",p->data);
            push(Stack,p);
            p = p->lchild;
        } else{
            pop(Stack,p);
            p = p->rchild;
        }
    }
}

//-----中序遍历------
void inOrder(BiTree &T){
    if(T!=NULL){
        inOrder(T->lchild);
        printf("%d ",T->data);
        inOrder(T->rchild);
    }
}

//非递归算法中序遍历
void inOrder2(BiTree &T){
    SqStack Stack;
    initSqStack(Stack);
    BiTNode * p = T;
    while (p!=NULL || !isEmpty(Stack)){
        if(p!=NULL){
            push(Stack,p);
            p = p->lchild;
        } else{
            pop(Stack,p);
            printf("%d ",p->data);
            p =p->rchild;
        }
    }
}

//-----后序遍历
//递归后序遍历
void postOrder(BiTree& T){
    if(T!=NULL){
        postOrder(T->lchild);
        postOrder(T->rchild);
        printf("%d ",T->data);
    }
}
//非递归后序遍历
void postOrder2(BiTree& T){
    SqStack Stack;
    initSqStack(Stack);
    BiTNode * p = T,*r =NULL;
    while (p!=NULL||!isEmpty(Stack)){
        if(p!=NULL){
            push(Stack,p);
            p = p->lchild;
        } else{
            getStackTop(Stack,p);
            if(p->rchild!=NULL&&p->rchild!=r){
                p =  p->rchild;
            } else{
                //访问结点
                pop(Stack,p);
                printf("%d ",p->data);
                r = p;
                p=NULL;
            }
        }
    }
}

//------层序遍历-----
void LevelOrder(BiTree &T){
    SqQueue Q;
    initQueue(Q);
    BiTNode * p = T;
    enQueue(Q,p);
    while (!isEmpty(Q)){
        deQueue(Q,p);
        printf("%d ",p->data);
        if(p->lchild!=NULL){
            enQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){
            enQueue(Q,p->rchild);
        }
    }
}

int main(){
    BiTree T = getBiTree();
    //前序
    preOrder(T);
    printf("

"); preOrder2(T); printf(" ");

    //中序
    inOrder(T);
    printf("

"); inOrder2(T); printf(" ");

    //后序
    postOrder(T);
    printf("

"); postOrder2(T); printf(" ");

    //层序
    LevelOrder(T);
    return 0;
}
版权声明

所有资源都来源于爬虫采集,如有侵权请联系我们,我们将立即删除

上一篇：C++编程分析(基于谭书第三版) 下一篇：蛛丝马迹二叉树中序可变返回类型线索化以及函数线索化构建和查找算法
相关文章
最新文章
标签列表
粤ICP备19068341号
所有资源都来源于爬虫采集,如有侵权请联系我们,我们将立即删除
Powered By Z-BlogPHP Theme By 编程老白