5.二叉树

作者: lumo的二次学习笔记 | 来源:发表于2017-12-09 15:51 被阅读0次

    [TOC]

    写在前面

    本篇文章整理《数据结构(C++语言版)》关于二叉树这种线性结构知识点。
    整个数据结构部分章节列表如下:
    1 向量
    -- 1.1 遍历
    -- 1.2 唯一化
    -- 1.3 查找

    2 列表
    -- 2.1 列表节点
    ---- 2.1.1前插入算法
    -- 2.2 列表模板类
    ---- 2.2.1 列表初始化

    3 栈
    -- 3.1 栈应用
    ---- 3.1.1 括号匹配
    ---- 3.1.2 栈混洗甄别
    ---- 3.1.3 中缀表达式
    4 队列

    5 二叉树
    -- 5.1 二叉树节点
    -- 5.2 遍历算法
    ---- 5.2.1 先序遍历
    ---- 5.2.2 中序遍历

    5 二叉树

    关于二叉树的概念,图论中有详细说明,这里不过多解释。
    结构上而言,二叉树与列表类似。可以将二叉树理解为半线性结构

    5.1 二叉树节点

    与列表节点的前驱后继相似,二叉树也有祖先parent,左孩子lChild,右孩子rChild以及存储具体值的data。


    二叉树节点结构

    因此,二叉树节点BinNode实现如下:

    #define BinNodePosi(T) BinNode<T>*
    
    template<typename T>
    struct BinNode<T> {
      T data;  //数值
      BinNodePosi(T) parent; BinNodePosi(T) lChild; BinNodePosi(T) rChild;  //祖先,左右孩子
      int height;  //高度
    //构造函数,列表初始化
      BinNode() : 
          parent(NULL), lChild(NULL), rChild(NULL) {}
      BinNode(T e, BinNodePosi(T) p=NULL, BinNodePosi(T) lc=NULL, BinNodePosi(T) rc=NULL,
              int h=0) :
          data(e), parent(p), lChild(lc), rChild(rc), height(h) {}
    //操作接口
      int size(); //统计当前节点后代总数,亦即以其为根的子树的规模
       BinNodePosi(T) insertAsLC ( T const& ); //作为当前节点的左孩子插入新节点
       BinNodePosi(T) insertAsRC ( T const& ); //作为当前节点的右孩子插入新节点
       BinNodePosi(T) succ(); //取当前节点的直接后继
       template <typename VST> void travLevel ( VST& ); //子树层次遍历
       template <typename VST> void travPre ( VST& ); //子树先序遍历
       template <typename VST> void travIn ( VST& ); //子树中序遍历
       template <typename VST> void travPost ( VST& ); //子树后序遍历
    }
    

    插入左孩子insertAsLC为例,介绍如何插入一个新的二叉树节点。
    通过调用BinNode节点中的构造函数,新建一个BinNode节点,其中{data=e, parent=this, lChild=NULL, rChild=NULL}。随后,再将当前节点的左孩子指向新建的节点即可。

    insertAsLC操作
    具体代码如下:
    template <typename T> 
    BinNodePosi(T) insertAsLC(T const& e) {
      return lChild = new BinNode(e, this);
    }
    

    5.2 遍历算法

    5.2.1 先序遍历

    先序遍历,即先访问根节点,再依次访问左子树与右子树。
    算法1:借助栈结构。访问当前根节点,随后先将其右子树压入栈中,再将左子树压入栈中,随后弹出栈顶元素(左孩子),重复上述操作。

    先序遍历
    代码实现如下:
    //version 1
    template<typename T, typename VST>
    void travPre_I1(BinNodePosi(T) x, VST & visit) {
      stack<BinNodePosi(T)> S;  //辅助栈
      if(x) S.push(x);  //根节点入栈
      while(!S.empty()) {
        x = S.pop(); visit( x->data );
        if( HasRChild(*x) ) S.push(x->rChild);
        if( HasLChild(*x) ) S.push(x->lChild);
      }
    }
    

    算法2(推广至中序遍历甚至后序遍历等):如下图所示,整个二叉树遍历可以看做是一个简化的左子树链。对于每个节点而言,先扫描当前节点,继而扫描其左孩子,当所有左子树的左孩子扫描完成后,以当前节点的右孩子当做新的左子树链,重复上述操作。

    左侧链
    代码实现:
    //version 2
    //左子树链的实现
    template<typename T, typename VST>
    static void visitAlongLeftBranch(BinNodePosi(T) x,  
                                     VST & visit, 
                                     stack<BinNodePosi(T)> & S)  
    {
      while(x) {
        visit(x->data);
        S.push(x->rChild);  //右孩子入栈
        x = x->lChild;
      }
    }
    
    //主算法实现
    template<typename T, typename VST>
    void travPre_I2(BinNodePosi(T) x, VST & visit) {
      stack<BinNodePosi(T) S;
      S.push(x);  //当前节点入栈
      while(!S.empty()) {
        visitAlongLfetBranch(x, visit, S);
        //左子树链中所有左孩子遍历完成后,进入最后一个右孩子重新构造左子树链,重新遍历
        x = S.pop();  
      }
    }
    

    5.2.2 中序遍历

    中序遍历,即依次访问左孩子,当前节点,右孩子。
    算法:如下图所示,节点优先权会依次传递给左子树链最后一个左孩子,随后,访问其右子树,重复操作。


    image.png

    相关文章

      网友评论

        本文标题:5.二叉树

        本文链接:https://www.haomeiwen.com/subject/pmjyixtx.html