C++ 二叉树实现

2019-11-09 0 条评论 197 次阅读 0 人点赞

二叉树想必大家非常熟悉, 本文介绍的是如何实现一个二叉树类, 其功能包括前序、中序、后序遍历等, 以及一些经典题型的解析

直接亮代码主体结构:

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
using namespace std;

//namaspace防冲突
namespace km {

    //结点类
    template<typename T>
    class TreeNode {
        T m_val;
        TreeNode<T> *m_left;
        TreeNode<T> *m_right;
    public:
        TreeNode(const T & val)
            :m_val(val){

        }
        //友元类模板用同一个T会产生冲突, 所以在声明的时候改成U
        template<class U>
        friend class Tree;
    };

    //结点类
    template<class T>
    class Tree {
        TreeNode<T> *m_root;

        static TreeNode<T> * maketree(const T *val, const T & end, int &i){
            //遇到结束符 跳过该位置
            if (val[i] == end){
                i++;
                return nullptr;
            }

            TreeNode<T> * root = new TreeNode<T>(val[i]);
            i++;

            root->m_left = maketree(val, end, i);
            root->m_right = maketree(val, end, i);

            return root;
        }
    public:
        Tree() :
                m_root(nullptr) {
        }

        Tree(const T *val, const T &end) {
            int i = 0;
            //参数 (根节点,) 值, 结束符号, 下标
            m_root = maketree(val, end, i);
        }
    };
};
  • 前序、中序、后序遍历

    1. NLR:前序遍历(Preorder Traversal 亦称先序遍历):访问根结点的操作发生在遍历其左右子树之前。

借助栈完成
1. 打印当前节点
2. 如果有右孩子就将右孩子入栈
3. 如果有左孩子就访问左孩子, 没有就访问栈顶

//非递归遍历借助stack

        //前序遍历: 右孩子入栈-->进左孩子-->没有左孩子 去栈顶
        void pre_order(){
            TreeNode<T> * cur = m_root;
            stack<TreeNode<T> *> st;

            while (cur){
                cout << cur->m_val <<' ';
                if (cur->m_right){
                    st.push(cur->m_right);
                }
                if(cur->m_left){
                    cur = cur->m_left;
                } else {
                    if (st.empty()){
                        cur = nullptr;
                    } else {
                        cur = st.top();
                        st.pop();
                    }
                }
            }
//                return preOrder;
        }

2. LNR:中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。

借助栈完成
1.从当前节点开始遍历左子树, 将所有的节点入栈, 直到左子树为空
2. 取出并打印栈顶, 访问他的右孩子, 如果有有孩子, 重复步骤1; 如果没有右孩子, 重复步骤2

//中序遍历: 自己和左全入栈, 取栈顶, 打印栈顶, 右重复, 没右再取栈顶
        void in_order(){
            TreeNode<T> * cur = m_root;
            stack<TreeNode<T> *> st;

            while (cur || !st.empty()){
                for (; cur; cur = cur->m_left){
                    //cur与左孩子全部入栈
                    st.push(cur);
                }

                if(!st.empty()){//空了, 取栈顶
                    cur = st.top();
                    st.pop();
                    cout << cur->m_val << ' ';

                    cur = cur->m_right;
                }
            }
        }

3. LRN:后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

借助双栈完成
tag标记(左子树访问标记)用true和false来表示
1. 从当前节点开始遍历左子树, 将所有的节点入栈, 且清空tag标记, 直到左子树为空, 然后进入过程2
2. 访问栈顶, 置位它的tag标记, 访问它的右子树, 如果右子树存在, 重复过程1, 如果右子树不存在, 进入过程3
3.取出栈顶, 打印, 然后检测它的父节点tag是否也被置位, 如果是, 则一并打印, 直到找到第一个tag标记为被清空状态(true)的节点位置, 然后回到过程2.
tips:
如果是从过程1进入过程2, 那么意味着这个节点没有左子树, 所以tag要置位;如果是过程3进入过程2, 那么意味着这个节点的左子树已经访问完毕, 所以tag要置位。循环打印的原因是: 如果父亲节点的tag也被置位, 则意味着当前处理的是父亲节点的右子树, 所以左右子树都被处理完成, 自然就可以被打印了。

void post_order() {
            TreeNode<T> *cur = m_root;
            stack<TreeNode<T> *> st;
            stack<bool> tag;
            while (cur || !st.empty()){
                for (; cur; cur->m_left){
                    //每一个节点元素对应标签, 二者同步push, 同步pop
                    st.push(cur);
                    tag.push(false);
                }

                while (!st.empty() && tag.top()){
                    //tag.top()-->左子树访问标记被置位, 标记为true则该被打印
                    cur = st.top();
                    cout << cur->m_val <<' ';
                    st.pop();
                    tag.pop();

                    cur = nullptr;//最后出栈完毕将cur置空, 访问下一个节点或跳出循环
                }

                if(!st.empty()){
                    tag.top() = true;
                    cur = st.top();
                    cur = cur->m_right;
                }
            }
        }
  • 其他遍历题型

