master

分支 (3)

管理

管理

master

Prometheus

dev

data-structures-cpp
/
Tree
/
BinaryTree
/
src
/
binary_tree.h

/*!
 * @file binary_tree.h
 * @author CyberDash计算机考研, cyberdash@163.com(抖音id:cyberdash_yuan)
 * @brief 二叉树模板类
 * @version 0.2.1
 * @date 2020-11-01
 */

#ifndef CYBER_DASH_BINARY_TREE_H
#define CYBER_DASH_BINARY_TREE_H


#include <iostream>
#include <cstdlib>
#include <stack>
#include <queue>
#include "binary_tree.h"


using namespace std;


/*!
 * @brief 二叉树结点模板结构体
 * @tparam TData 数据项类型模板参数
 */
template <class TData>
struct BinaryTreeNode {
    /*! @brief **默认构造函数** */
    BinaryTreeNode() : left_child(NULL), right_child(NULL) {}
    /*! @brief 构造函数(数据项/左右孩子) */
    BinaryTreeNode(TData data, BinaryTreeNode<TData>* left_child = NULL, BinaryTreeNode<TData>* right_child = NULL)
        : data(data), left_child(left_child), right_child(right_child) {}

    TData data;                           //!< **数据项**
    BinaryTreeNode<TData>* left_child;    //!< **左孩子结点(指针)**
    BinaryTreeNode<TData>* right_child;   //!< **右孩子结点(指针)**
};


/*!
 * @brief **(后序遍历)回溯栈结点模板类**
 * @tparam TData 数据项类型模板参数
 */
template <class TData>
struct PostorderBacktrackStackNode {
    /*! @brief 构造函数(二叉树结点指针) */
    explicit PostorderBacktrackStackNode(BinaryTreeNode<TData>* node = NULL) : node(node), tag(LEFT_BACK_TRACKING) {}

    BinaryTreeNode<TData>* node;                                //!< 二叉树结点指针
    enum { LEFT_BACK_TRACKING, RIGHT_BACK_TRACKING } tag;       //!< 标签, 0: 左孩子回溯, 1: 右孩子回溯
};


/*!
 * @brief 二叉树模板类
 * @tparam TData 数据项类型模板参数
 */
template <class TData>
class BinaryTree {
public:
    /*! @brief 默认构造函数*/
    BinaryTree() : root_(NULL) {}
    /*! @brief 构造函数(根结点数据项) */
    BinaryTree(const TData& data) { this->InsertInSubTreeRecursive_(this->root_, data); }
    /*! @brief 复制构造函数 */
    BinaryTree(const BinaryTree<TData>& binary_tree);
    /*! @brief 析构函数 */
    ~BinaryTree() { this->DestroySubtreeRecursive_(root_); }

    /*! @brief 获取根节点 */
    BinaryTreeNode<TData>* Root() const { return this->root_; }

    /*! @brief 是否为空树 */
    bool IsEmpty() { return this->root_ == NULL; }

    /*!
     * @brief 获取父节点
     * @return 父节点(指针)
     */
    BinaryTreeNode<TData>* Parent(BinaryTreeNode<TData>* node) const {
        return (this->root_ == NULL || this->root_ == node) ? NULL : this->Parent_(this->root_, node);
    }

    /*!
     * @brief 获取高度
     * @return 高度
     */
    int Height() { return this->HeightOfSubTreeRecursive_(this->root_); }

    /*!
     * @brief 获取结点数
     * @return 结点数
     */
    int Size() { return this->SizeOfSubTree_(this->root_); }

    /*!
     * @brief 插入结点
     * @param data 数据项
     * @return 是否成功
     */
    bool Insert(const TData& data) { return this->InsertInSubTreeRecursive_(this->root_, data); }

    /*!
     * @brief 查询数据项是否在树中
     * @param data 数据项
     * @return 是否在树中
     */
    bool Exist(TData data) { return this->ExistInSubTree_(this->root_, data); }

    /* 遍历系列 */
    /*!
     * @brief 前序遍历(递归)
     * @param visit 结点访问函数
     */
    void PreOrderTraversal(void (*visit)(BinaryTreeNode<TData>* node)) {
        this->PreOrderTraversalOfSubTreeRecursive_(this->root_, visit);
    }

