数据结构_二叉树的遍历/线索二叉树

原始头文件和一些其中会用到的函数

//
// Created by XuYiMing on 2020/3/2.
//

#include <iostream>
#include <stack>
#include <queue>

#define MaxSize 100

using namespace std;
typedef int ElemType;

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

ElemType visit(BiTree T) {
    return T->data;
}

二叉树遍历方法

用递归方法解决遍历问题

//先序遍历
void PreOrder(BiTree T) {
    if (T != nullptr) {
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历
void InOrder(BiTree T) {
    if (T != nullptr) {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

//后序遍历
void PostOrder(BiTree T) {
    if (T != nullptr) {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

//层次遍历
void LevelOrder(BiTree T) {
    queue<BiTree> q;
    BiTree p = T;
    q.push(T);
    while (!q.empty()) {
        q.pop();
        visit(p);
        if (p->lchild != nullptr)
            q.push(p->lchild);
        else if (p->rchild != nullptr)
            q.push(p->rchild);
    }
}

用非递归方法解决遍历问题

//先序遍历非递归算法
void PreOrder2(BiTree T) {
    stack<int> s;
    BiTree p = T;
    while (p != nullptr || !s.empty()) {
        if (p) {
            visit(p);
            s.push(p->data);
            p = p->lchild;
        } else {
            s.pop();
            p = p->rchild;
        }
    }
}

//中序遍历非递归算法
void InOrder2(BiTree T) {
    stack<int> s;
    BiTree p = T;
    while (p != nullptr || !s.empty()) {
        if (p) {
            s.push(p->data);
            p = p->lchild;
        } else {
            s.pop();
            visit(p);
            p = p->rchild;
        }
    }
}

//后序遍历非递归算法
void PostOrder2(BiTree T) {
    stack<BiTree> s;
    BiTree p = T;
    //r为辅助指针，用于指向最近访问过的结点
    BiTree r = nullptr;
    while (p || !s.empty()) {
        //走到最左边，找到后序遍历的第一个结点
        if (p) {
            s.push(p);
            p = p->lchild;
        } else {
            //读取栈顶结点
            p = s.top();
            //右子节点存在且未被访问过
            if (p->rchild && p->rchild != r) {
                p = p->rchild;
                s.push(p);
                p = p->lchild;
            } else {
                //否则从栈中弹出还未被访问的结点
                s.pop();
                visit(p);
                //把r指向该节点已被访问
                r = p;
                //每次出栈访问完一个结点都是该结点的子树，需将p置null
                p = nullptr;
            }
        }
    }
}

线索二叉树

//线索二叉树的存储结构
typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;
    //tag为0表示孩子，为1表示前驱/后继
} ThreadNode, *ThreadTree;

//中序线索二叉树的递归算法
void InThread(ThreadTree &p, ThreadTree &pre) {
    if (p != nullptr) {
        //递归线索化左子树
        InThread(p->lchild, pre);
        if (p->lchild == nullptr) {
            p->lchild = pre;
            p->ltag = 1;
        }
        //建立前驱结点的后继线索
        if (pre != nullptr && pre->rchild == nullptr) {
            pre->rchild = p;
            pre->rtag = 1;
        }
        pre = p;
        InThread(pre->rchild, pre);
    }
}

//建立中序线索二叉树的过程
void CreateInThread(ThreadTree T) {
    ThreadTree pre = nullptr;
    if (T != nullptr) {
        //线索化二叉树
        InThread(T, pre);
        //处理遍历后的最后一个结点
        pre->rchild = nullptr;
        pre->rtag = 1;
    }
}