一、后序遍历

后序遍历逻辑：优先访问左、右子节点，然后访问当前节点。

一个后序遍历的示例，它的后序遍历结果为[4, 2, 5, 6, 3, 1]：

二、非递归实现

后序遍历的非递归实现比前序和中序的非递归实现要复杂很多，因为每个节点都可能有2个子节点，遍历的时候节点中并没有保存当前的状态，无法确定两个子节点是否已经访问过了。因此，下面采用两个方法来实现非递归访问。

2.1 实现方式一

通过栈+链表配合，流程如下：

1. 根节点入栈，然后循环遍历访问栈顶元素。
2. 每访问一个元素，把该元素插入到链表开头，然后分别把左、右子节点压栈。
3. 循环1-2步，完成后把链表中的节点顺序输出。

代码实现：

void postorder_traversal2(tree_node<T> *node, vector<T> &v) {
    stack<tree_node<T> *> s;
    list<tree_node<T> *> l;
    typename list<tree_node<T> *>::iterator it;
    tree_node<T> *p;
    if (node == nullptr)
        return;

    s.push(node);
    while (!s.empty()) {
        // 取栈顶元素
        p = s.top();
        s.pop;
        // 插入到链表的开头
        l.push_front(p);
        // 左子树入栈
        if (p->lchild)
            s.push(p->lchild);
        // 右子树入栈
        if (p->rchild)
            s.push(p->rchild);
    }

    // 结果放到vector中去
    while (!l.empty()) {
        p = l.front();
        l.pop_front();
        v.push_back(p->val);
    }
}

2.2 实现方式二

非递归的后序遍历和前、中序遍历一样，也依赖栈这个数据结构，原理：

1. 把根节点压栈两次，然后循环判断，当栈不为空的时候，取出栈顶元素。
2. 把取出的栈顶元素和栈当前的栈顶元素对比，如果相等，则把右子节点和左子节点也分别压入栈两次；如果不相等，则访问当前元素。

压栈两次的作用：判断第几次访问节点，第一次访问到节点的时候要先访问子节点，第二次才是访问自己。

一个特别要注意的地方是：栈是先进后出的，所以在压入左右子节点的时候，要先压入右子节点。

代码实现：

void postorder_traversal(tree_node<T> *node, vector<T> &v) {
    stack<tree_node<T> *> st;
    tree_node<T> *p;
    
    if (node == nullptr)
        return;

    // 根元素压栈2次
    st.push(node);
    st.push(node);
    while (!st.empty()) {
        // 弹出栈顶元素
        p = st.top();
        st.pop();
        if (!st.empty() && p != st.top()) { // 如果栈顶元素和刚取出的相等，说明还没有访问过
            // 先压入右子节点
            if (p->rchild) {
                st.push(p->rchild);
                st.push(p->rchild);
            }
            // 再压入左子节点
            if (p->lchild) {
                st.push(p->lchild);
                st.push(p->lchild);
            }
        } else { // 已经访问过了
            v.push_back(p->data);
        }
    }
}

三、递归实现

