数据结构之链式二叉树详解

链式二叉树是一种基于链表的二叉树存储实现方式，相对于基于数组的存储方式更加灵活。本文将详细讲解如何实现链式二叉树及相关操作。

数据结构定义

链式二叉树的节点定义如下：

template<class T>
struct BinaryTreeNode
{
    T m_nValue; // 节点的值
    BinaryTreeNode* m_pLeft; // 左子节点
    BinaryTreeNode* m_pRight; // 右子节点
};

链式二叉树的定义如下：

template<class T>
class BinarySearchTree
{
public:
    BinarySearchTree();
    ~BinarySearchTree();

    void insert(const T& value); // 插入节点
    void remove(const T& value); // 删除节点
    BinaryTreeNode<T>* find(const T& value); // 查找节点
    BinaryTreeNode<T>* minimum() const; // 返回最小值节点
    BinaryTreeNode<T>* maximum() const; // 返回最大值节点
    void print() const; // 中序遍历
private:
    void destroy_tree(BinaryTreeNode<T>* leaf); // 删除树节点
    void insert(const T& value, BinaryTreeNode<T>*& leaf); // 插入节点
    void remove(const T& value, BinaryTreeNode<T>*& leaf); // 删除节点
    BinaryTreeNode<T>* find(const T& value, BinaryTreeNode<T>* leaf); // 查找节点
    BinaryTreeNode<T>* minimum(BinaryTreeNode<T>* leaf) const; // 返回最小值节点
    BinaryTreeNode<T>* maximum(BinaryTreeNode<T>* leaf) const; // 返回最大值节点
    void print(BinaryTreeNode<T>* leaf) const; // 中序遍历
    BinaryTreeNode<T>* root_;
};

插入节点

插入操作是链式二叉树中比较简单的操作，比较文本值，根据大小选择左子节点或右子节点进行插入。根据文本值大小判断节点的左右子树，若某个节点的左子树或右子树为空，则在该位置插入节点，否则利用递归进行插入操作。

代码实现如下：

template<class T>
void BinarySearchTree<T>::insert(const T& value)
{
    insert(value, root_);
}

template<class T>
void BinarySearchTree<T>::insert(const T& value, BinaryTreeNode<T>*& leaf)
{
    if (leaf == nullptr) {
        leaf = new BinaryTreeNode<T>();
        leaf->m_nValue = value;
        leaf->m_pLeft = nullptr;
        leaf->m_pRight = nullptr;
    } else if (value < leaf->m_nValue) {
        insert(value, leaf->m_pLeft);
    } else {
        insert(value, leaf->m_pRight);
    }
}

删除节点

删除操作需要分为三种情况：

• 节点为叶子节点，直接删除即可。
• 节点有一个子节点，将子节点替换该节点即可。
• 节点有两个子节点，先找出该节点右子树中的最小值，将其替换该节点，再删除该最小值节点。

代码实现如下：

template<class T>
void BinarySearchTree<T>::remove(const T& value)
{
    remove(value, root_);
}

template<class T>
void BinarySearchTree<T>::remove(const T& value, BinaryTreeNode<T>*& leaf)
{
    if (leaf == nullptr) {
        return;
    }
    if (value < leaf->m_nValue) {
        remove(value, leaf->m_pLeft);
    } else if (value > leaf->m_nValue) {
        remove(value, leaf->m_pRight);
    } else {
        if (leaf->m_pLeft == nullptr && leaf->m_pRight == nullptr) {
            delete leaf;
            leaf = nullptr;
        } else if (leaf->m_pLeft == nullptr) {
            BinaryTreeNode<T>* temp = leaf->m_pRight;
            delete leaf;
            leaf = temp;
        } else if (leaf->m_pRight == nullptr) {
            BinaryTreeNode<T>* temp = leaf->m_pLeft;
            delete leaf;
            leaf = temp;
        } else {
            BinaryTreeNode<T>* temp = minimum(leaf->m_pRight);
            leaf->m_nValue = temp->m_nValue;
            remove(temp->m_nValue, leaf->m_pRight);
        }
    }
}

查找节点

查找操作也是基于链式二叉树的特点，利用文本值大小进行查找，若该节点值大于（小于）查找值，则在左子树中（右子树中）进行查找，否则查找值即为该节点值，返回之。

代码实现如下：

template<class T>
BinaryTreeNode<T>* BinarySearchTree<T>::find(const T& value)
{
    return find(value, root_);
}

template<class T>
BinaryTreeNode<T>* BinarySearchTree<T>::find(const T& value, BinaryTreeNode<T>* leaf)
{
    if (leaf == nullptr) {
        return nullptr;
    }
    if (value < leaf->m_nValue) {
        return find(value, leaf->m_pLeft);
    } else if (value > leaf->m_nValue) {
        return find(value, leaf->m_pRight);
    } else {
        return leaf;
    }
}

返回最小值节点和最大值节点

返回最小值节点和最大值节点同样是基于链式二叉树的特点，分别在左子树上和右子树上不断向下寻找，直到到达叶子节点。

代码实现如下：

template<class T>
BinaryTreeNode<T>* BinarySearchTree<T>::minimum() const
{
    return minimum(root_);
}

template<class T>
BinaryTreeNode<T>* BinarySearchTree<T>::minimum(BinaryTreeNode<T>* leaf) const
{
    if (leaf == nullptr) {
        return nullptr;
    }
    if (leaf->m_pLeft == nullptr) {
        return leaf;
    } else {
        return minimum(leaf->m_pLeft);
    }
}

template<class T>
BinaryTreeNode<T>* BinarySearchTree<T>::maximum() const
{
    return maximum(root_);
}

template<class T>
BinaryTreeNode<T>* BinarySearchTree<T>::maximum(BinaryTreeNode<T>* leaf) const
{
    if (leaf == nullptr) {
        return nullptr;
    }
    if (leaf->m_pRight == nullptr) {
        return leaf;
    } else {
        return maximum(leaf->m_pRight);
    }
}

中序遍历

中序遍历是将整棵树按照从小到大的顺序输出。

template<class T>
void BinarySearchTree<T>::print() const
{
    print(root_);
    std::cout << std::endl;
}

template<class T>
void BinarySearchTree<T>::print(BinaryTreeNode<T>* leaf) const
{
    if (leaf == nullptr) {
        return;
    }
    print(leaf->m_pLeft);
    std::cout << leaf->m_nValue << " ";
    print(leaf->m_pRight);
}

示例说明

BinarySearchTree<int> t;
t.insert(5);
t.insert(3);
t.insert(2);
t.insert(4);
t.insert(7);
t.insert(6);
t.insert(8);
t.print(); // 2 3 4 5 6 7 8
t.remove(5);
t.print(); // 2 3 4 6 7 8
t.find(6); // 返回6节点
t.minimum(); // 返回值为2的节点
t.maximum(); // 返回值为8的节点

以上代码示例展示了链式二叉树的插入、删除、查找、返回最小值节点、返回最大值节点及中序遍历操作。