    /*!
     * @brief 前序遍历(非递归)
     * @param visit 结点访问函数
     */
    void PreOrderTraversalNonRecursive(void (*visit)(BinaryTreeNode<TData>* node)) {
        this->PreorderTraversalOfSubtreeNonRecursive_(this->root_, visit);
    }

    /*!
     * @brief 中序遍历(使用递归)
     * @param visit 结点访问函数
     */
    void InorderTraversal(void (*visit)(BinaryTreeNode<TData>* node)) {
        this->InorderTraversalOfSubtreeRecursive_(this->root_, visit);
    }

    /*!
     * @brief 中序遍历(使用非递归)
     * @param visit 结点访问函数
     */
    void InorderTraversalNonRecursive(void (*visit)(BinaryTreeNode<TData>* node)) {
        this->InorderTraversalOfSubtreeNonRecursive_(this->root_, visit);
    }

    /*!
     * @brief 后序遍历(使用递归)
     * @param visit 结点访问函数
     */
    void PostorderTraversal(void (*visit)(BinaryTreeNode<TData>* node)) {
        this->PostorderTraversalOfSubtreeRecursive_(this->root_, visit);
    }

    /*!
     * @brief 后序遍历(使用非递归)
     * @param visit 结点访问函数
     */
    void PostorderTraversalNonRecursive(void (*visit)(BinaryTreeNode<TData>* node)) {
        this->PostorderTraversalOfSubtreeNonRecursive_(this->root_, visit);
    }

    /*!
     * @brief 层序遍历
     * @param visit 结点访问函数
     */
    void LevelOrderTraversal(void (*visit)(BinaryTreeNode<TData>* node)) {
        this->LevelOrderTraversalOfSubtree_(this->root_, visit);
    }

    /*!
     * @brief 建树(by前序遍历和中序遍历)
     * @param preorder_list 前序遍历列表
     * @param inorder_list 中序遍历列表
     * @param length 字符串长度
     */
    bool CreateByPreorderAndInorderList(TData* preorder_list, TData* inorder_list, int length) {
        bool res = this->CreateSubtreeByPreorderAndInorderList_(preorder_list, inorder_list, length, this->root_);
        return res;
    }

    /*!
     * @brief 打印二叉树(使用'(', ',',')')
     */
    void Print() { this->PrintSubTree_(this->root_); };

    // 判断两颗二叉树是否相同(递归)
    static bool Equal(BinaryTreeNode<TData>* root1, BinaryTreeNode<TData>* root2);

protected:
    BinaryTreeNode<TData>* root_; //!< 根结点

    // 子树插入数据
    bool InsertInSubTreeRecursive_(BinaryTreeNode<TData>*& subtree_root, TData data);
    // 删除子树
    void DestroySubtreeRecursive_(BinaryTreeNode<TData>*& subtree_root);
    // 查找数据是否在(子)树中(递归)
    bool ExistInSubTree_(BinaryTreeNode<TData>* subtree_root, TData data) const;
    // 复制二叉树
    bool DuplicateSubTreeRecursive_(BinaryTreeNode<TData>* src_subtree_root, BinaryTreeNode<TData>*& target_subtree_root);
    // 求子树的高度(递归)
    int HeightOfSubTreeRecursive_(BinaryTreeNode<TData>* subtree_root) const;
    // 求子树的Size(递归)
    int SizeOfSubTree_(BinaryTreeNode<TData>* subtree_root) const;
    // 子树获取节点的父节点
    BinaryTreeNode<TData>* Parent_(BinaryTreeNode<TData>* subtree_root, BinaryTreeNode<TData>* node) const;