/*
 * 后序遍历的递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void postorder_traversal(tree_node<T> *node, vector<T> &v) {
    if (node == nullptr)
        return;
    
    if (node->lchild)
        postorder_traversal(node->lchild);
    if (node->rchild)
        postorder_traversal(node->rchild);
    v.push_back(node->data);
}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

给定一个二叉树，返回它的中序遍历。

例如输入: [1,null,2,3]

   1
    \
     2
    /
   3

输出:

[1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二、题解

参考：二叉树的中序遍历（递归和非递归实现）。

三、代码

3.1 非递归代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        stack<TreeNode *> st;
        TreeNode *p;
        p = root;
        while (p || !st.empty()) {
            // 循环遍历左子树
            while (p) {
                st.push(p);
                p = p->left;
            }

            if (!st.empty()) {
                // 弹出栈顶节点
                p = st.top();
                st.pop();
                // 访问节点
                v.push_back(p->val);
                // 访问右子树
                p = p->right;
            }
        }
        return v;
    }
};

3.2 递归代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    void inorderTraversal(TreeNode *root, vector<int> &v) {
        if (root == nullptr) {
            return ;
        }
        if (root->left) {
            inorderTraversal(root->left, v);
        }
        v.push_back(root->val);
        if (root->right) {
            inorderTraversal(root->right, v);
        }
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> v;
        inorderTraversal(root, v);
        return v;
    }
};

一、中序遍历

中序遍历过程：先访问左子节点，然后访问当前节点，最后访问右子节点。

以下试一次中序遍历过程：

二、非递归实现

非递归方式遍历依赖栈来实现，因为要先访问子节点，然后访问父节点，因此必须要有一个数据结构来保存已经父节点。

实现原理：

1. 每次遍历到一个节点，不访问它，先压栈，然后对左子树循环做这个操作。
2. 遍历左节点直到左节点为空时，取出栈顶元素，访问它。
3. 然后对这个栈顶元素的右节点重复执行第一个步骤。

大致的逻辑和前序遍历差不多，相对于前序遍历而言，中序遍历知识把访问节点的时机延后了一些。前序遍历可以参考二叉树的先序遍历。

代码描述：

/*
 * 中序遍历的非递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void in_order_traversal_by_stack(tree_node<T> *node, vector<T> &v) {
    stack<tree_node<T> *> st;
    tree_node<T> *p;

    p = node;
    while (p || !st.empty()) {
        // 左子树压栈
        while (p) {
            st.push(p);
            p = p->lchild;
        }

        if (!st.empty()) {
            // 取出栈顶元素
            p = st.top();
            st.pop();
            // 访问节点
            v.push_back(p->data);
            // 设置指针为右子节点
            p = p->rchild;
        }
    }
}

三、递归实现

递归实现很简单，不做详细描述：

/*
 * 中序遍历的递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void in_order_traversal(tree_node<T> *node, vector<T> &v) {
    if (node == nullptr)
        return;

    if (node->lchild)
        in_order_traversal(node->lchild, v);

    v.push_back(node->data);

    if (node->rchild)
        in_order_traversal(node->rchild, v);
}

一、题目描述

给定一个二叉树，返回它的前序遍历结果。

例如输入二叉树[1,null,2,3]：

   1
    \
     2
    /
   3 

输出：

[1,2,3]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

二、题解

二叉树的前序遍历，递归和非递归方式。

参考：二叉树的前序遍历。

三、代码

3.1 递归代码

class Solution {
    void preorderTraversal(TreeNode *root, vector<int> &v) {
        if (root == nullptr) {
            return;
        }
        v.push_back(root->val);
        if (root->left) {
            preorderTraversal(root->left, v);
        }
        if (root->right) {
            preorderTraversal(root->right, v);
        }
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> v;
        preorderTraversal(root, v);
        return v;
    }
};

3.2 非递归代码

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode *> st;
        TreeNode *p;
        vector<int> v;

        p = root;
        while (p || !st.empty()) {
            while (p) {
                // 遍历当前节点
                v.push_back(p->val);
                st.push(p);
                // 遍历左子树
                p = p->left;
            }

            // 通过栈来遍历右子树
            if (!st.empty()) {
                p = st.top()->right;
                st.pop();
            }
        }

        return v;
    }
};

一、先序遍历

先序遍历的意思是：先遍历当前节点，再分别遍历左、右子节点。

例如一棵二叉树为：

它的先序遍历序列（红色虚线标出来的）为：[1, 2, 4, 3, 5 6]。

二、递归实现

递归的实现很简单，先访问当前节点，然后分别递归访问左右子节点。

/*
 * 先序遍历的递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void pre_order_traversal(tree_node<T> *node, vector<T> &v) {
    if (node == nullptr)
        return;

    // 遍历当前节点
    v.push_back(node->data);

    // 遍历左子树
    if (node->lchild)
        pre_order_traversal(node->lchild);

    // 遍历右子树
    if (node->rchild)
        pre_order_traversal(node->rchild);
}

三、非递归实现

非递归的方式依赖栈来实现，逻辑：

1. 访问根节点，把当前节点压栈。然后设置当前节点为左子节点，重复过程，直到左子节点为空。
2. 设置当前节点为栈顶节点的右子节点，重复1过程。

3.1 图文描述

以上面的二叉树为例，首先访问根元素1，压栈：

然后继续访问1节点的左节点2，压栈：

节点2没有左子节点，退出左树遍历。然后取出栈顶元素2，访问它的右子节点4：

右子节点没有子节点，因此继续从栈顶取元素1，访问它的右子节点3并压栈：

节点3有左子节点，顺着遍历左子节点5，节点5入栈：

此时5没有没有左子节点了，于是取出栈顶元素5，访问它的右子节点。但是它没有右子节点，继续取出栈顶元素3，访问它的右子节点6：

访问完6后，因为没有子节点了。所以继续从栈里取元素，但是此时栈也为空了，遍历结束。

3.2 代码描述

/*
 * 先序遍历的非递归实现
 * @node 需要遍历的节点
 * @v 保存遍历结果的数组
 */
