二叉树平衡（有序数组创建）

骑猪看日落 2023-02-22 10:35 9阅读 0赞

## 一、前言 ##

[《二叉查找树全面详细介绍》][Link 1]中讲解了二叉树操作：搜索（查找）、遍历、插入、删除。[《二叉树遍历详解（递归遍历、非递归栈遍历，Morris遍历）》][Morris]详细讲解了二叉树遍历的几种方法。本文介绍一种二叉树平衡构建方法。

## 二、思路 ##

根据二叉树插入的规则，我们只需要按照正确顺序将元素添加到二叉树中，就可以构建一颗平衡二叉树了。

## 三、总结 ##

该方法需要额外空间记录树中所有元素，并对其排序，这个构建过程效率不高，且需要额外空间，当构建好平衡二叉树之后，如果需要添加元素，是无法直接添加，需要删除树，重新构建才行。

后面文章中会介绍几种更好构建平衡二叉树的方法。

## 四、编码实现 ##

二叉树BST<T>代码见[《二叉查找树全面详细介绍》][Link 1]有完整代码。

//==========================================================================
    /**
    * @file    : BalanceBST.h
    * @blogs   : 
    * @author  : niebingyu
    * @title   : 平衡二叉树
    * @purpose : 将一组元素，通过排序之后，通过插入构建一颗平衡二叉树
    */
    //==========================================================================
    #pragma once
    #include "GenBST.h"
    #include <algorithm>
    template<class T>
    class BalanceBST : private BST<T>
    {
    public:
    	// 平衡二叉树，通过插入让树满足平衡，只适合树的重建，不能中途插入节点
    	void createBalanceBST(T*, int);
    
        // 前序遍历二叉树
        void preorder() { BST<T>::preorder(); }
    
    	// 中序遍历
    	void inorder() { BST<T>::inorder(); }
    
    private:
    	// 平衡二叉树，通过插入让树满足平衡，只适合树的重建，不能中途插入节点
    	void balance(T data[], int first, int last);
    };
    
    // 平衡二叉树 
    template<class T>
    void BalanceBST<T>::createBalanceBST(T* data, int len)
    {
    	// 先将树清空
    	BST<T>::clear();
    
    	std::sort(data, data+len);
    	balance(data, 0, len-1);
    }
    
    template<class T>
    void BalanceBST<T>::balance(T data[], int first, int last)
    {
        if (first <= last)
        {
            int middle = (first + last) / 2;
            BST<T>::insert(data[middle]);
            balance(data, first, middle - 1);
            balance(data, middle + 1, last);
        }
    }

**测试代码**

//==========================================================================
    /**
    * @file    : BalanceBSTTest.h
    * @blogs   : https://blog.csdn.net/nie2314550441/article/details/107092408
    * @author  : niebingyu
    * @title   : 测试平衡二叉树
    * @purpose : 测试平衡二叉树
    *
    */
    //==========================================================================
    #pragma once
    #include "BalanceBST.h"
    using namespace std;
    
    #define NAMESPACE_BALANCEBSTTEST namespace NAME_BALANCEBSTTEST {
    #define NAMESPACE_BALANCEBSTTESTEND }
    NAMESPACE_BALANCEBSTTEST
    
    // 测试用例
    void Test1()
    {
        vector<int> data = { 2,1,3,4,7,5,6,9,0,8 };
    
    	BalanceBST<int> tree;
    	tree.createBalanceBST(data.data(), data.size());
    
        cout << "Test1 前序遍历: ";
        tree.preorder();
        cout << "\nTest1 中序遍历: ";
        tree.inorder();
        cout << endl;
    }
    NAMESPACE_BALANCEBSTTESTEND
    
    void BalanceBSTTest_Test()
    {
    	NAME_BALANCEBSTTEST::Test1();
    }

**执行结果：**

![20200702232620356.png][]

[Link 1]: https://blog.csdn.net/nie2314550441/article/details/107030025
[Morris]: https://blog.csdn.net/nie2314550441/article/details/107073598
[20200702232620356.png]: https://img-blog.csdnimg.cn/20200702232620356.png