    // 子树前序遍历(递归)
    void PreOrderTraversalOfSubTreeRecursive_(BinaryTreeNode<TData>* subtree_root,
                                              void (*visit)(BinaryTreeNode<TData>* node));
    // 子树前序遍历(非递归)
    void PreorderTraversalOfSubtreeNonRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                 void (*visit)(BinaryTreeNode<TData>* node));
    // 子树中序遍历(递归)
    void InorderTraversalOfSubtreeRecursive_(BinaryTreeNode<TData>* subtree_root,
                                             void (*visit)(BinaryTreeNode<TData>* node));
    // 子树中序遍历(非递归)
    void InorderTraversalOfSubtreeNonRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                void (*visit)(BinaryTreeNode<TData>* node));
    // 子树后序遍历(递归)
    void PostorderTraversalOfSubtreeRecursive_(BinaryTreeNode<TData>* subtree_root,
                                               void (*visit)(BinaryTreeNode<TData>* node));
    // 子树后序遍历(非递归)
    void PostorderTraversalOfSubtreeNonRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                  void (*visit)(BinaryTreeNode<TData>* node));
    // 子树层序遍历
    void LevelOrderTraversalOfSubtree_(BinaryTreeNode<TData>* subtree_root,
                                       void (*visit)(BinaryTreeNode<TData>* node));
    // 子树打印
    void PrintSubTree_(BinaryTreeNode<TData>* subtree_root);

    // 使用前序遍历和中序遍历结果, 创建二叉子树(递归)
    bool CreateSubtreeByPreorderAndInorderList_(TData* preorder_list,
                                                TData* inorder_list,
                                                int length,
                                                BinaryTreeNode<TData>*& subtree_root);

    // 判断两颗树相同
    template<class TData>
    friend bool operator == (const BinaryTree<TData>& binary_tree_1, const BinaryTree<TData>& binary_tree_2);
    // 输出二叉树
    template<class TData>
    friend ostream& operator << (ostream& out, BinaryTree<TData>& binary_tree);
};


template<class TData>
BinaryTree<TData>::BinaryTree(const BinaryTree<TData>& binary_tree) {
    bool res = this->DuplicateSubTreeRecursive_(binary_tree.Root(), this->root_);
    if (!res) {
        throw std::exception("DuplicateSubTreeRecursive_ error");
    }
}


/*!
 * @brief 子树插入数据
 * @tparam TData 类型模板参数
 * @param subtree_root 子树根结点
 * @param data 结点数据项
 * @return 是否插入成功
 */
template<class TData>
bool BinaryTree<TData>::InsertInSubTreeRecursive_(BinaryTreeNode<TData>*& subtree_root, TData data) {

    if (subtree_root == NULL) {
        subtree_root = new BinaryTreeNode<TData>(data);
        if (subtree_root == NULL) {
            cerr << "存储分配错误!" << endl;
            return false;
        }

        return true;
    }

    bool res = false;

    int left_subtree_height = HeightOfSubTreeRecursive_(subtree_root->left_child);
    int right_subtree_height = HeightOfSubTreeRecursive_(subtree_root->right_child);

    if (left_subtree_height > right_subtree_height) {
        res = InsertInSubTreeRecursive_(subtree_root->right_child, data);
        if (!res) {
            return false;
        }
    } else {
        res = InsertInSubTreeRecursive_(subtree_root->left_child, data);
        if (!res) {
            return false;
        }
    }

    return true;
}


/*!
 * @brief 删除子树
 * @param subtree_root 子树根节点
 */
template <class TData>
void BinaryTree<TData>::DestroySubtreeRecursive_(BinaryTreeNode<TData>*& subtree_root) {
    if (subtree_root == NULL) {
        return;
    }

    this->DestroySubtreeRecursive_(subtree_root->left_child);
    this->DestroySubtreeRecursive_(subtree_root->right_child);

    delete subtree_root;
    subtree_root = NULL;
}


/**
 * @brief 查找数据是否在(子)树中(递归)
 * @tparam TData 结点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param data 被查找数据
 * @return 是否存在
 */
template<class TData>
bool BinaryTree<TData>::ExistInSubTree_(BinaryTreeNode<TData>* subtree_root, TData data) const {

    if (subtree_root == NULL) {
        return false;
    }

    if (subtree_root->data == data) {
        return true;
    }

    bool existed = ExistInSubTree_(subtree_root->left_child, data);
    if (existed) {
        return true;
    }

    existed = ExistInSubTree_(subtree_root->right_child, data);

    return existed;
}


 /*!
  * @brief **复制二叉树(递归)**
  * @tparam TData
  * @param src_subtree_root
  * @param target_subtree_root
  * @return
  */