void pre_order_traversal(tree_node<T> *root, vector<T> &v) {
    stack<tree_node<T> *> st;
    tree_node<T> *p;

    p = root;
    while (p != nullptr || !st.empty()) {
        // 遍历左子树
        while (p) {
            // 访问当前节点
            v.push_back(p->data);
            // 当前节点入栈
            st.push(p);
            // 遍历左子节点
            p = p->lchild;
        }

        // 取栈顶元素，访问父亲节点的右子节点
        if (!st.empty()) {
            p = st.top()->rchild;
            st.pop();
        }
    }
}

一、题目

给定一颗二叉树和其中的一个节点，如何找出中序遍历序列的下一个节点？树中的节点除了有两个分别指向左右子节点的指针，还有一个指向父节点的指针。

以下面的二叉树为例，它的中序遍历序列是：[2, 4, 1, 5, 3, 6]，节点4的下一个节点是1，节点3的下一个节点是5。

二、分析

画出上面这棵二叉树的中序遍历过程为：

根据中序遍历的特性，可以整理出来的下一个节点的规律：

1. 如果节点有右子节点，那么下一个节点一定在右子树中，这种又分成了2种情况。

   • 右儿子没有子节点，那么下一个节点就是子节点（节点2）
   • 如果右子节点有子节点，下一个节点就是右子节点种最左的节点（节点1）。
2. 如果节点没有右子节点，并且是父节点的左子节点，那么下一个节点就是父亲节点（节点5）。
3. 如果节点没有右子节点，并且是父节点的右子节点，那就递归查找父节点，直到一个父节点是祖父节点的左子树（节点4）。如果找到根节点都没有找到，就说明该节点已经是最后一个了（节点6）。

三、代码

类节点定义：

template<typename T>
class tree_node {
private:
    T data;
    tree_node *lchild;
    tree_node *rchild;
    tree_node *parent;
};

查找中序遍历序列中下一个节点的成员函数：

// 获取中序遍历的下一个节点
const tree_node<T> *get_next_node_in_order() const {
    const tree_node<T> *p, *father;
    if (rchild) { // 有右节点，在右子树中查找
        p = rchild;
      
        // 循环遍历左子树
        while (p->lchild)
            p = p->lchild;
      
        return p;
    } else if (parent) {
        p = this;
        father = parent;
      
        // 只要不是父节点的左子节点，一直往上找
        while (father && p != father->lchild) {
            p = father;
            father = father->parent;
        }

        // 返回父亲节点
        return father;
    }
    return nullptr;
}

四、单元测试

单元测试主要覆盖几个点：

• 节点有右子节点。
• 节点没有右子节点，存在一个父节点是祖先节点的左子节点。
• 节点没有右子节点，不存在一个父节点是祖先节点的左子节点。

/*
 * 测试案例：查找二叉树中序遍历的下一个节点
 *         1
 *      /     \
 *     2       3
 *      \     / \
 *       4   5   6
 */
TEST(bin_tree, get_next_node_in_order) {
    bin_tree<int> tree;
    const tree_node<int> *node;
    int in[] = {2, 4, 1, 5, 3, 6}; // 先序遍历序列
    int pre[] = {1, 2, 4, 3, 5, 6}; // 中序遍历序列
    
    // 根据先序遍历序列和中序遍历序列生成二叉树
    tree.construct(pre, in, 6);
    EXPECT_TRUE(tree.get_root());

    // 定位到中序遍历的开始节点2，然后依次获取下一个节点，和in数组对比
    node = tree.get_root()->get_lchild();
    for (int i = 0; i < 6; i++) {
        EXPECT_TRUE(node) << i;
        EXPECT_EQ(node->get_data(), in[i]);
        node = tree.get_next(node);
    }
    EXPECT_EQ(node, nullptr);
}

