最大二叉树

给定一个不含重复元素的整数数组,以此构建最大二叉树。

最大二叉树有如下特点:

  • 二叉树的根对应数组中的最大值
  • 左子树是原数组最大值左边的子数组构建出的最大二叉树
  • 右子树是原数组最大值右边的子数组构建出的最大二叉树

下面是一个经典例子:

image-20201013100218048

树的构建一般都使用 递归 的方式。

在递归时,为了避免为子数组开辟额外的存储空间,可以选择在原数组上遍历。

maxBiTree.h

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
26
27
28
29
#ifndef MAXBITREE_H
#define MAXBITREE_H

#include <vector>
using namespace std;

/* 声明一个二叉节点 */
template <class T>
class BiNode {
public:
T data; // 二叉节点的数据
BiNode<T> *left; // 二叉节点的左子树地址,叶子节点为nullptr
BiNode<T> *right; // 二叉节点的右子树地址,叶子节点为nullptr
BiNode(T); // 只能从已有数据初始化一个二叉节点
};

/* 定义一个最大二叉树类 */
template <class T>
class MaxBiTree {
public:
BiNode<T> *root; // 根节点,是一个二叉节点类型
void construct(const vector<T>&); // 给定数组构建最大二叉树
void printPreOrder(); // 打印前序遍历结果
private:
BiNode<T>* _r_construct(const vector<T>&, int, int); // 递归构建
void _r_preorder(const BiNode<T>*); // 递归前序遍历
};

#endif

maxBiTree.cpp

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <vector>
#include "maxBiTree.h"
using namespace std;

template <class T>
BiNode<T>::BiNode(T d): data(d) {}

/* 递归构建二叉树 */
template <class T>
BiNode<T>* MaxBiTree<T>::_r_construct(const vector<T>& vec, int begin, int end) {
if (begin >= end ) return nullptr;
int maxv_index = begin;
for (int i = begin; i < end; ++i) {
if (vec[i] > vec[maxv_index]) {
maxv_index = i;
}
}
BiNode<T> *node = new BiNode<T>(vec[maxv_index]);
node->left = _r_construct(vec, begin, maxv_index);
node->right = _r_construct(vec, maxv_index+1, end);
return node;
};

template <class T>
void MaxBiTree<T>::construct(const vector<T>& vec) {
cout << "call _r_construct ..." << endl;
root = _r_construct(vec, 0, vec.size());
}

/* 递归前序遍历 */
template <class T>
void MaxBiTree<T>::_r_preorder(const BiNode<T> *node) {
cout << node->data << ' ';
if (node->left != nullptr) _r_preorder(node->left);
if (node->right != nullptr) _r_preorder(node->right);
}

template <class T>
void MaxBiTree<T>::printPreOrder(){
_r_preorder(root);
}

/* Explicit Instantiation */
/* 显式实例化 */
template class BiNode<int>;
template class MaxBiTree<int>;

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
#include <vector>
#include "maxBiTree.h"
using namespace std;

int main(){
vector<int> vec = {3,2,1,6,0,5};
MaxBiTree<int> mbtree;
mbtree.construct(vec);
mbtree.printPreOrder();
return 0;
}

测试

1
2
3
> g++ main.cpp maxBiTree.cpp && a.exe && del a.exe
call _r_construct ...
6 3 2 1 5 0

用这个例子好好复习了一下 C++, emmm

----- For reprint please indicate the source -----
0%