template<class TData>
bool BinaryTree<TData>::DuplicateSubTreeRecursive_(BinaryTreeNode<TData>* src_subtree_root,
                                                   BinaryTreeNode<TData>*& target_subtree_root)
{
    if (src_subtree_root == NULL) {
        target_subtree_root = NULL;
        return true;
    }

    target_subtree_root = new BinaryTreeNode<TData>(src_subtree_root->data);
    if (!target_subtree_root) {
        return false;
    }

    bool res = this->DuplicateSubTreeRecursive_(src_subtree_root->left_child, target_subtree_root->left_child);
    if (!res) {
        return false;
    }

    res = this->DuplicateSubTreeRecursive_(src_subtree_root->right_child, target_subtree_root->right_child);
    if (!res) {
        return false;
    }

    return true;
}


/*!
 * @brief 求子树的高度(递归)
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @return 子树高度
 */
template<class TData>
int BinaryTree<TData>::HeightOfSubTreeRecursive_(BinaryTreeNode<TData>* subtree_root) const {
    // 如果子树根节点为空, 则返回0
    if (subtree_root == NULL) {
        return 0;
    }

    int left_subtree_height = HeightOfSubTreeRecursive_(subtree_root->left_child); // 递归求左子树高度
    int right_subtree_height = HeightOfSubTreeRecursive_(subtree_root->right_child); // 递归求右子树高度

    // 树高度 = 最高的左右子树高度 + 1
    int subtree_height = 0;
    if (left_subtree_height < right_subtree_height) {
        subtree_height = right_subtree_height + 1;
    } else {
        subtree_height = left_subtree_height + 1;
    }

    return subtree_height;
}


/*!
 * @brief 求子树的size(递归)
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @return 子树size
 */
template<class TData>
int BinaryTree<TData>::SizeOfSubTree_(BinaryTreeNode<TData>* subtree_root) const {
    if (subtree_root == NULL) {
        return 0;
    }

    int left_subtree_size = SizeOfSubTree_(subtree_root->left_child); // 递归求左子树size
    int right_subtree_size = SizeOfSubTree_(subtree_root->right_child); // 递归求右子树size

    int subtree_size = 1 + left_subtree_size + right_subtree_size;

    return subtree_size;
}


/*!
 * @brief 子树获取节点的父节点
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param node 节点指针
 * @return 节点的(位于子树内的)父节点指针
 */
template<class TData>
BinaryTreeNode<TData>* BinaryTree<TData>::Parent_(BinaryTreeNode<TData>* subtree_root,
                                                  BinaryTreeNode<TData>* node) const
{
    // 如果子树根为NULL, 则返回NULL
    if (subtree_root == NULL) {
        return NULL;
    }

    // 如果子树根的左孩子or右孩子, 就是node_ptr的父节点, 则返回子树根结点
    if (subtree_root->left_child == node || subtree_root->right_child == node) {
        return subtree_root;
    }

    BinaryTreeNode<TData>* parent = Parent_(subtree_root->left_child, node);

    if (parent == NULL) {
        parent = Parent_(subtree_root->right_child, node);
    }

    return parent;
}


 /*!
  * @brief 子树前序遍历(递归)
  * @tparam TData 节点数据模板类型
  * @param subtree_root 子树根节点指针
  * @param visit 访问函数
  */
template<class TData>
void BinaryTree<TData>::PreOrderTraversalOfSubTreeRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                             void (*visit)(BinaryTreeNode<TData>* node))
{
    if (subtree_root == NULL) {
        return;
    }

    visit(subtree_root);

    PreOrderTraversalOfSubTreeRecursive_(subtree_root->left_child, visit);
    PreOrderTraversalOfSubTreeRecursive_(subtree_root->right_child, visit);
}


/**
 * @brief 子树前序遍历(非递归)
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param visit 访问函数
 */
template<class TData>
void BinaryTree<TData>::PreorderTraversalOfSubtreeNonRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                                void (*visit)(BinaryTreeNode<TData>*))
{

    // (栈初始化)声明前序遍历栈, 子树根节点指针入栈
    stack<BinaryTreeNode<TData>*> backtrack_stack;
    backtrack_stack.push(subtree_root);

    while (!backtrack_stack.empty()) {

        // 出栈
        BinaryTreeNode<TData>* cur = backtrack_stack.top();
        backtrack_stack.pop();

        // 访问
        visit(cur);

        // 孩子节点入栈
        if (cur->right_child != NULL) {
            backtrack_stack.push(cur->right_child);
        }

        if (cur->left_child != NULL) {
            backtrack_stack.push(cur->left_child);
        }
    }
}