测试结果：

一、问题描述

画二叉树的时候，总是无法对齐圆点得到对称的节点。例如：

graph test {
    graph [dpi=80]
    node [shape=circle];

    1 -- 2, 3;
    2 -- 4, 5 [color=red,penwidth=3.0];

    3 -- 6, 7 [color=red,penwidth=3.0];
    4 -- 8;
}

画出来的效果：

红色标出来的4个线条，长度不一样，子节点看起来不对称，就导致整个二叉树看起来也不够美观。

二、解决方案

可以在子节点中加一个中间节点，把线条的weight设置成10，然后隐藏中间的节点和连线：

graph bin_tree {
    node [shape=circle];

    1 -- 2, 3;
    2 -- 4;
    // 隐藏中间节点的连线
    2 -- m2 [weight=10 style="dashed"];
    2 -- 5;

    3 -- 6;
    // 隐藏中间节点的连线
    3 -- m3 [weight=10 style="dashed"];
    3 -- 7;
    4 -- 8;
        
        // 隐藏中间节点
    m2, m3 [label="" style="dashed"]
}

效果：

weight属性的作用是设置线条的权重，权重越大，线条越垂直。

如果希望完全隐藏中间节点，只要把对应节点和线条的属性设置为invis即可：

style="dashed" -> style="invis"

三、参考

Enforcing horizontal node ordering in a .dot tree

How to get balanced diagrams from graphviz?

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出前序遍历 preorder = [3,9,20,15,7]，中序遍历 inorder = [9,3,15,20,7]，返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

二、题解

这道题在《剑指offer》也出现了，题目完全一样。主要用到了树的两个特性：

• 前序遍历的首元素为根节点。
• 中序遍历中，根节点的左边是左子树，根节点的右边是右子树。

解题的思路就是：通过前序遍历得到根节点，然后在中序遍历中找到这个节点，再通过递归的方式找出左右子树。

详细的分析可以参考《剑指offer》面试题7：重建二叉树。

三、代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        size_t len = preorder.size();
        if (len < 1)
            return nullptr;
        return buildTreeCore(preorder, 0, len - 1, inorder, 0, len - 1);        
    }
private:
    TreeNode *buildTreeCore(vector<int> &preOrder, unsigned int preStart, unsigned int preEnd,
                            vector<int> &inOrder, unsigned int inStart, unsigned int inEnd) {
        unsigned int idx, lchild_len;
        TreeNode *root = nullptr;
        root = new TreeNode(preOrder[preStart]);

        if (preStart == preEnd) {
            return root;
        }

        // 在中序遍历中找到根节点
        idx = inStart;
        while (idx < inEnd && root->val != inOrder[idx]) {
            idx++;
        }

        // 左子树的长度
        lchild_len = idx - inStart;
        
        if (lchild_len > 0) {
            // 计算左子树
            root->left = buildTreeCore(preOrder, preStart + 1, preStart + lchild_len,
                    inOrder, inStart, idx - 1);
        }

        if (lchild_len < preEnd - preStart) {
            // 计算右子树
            root->right = buildTreeCore(preOrder, preStart + lchild_len + 1, preEnd,
                    inOrder, idx + 1, inEnd);
        }

        return root;
    }
};

执行通过：

一、题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不包含重复的数字。

例如，输入前序遍历序列[1, 2, 4, 7, 3, 5, 6, 8]和中序遍历序列[4, 7, 2, 1, 5, 3, 8, 6]，则重建如下图所示的二叉树并输出它的头结点：

二、解析

根据前序、中序遍历的特性和上面的图形能得到的结论：

• 前序遍历的第一个元素就是树的根节点。
• 根节点左边的元素就是左子树，根右边的就是右子树。

图片描述：

基于这两个特性就可以通过以下方式来构建出一颗二叉树：从前序遍历中确认根节点，再到中序遍历中找到定位到这个根节点，这样就可以拿到对应的左子树和右子树了。然后再按照相同的方式分别得到左右子树的子树，那么整个二叉树就可以构建起来了。

三、代码实现

二叉树节点定义：

template<typename T>
class tree_node {
    friend class bin_tree<T>;
    tree_node(const T &data) : data(data), lchild(nullptr), rchild(nullptr) {}
private:
    T data;
    tree_node *lchild;
    tree_node *rchild;
}

