数据结构——二叉树的操作（1）（C++）

我们继续来学习二叉树的实现：

二叉树结点的定义

这里二叉树结点和单链表的结点差不多，值不过，二叉树结点要储存左结点的指针和右节点的指针：

//二叉树的结点
template<class T>
struct BTreeNode
{
    BTreeNode()
        :_data(0)
    {

    }

    BTreeNode(const T& data)
        :_data(data)
    {

    }
    //数据域
    T _data;

    //左孩子（左子树）
    BTreeNode<T>* _leftChild = nullptr;

    //右孩子（右子树）
    BTreeNode<T>* _rightChild = nullptr;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

然后我们就可以定义一棵二叉树了：

//二叉树
template<class T>
class BTree
{
    typedef BTreeNode<T> _Node;
public:
    BTree()
        :_root(nullptr)
    {

    }


private:
    _Node* _root;  
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这样的结构，定义了一个空结点的二叉树：

构建二叉树

我们现在要构建一个二叉树，这里为了方便我们构建，我们插入元素跟root的data相比，如果比root的data大，就插入root的右子树，否则就插入root的左子树：
那么什么叫插入呢？其实就是看这个位置是不是nullptr，如果是nullptr就以data来创建一个结点。

这里有一个难点，我们的二叉树是以递归的方式来创建，这里我们要记住一个原则，递归创建不要过多探究细节，只关注当前的任务：

所以，我们大概可以理清思路：

1. 在当前位置插入，如果为空，就以data创建结点
2. 如果当前位置不为空，若data > root->data 插入右子树
3. 若data < root->data 插入左子树

    //插入
    _Node* _Insert(_Node*& root,const T& data)
    {
        if(root == nullptr)
        {
            root = new _Node(data);
            return root;
        }
        else if(root->_data < data)
        {
            return _Insert(root->_rightChild,data);
        }
        else if(root ->_data > data)
        {
            return _Insert(root->_leftChild,data);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

现在我们可以用这个函数来插入结点，创建二叉树，为了更好封装这个函数，我们可以再封装一层：

    //插入
    _Node* Insert(const T& data)
    {
        return _Insert(_root,data);
    }
1
2
3
4
5

好了，现在我们可以创建一棵二叉树，现在我们可以打印这棵树，这就涉及到二叉树最经典的三个算法了。

前中后序遍历

前序遍历

二叉树是以递归方式定义的，所以我们遍历二叉树也要以递归来方式遍历，前序遍历方式是以 根 左 右 的顺序来遍历的：

既然是以递归方式来遍历，所以我们要弄清楚对于当前结点我们要做什么，对于前序遍历，当前结点要做的就是打印自身的值：

    //前序遍历
    void  _PrveOrder(_Node* root)
    {
        std::cout<<root->_data << " ";
    }
1
2
3
4
5

那么打印完了之后，我们还要依次打印左子树和右子树的值：

    //前序遍历
    void  _PrveOrder(_Node* root)
    {
        std::cout<<root->_data << " ";
        _PrveOrder(root->_leftChild);
        _PrveOrder(root->_rightChild);
    }
1
2
3
4
5
6
7

那么什么时候停止呢？如果遇到空结点，就表示到了尽头，所以这个时候就可以返回了：

    //前序遍历
    void  _PrveOrder(_Node* root)
    {
        if(root==nullptr)
        {
            return;
        }

        std::cout<<root->_data << " ";
        _PrveOrder(root->_leftChild);
        _PrveOrder(root->_rightChild);
    }
1
2
3
4
5
6
7
8
9
10
11
12

我们可以测试一下：

int main()
{
    BTree<int> bt;

    bt.Insert(233);
    bt.Insert(1);
    bt.Insert(20);

    bt.PrveOrder();
    std::cout<<std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

中序遍历和后序遍历

中序遍历和后序遍历跟前序遍历是一样的：

    //中序遍历
    void  _InOrder(_Node* root)
    {
        if(root==nullptr)
        {
            return;
        }

        _InOrder(root->_leftChild);
        std::cout<<root->_data << " ";
        _InOrder(root->_rightChild);
    }

    //后序遍历
    void  _PostOrder(_Node* root)
    {
        if(root==nullptr)
        {
            return;
        }

        _PostOrder(root->_leftChild);
        _PostOrder(root->_rightChild);
        std::cout<<root->_data << " ";
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int main()
{
    BTree<int> bt;

    bt.Insert(20);
    bt.Insert(12);
    bt.Insert(35);

    bt.PrveOrder();
    std::cout<<std::endl;
    bt.InOrder();
    std::cout<<std::endl;
    bt.PostOrder();
    std::cout<<std::endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

几行代码就可以实现前中后序遍历，递归非常神奇，但是如果是第一次接触递归，可能会有点迷糊，我之前写了一篇递归思想的博客，如果还是不太明白的可以点击这里：

https://blog.csdn.net/qq_67693066/article/details/133562585