/*!
 * @brief 子树中序遍历(递归)
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param visit 访问函数
 */
template<class TData>
void BinaryTree<TData>::InorderTraversalOfSubtreeRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                            void (*visit)(BinaryTreeNode<TData>* node))
{
    if (subtree_root == NULL) {
        return;
    }

    InorderTraversalOfSubtreeRecursive_(subtree_root->left_child, visit);

    visit(subtree_root);

    InorderTraversalOfSubtreeRecursive_(subtree_root->right_child, visit);
}


/**
 * @brief 子树中序遍历(非递归)
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param visit 访问函数
 */
template<class TData>
void BinaryTree<TData>::InorderTraversalOfSubtreeNonRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                               void (*visit)(BinaryTreeNode<TData>* node))
{
    stack<BinaryTreeNode<TData>*> backtrack_stack;
    BinaryTreeNode<TData>* cur_tree_node = subtree_root;

    while (cur_tree_node != NULL || !backtrack_stack.empty()) {

        // 一直向左子树方向搜索(等于在做深度优先搜索DFS)
        while (cur_tree_node != NULL) {
            backtrack_stack.push(cur_tree_node);
            cur_tree_node = cur_tree_node->left_child;
        }

        if (!backtrack_stack.empty()) {

            cur_tree_node = backtrack_stack.top();
            backtrack_stack.pop();

            visit(cur_tree_node);

            cur_tree_node = cur_tree_node->right_child;
        }
    }
}


/*!
 * @brief 子树后序遍历(递归)
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param visit 访问函数
 */
template<class TData>
void BinaryTree<TData>::PostorderTraversalOfSubtreeRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                              void (*visit)(BinaryTreeNode<TData>* node))
{
    if (subtree_root == NULL) {
        return;
    }

    PostorderTraversalOfSubtreeRecursive_(subtree_root->left_child, visit);
    PostorderTraversalOfSubtreeRecursive_(subtree_root->right_child, visit);

    visit(subtree_root);
}


/**
 * @brief 子树后序遍历(非递归)
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param visit 访问函数
 */
template <class TData>
void BinaryTree<TData>::PostorderTraversalOfSubtreeNonRecursive_(BinaryTreeNode<TData>* subtree_root,
                                                                 void (*visit)(BinaryTreeNode<TData>*))
{
    stack<PostorderBacktrackStackNode<TData> > backtrack_stack;

    BinaryTreeNode<TData>* cur_tree_node = subtree_root;

    do {
        // 一直向左子树方向搜索(等于在做深度优先搜索DFS)
        while (cur_tree_node != NULL) {
            PostorderBacktrackStackNode<TData> node(cur_tree_node);
            backtrack_stack.push(node);
            cur_tree_node = cur_tree_node->left_child;
        }

        bool cur_tree_node_left_backtrack_unfinished = true;
        while (cur_tree_node_left_backtrack_unfinished && !backtrack_stack.empty()) {

            PostorderBacktrackStackNode<TData> cur_backtrack_node = backtrack_stack.top();
            backtrack_stack.pop();

            cur_tree_node = cur_backtrack_node.node;

            if (cur_backtrack_node.tag == PostorderBacktrackStackNode<TData>::LEFT_BACK_TRACKING) {
                cur_backtrack_node.tag = PostorderBacktrackStackNode<TData>::RIGHT_BACK_TRACKING;
                backtrack_stack.push(cur_backtrack_node);
                cur_tree_node = cur_tree_node->right_child;

                cur_tree_node_left_backtrack_unfinished = false;

            } else if (cur_backtrack_node.tag == PostorderBacktrackStackNode<TData>::RIGHT_BACK_TRACKING) {
                visit(cur_tree_node);
            }
        }
    } while (!backtrack_stack.empty());
}


/**
 * @brief 子树层序遍历
 * @tparam TData 节点数据模板类型
 * @param subtree_root 子树根节点指针
 * @param visit 访问函数
 */