二叉树定义：

class bin_tree {
public:
    bin_tree() : root(nullptr) {}
    tree_node<T> *root;
};

在二叉树类中实现通过前序遍历和中序遍历构造二叉树的函数：

/*
 * 根据前序和中序遍历序列构造一个二叉树
 * @pre_order 前序遍历序列
 * @in_order 中序遍历序列
 * @len 序列长度
 */
void construct(const T pre_order[], const T in_order[], const unsigned int len) {
    if (len < 1)
        return;

    this->root = construct_core(pre_order, pre_order + len - 1, 
            in_order, in_order + len - 1);
}

/*
 * 通过前序遍列和中序遍历的结果构建二叉树
 * 前序遍历序列[pre_order_start, pre_order_end]，中序遍历序列[in_order_start, in_order_end]
 * @pre_order_start 前序遍历的开始位置
 * @pre_order_end 前序遍历的结束位置
 * @in_order_start 中序遍历的开始位置
 * @in_order_end 中序遍历的结束位置
 */
tree_node<T> *construct_core(const T *pre_order_start, const T *pre_order_end,
                             const T *in_order_start, const T *in_order_end) {
    // 遍历指针
    const T *cursor;
    // 前序遍历序列中左子树的结束位置
    const T *lchild_end;
    // 左子树的长度
    unsigned int lchild_len;
    // 根节点
    tree_node<T> *root = nullptr;;

    // 前序遍历的首元素即为树根
    root = new tree_node<T>(pre_order_start[0]);

    // 如果前序遍历的头和尾相等，说明只有一个元素了，返回当前元素
    if (pre_order_start == pre_order_end) {
        // 下面是简单的判断输入参数是否合法
        // 如果只有一个元素了，前序和中序的遍历结果是相同的
        if (in_order_start == in_order_end && *in_order_start == *pre_order_start)
            return root;
        else // 输入有问题
            throw "invalid input";
    }

    // 在中序遍历中找到根节点
    cursor = in_order_start;
    while (cursor < in_order_end && *cursor != root->data)
        cursor++;

    // 匹配到中序遍历的最后一个元素了还没有找到，说明输入不合法
    if (cursor == in_order_end && *cursor != root->data)
        throw "invalid input";

    lchild_len = cursor - in_order_start;
    lchild_end = pre_order_start + lchild_len;

    // 递归获取左子树
    if (lchild_len > 0) {
        root->lchild = construct_core(pre_order_start + 1, lchild_end,
                                      in_order_start, cursor - 1);
    }

    // 递归获取右子树
    if (lchild_len < pre_order_end - pre_order_start) {
        root->rchild = construct_core(lchild_end + 1, pre_order_end,
                                      cursor + 1, in_order_end);
    }

    return root;
}

四、单元测试

单元测试覆盖以下几点：

• 树为空
• 树只有一个节点
• 完全二叉树
• 满二叉树
• 不完全二叉树

4.1 树为空

/*
 * 测试：通过前序和中序遍历序列构造二叉树
 * 案例：二叉树为空
 */
TEST(construct_by_pre_order_and_in_order, no_node) {
    bin_tree<int> tree;
    tree.construct(nullptr, nullptr, 0);
    EXPECT_FALSE(tree.get_root());
}

4.2 树只有一个节点

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：二叉树包含一个节点
 */
TEST(construct_by_pre_order_and_in_order, one_node) {
    bin_tree<int> tree;
    int data[1] = {1};
    tree.construct(data, data, 1);
    EXPECT_TRUE(tree.get_root());
    EXPECT_FALSE(tree.get_root()->get_lchild());
    EXPECT_FALSE(tree.get_root()->get_rchild());
}

4.3 完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：完全二叉树测试
 *          1
 *        2   3
 *       4 5
 */
TEST(construct_by_pre_order_and_in_order, complete_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3};
    int in_order[7] = {4, 2, 5, 1, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
}

4.4 满二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：满二叉树测试
 *          1
 *        2   3
 *       4 5 6 7
 */
TEST(construct_by_pre_order_and_in_order, full_bin_tree) {
    int pre_order[7] = {1, 2, 4, 5, 3, 6, 7};
    int in_order[7] = {4, 2, 5, 1, 6, 3, 7};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 7);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 4);
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    EXPECT_EQ(node->get_rchild()->get_data(), 7);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());
}