1. 两个节点最近公共祖先

//两个节点最近公共祖先
        //方法1: 利用后序遍历根最后出栈的特点
        TreeNode<T> * lowestCommonAncestor_post(TreeNode<T> * p, TreeNode<T> * q){
            TreeNode<T> * cur = m_root;
            stack<TreeNode<T> *> st;
            stack<bool> tag;

            stack<TreeNode<T> *> res1;
            stack<TreeNode<T> *> res2;

            while (cur || !st.empty()){
                for (; cur; cur = cur->m_left){
                    st.push(cur);
                    tag.push(false);
                }

                while (!st.empty() && tag.top()){
                    cur = st.top();
                    if (cur == p || cur == q){
                        if (res1.empty()){
                            res1 = st;
                        } else {
                            res2 = st;
                        }
                    }
                    st.pop();
                    tag.pop();

                    cur = nullptr;
                }

                if (!st.empty()){
                    tag.top() = true;
                    cur = st.top();
                    cur = cur->m_right;
                }
            }

            if (res1.size() < res2.size()){
                //保持res1比较大
                swap(res1, res2);
            }

            int i = res1.size() - res2.size();

            for (;i > 0; i--) {
                res1.pop();
                //用这样的方式让两个栈长度对齐
            }

            while (res1.top() != res2.top()){
                //都出栈
                res1.pop();
                res2.pop();
            }
            //找到公共祖先
            return res1.top();
        }

        //方法2 中序遍历做法: 以我为根的子树内包含两个节点
        //当子树内找到两个数, 计数为2时就找到了
        TreeNode<T> * lowestCommonAncestor_in(TreeNode<T> * p, TreeNode<T> * q){
            TreeNode<T> * cur = m_root;
            stack<TreeNode<T> *> st;
            TreeNode<T> * tmp = nullptr;
            size_t stsize = 0;

            while (cur || !st.empty()){
                for (; cur; cur = cur->m_left){
                    st.push(cur);
                }

                if (!st.empty()){
                    cur = st.top();

                    if (stsize > st.size()){//栈顶是parent,改指向重新置位
                        tmp = cur;
                        stsize = st.size();
                    }

                    if (cur == p || cur == q){//可能是祖先节点
                        if (!tmp){
                            tmp = cur;//保存这个点
                            stsize = st.size();//保存栈大小, 改变则改变指向
                        } else {
                            return tmp;
                        }
                    }
                    st.pop();
                    cur = cur->m_right;
                }
            }
            return nullptr;
        }

2.层序遍历

//层序遍历:
        void level_orde(){
            queue<TreeNode<T> *> qu;
            TreeNode<T> * tmp;

            qu.push(m_root);
            while (!qu.empty()){//队列不为空
                tmp = qu.front();
                cout << tmp->m_val << ' ';
                qu.pop();

                //左右子树分别进队
                if(tmp->m_left){
                    qu.push(tmp->m_left);
                }
                if(tmp->m_right){
                    qu.push(tmp->m_right);
                }
            }
        }

3.层序遍历逐行打印

//层序遍历逐行打印
        void every_line_order(){
            queue<TreeNode<T> * > qu;
            TreeNode<T> * tmp;
            int length = 1;//记录每一行入队后队伍的长度,打印完一行换行即可
            //根第一行长度为1
            qu.push(m_root);

            while (!qu.empty()){
                for (int i = 0; i < length; i++){//每一行的长度打印
                    tmp = qu.front();
                    cout << tmp->m_val << " ";

                    //左右子树分别进队
                    if(tmp->m_left){
                        qu.push(tmp->m_left);
                    }
                    if(tmp->m_right){
                        qu.push(tmp->m_right);
                    }
                }
                cout << endl;
                length = qu.size();
            }
        }

4. 求二叉树每一层的最大值

void max_level_order(){
            queue<TreeNode<T> *> qu;
            TreeNode<T> * tmp;
            int length = 1;
            T max;

            qu.push(m_root);
            while (!qu.empty()){
                max = qu.front()->val;//存储每一行最大值进行比较
                for(int i = 0; i < length; i++){
                    tmp = qu.front();

                    if (max < tmp->m_val){//大于存储最大值则进行交换
                        max = tmp->m_val;
                    }
                    qu.pop();

                    if (tmp->m_left){
                        qu.push(tmp->m_left);
                    }
                    if (tmp->m_right){
                        qu.push(tmp->m_right);
                    }
                }
                cout << max << ' ';
                length = qu.size();
            }
        }

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)