template<class TData>
void BinaryTree<TData>::LevelOrderTraversalOfSubtree_(BinaryTreeNode<TData>* subtree_root,
                                                      void (*visit)(BinaryTreeNode<TData>* node))
{
    queue<BinaryTreeNode<TData>*> traversal_queue;

    BinaryTreeNode<TData>* cur = subtree_root;
    traversal_queue.push(cur);

    while (!traversal_queue.empty()) {
        cur = traversal_queue.front();
        traversal_queue.pop();

        visit(cur);

        if (cur->left_child != NULL) {
            traversal_queue.push(cur->left_child);
        }

        if (cur->right_child != NULL) {
            traversal_queue.push(cur->right_child);
        }
    }
}


/*!
 * @brief 子树打印
 * @tparam TData 结点数据模板类型
 * @param subtree_root 子树根节点
 */
template<class TData>
void BinaryTree<TData>::PrintSubTree_(BinaryTreeNode<TData>* subtree_root) {

    if (subtree_root == NULL) {
        return;
    }

    cout << subtree_root->data;

    if (subtree_root->left_child != NULL || subtree_root->right_child != NULL) {

        cout << '(';

        this->PrintSubTree_(subtree_root->left_child);

        cout << ',';

        if (subtree_root->right_child != NULL) {
            this->PrintSubTree_(subtree_root->right_child);
        }

        cout << ')';
    }
}


/*!
 * @brief 使用前序遍历和中序遍历结果, 创建二叉子树(递归)
 * @param preorder_list 前序遍历字符串
 * @param inorder_list 后序遍历字符串
 * @param length 字符串长度
 * @param subtree_root 子树根结点
 */
template<class TData>
bool BinaryTree<TData>::CreateSubtreeByPreorderAndInorderList_(TData* preorder_list,
                                                               TData* inorder_list,
                                                               int length,
                                                               BinaryTreeNode<TData>*& subtree_root)
{
    if (length == 0) {
        return true;
    }

    int pivot = 0;
    TData cur_root_data = *preorder_list;

    while (cur_root_data != inorder_list[pivot]) {
        pivot++;
    }

    subtree_root = new BinaryTreeNode<TData>(cur_root_data);
    if (subtree_root == NULL) {
        cerr << "存储分配错误!" << endl;
        return false;
    }

    bool res = CreateSubtreeByPreorderAndInorderList_(preorder_list + 1,
                                                      inorder_list,
                                                      pivot,
                                                      subtree_root->left_child);
    if (!res) {
        return false;
    }

    res = CreateSubtreeByPreorderAndInorderList_(preorder_list + pivot + 1,
                                                 inorder_list + pivot + 1,
                                                 length - pivot - 1,
                                                 subtree_root->right_child);

    return res;
}


/*!
 * @brief 判断两颗二叉树是否相同(递归)
 * @tparam TData 结点数据模板类型
 * @param root1 根节点a
 * @param root2 根节点2
 * @return 是否相同
 */
template<class TData>
bool BinaryTree<TData>::Equal(BinaryTreeNode<TData>* root1, BinaryTreeNode<TData>* root2) {
    if (root1 == NULL && root2 == NULL) {
        return true;
    }

    if (root1 != NULL && root2 != NULL && root1->data == root2->data
        && BinaryTree<TData>::Equal(root1->left_child, root2->left_child)
        && BinaryTree<TData>::Equal(root1->right_child, root2->right_child))
    {
        return true;
    }

    return false;
}


 /*!
  * @brief 重载==
  * @tparam TData 类型模板参数
  * @param binary_tree_1 二叉树1
  * @param binary_tree_2 二叉树2
  * @return
  */
template<class TData>
bool operator == (const BinaryTree<TData>& binary_tree_1, const BinaryTree<TData>& binary_tree_2) {
    return (BinaryTree<TData>::Equal(binary_tree_1.Root(), binary_tree_2.Root()));
}


template<class TData>
ostream& operator << (ostream& out, BinaryTree<TData>& binary_tree) {
    out << "二叉树的前序遍历\n";
    binary_tree.Traverse(binary_tree.Root(), out);
    out << endl;
    return out;
}


#endif //CYBER_DASH_BINARY_TREE_H