4.5 非完全二叉树

/*
 * 测试：通过前序和中序便利序列构造二叉树
 * 案例：普通二叉树测试
 *          1
 *        2   3
 *         5 6
 */
TEST(construct_by_pre_order_and_in_order, normal_bin_tree) {
    int pre_order[7] = {1, 2, 5, 3, 6};
    int in_order[7] = {2, 5, 1, 6, 3};
    bin_tree<int> tree;
    const tree_node<int> *root, *node;
    tree.construct(pre_order, in_order, 5);
    root = tree.get_root();
    EXPECT_TRUE(root);

    EXPECT_EQ(root->get_data(), 1);
    EXPECT_TRUE(root->get_lchild());
    EXPECT_TRUE(root->get_rchild());
    EXPECT_EQ(root->get_lchild()->get_data(), 2);
    EXPECT_EQ(root->get_rchild()->get_data(), 3);

    node = root->get_lchild(); // -> 节点2
    // 检查子节点
    EXPECT_FALSE(node->get_lchild());
    EXPECT_TRUE(node->get_rchild());
    EXPECT_EQ(node->get_rchild()->get_data(), 5);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_rchild()->get_lchild());
    EXPECT_FALSE(node->get_rchild()->get_rchild());

    node = root->get_rchild(); // -> 节点3
    // 检查子节点
    EXPECT_TRUE(node->get_lchild());
    EXPECT_FALSE(node->get_rchild());
    // 左子节点为6，右子节点为空
    EXPECT_EQ(node->get_lchild()->get_data(), 6);
    // 检查子节点的子节点
    EXPECT_FALSE(node->get_lchild()->get_lchild());
    EXPECT_FALSE(node->get_lchild()->get_rchild());
}

4.6 测试结果

一、梳排序简介

梳排序是冒泡排序的一种优化方案，主要是为了解决冒泡排序中的尾部小数值问题。它主要的思想是通过比较元素和固定步长位置上的数据，先进行部分优化，然后逐步减少步长，以此来对数据进行预处理。

以数组[3,1 5, 2, 4]为例，假设步长是2，那么就分别处理[3, 5, 4]和[1, 2]，先局部优化。优化完成后，再使用冒泡排序。

关于步长的选取

步长并不是逐步递减的，步长的选取一般通过一个步长因子来控制：

1. 初始化时，步长等于数组长度除以步长因子。
2. 后续的所有步长都等于前一次步长除以步长因子，直到步长小于等于1。

从实验结果来看，这个步长因子设置为1.3时能获得较好的性能，并且实验数据证明，梳排序的良好性能甚至可以与快速排序媲美。

排序示例

以数组[41, 11, 18, 7, 16, 25, 4, 23, 32, 31, 22, 9, 1, 22, 3, 7, 31, 6, 10]为例，它的长度是19，计算得到的步长分别是[14, 10, 7, 5, 3, 2]，它的预处理过程可以整理为：

其中no表示第几趟排序，step表示步长，data是当前经过处理后的数组。很明显可以看出经过6次预处理后，数据已经基本有序了。

此时再通过冒泡排序来对整体排序就能减少很多工作量了（实际上只需要再做一次冒泡排序就能完成排序了）。如果没有第一阶段的处理，冒泡需要19趟排序才能完成，而经过处理后，第8趟排序就已经有序了。此时排序结束，节省了一半以上的时间。

二、代码

C++代码：

const float factor = 1.3;

template<typename T>
void comb_sort(T data[], const unsigned int n) {
    unsigned int i, j, step = n;
    bool flag = true;

    if (n < 2)
        return;
    
    // 步长处理
    while ((step = (unsigned int) (step / factor)) > 1) {
        for (i = n - 1; i >= step; i--) {
            j = i - step;
            if (data[i] < data[j])
                my_swap(data[i], data[j]);
        }
    }

    // 冒泡排序
    for (i = 0; flag && i < n - 1; i++) {
        flag = false;
        for (j = 1; j < n - i; j++) {
            if (data[j] < data[j - 1]) {
                my_swap(data[j], data[j - 1]);
                flag = true;
            }
        }
    }
}