构建一个不完整的二叉树

Question

我正在尝试根据文本文件中提供的数据构建一个不完整的二叉树

2
3 8
2 10 0 12
1 8 0 0 4 0

这将形成这样的树：

我大概知道我需要做什么，我想：

从文件中逐行读入。
将数组传递给构建函数。
在构建树时，树数据类型将跟踪它添加到指针数组中的最后一个节点（例如，如果我们刚刚添加完文本文件的第 3 行，则前一个节点数组看起来像是指向包含 [2 10 12]
当我们开始添加第 4 行时，我们创建了一个 3*2=6 长度的数组来存储指向我们添加的节点的指针。
我们遍历前一个运行（包含 [2 10 12]）的指针数组，并为通过的任何非零键创建左右子节点。我们将指向这些节点的指针放在我们的 6 长数组中。
当我们得到一个空行时，我们就完成了。

我运行遇到的问题是，我不确定如何存储指向节点的指针数组，每次调用构建函数时节点的大小都会发生变化，并且是 class 变量（对于树 class）。我这样做是对的吗？有没有更简单的方法来解决这个问题？

Answer 1

为什么不使用 std::vector 而不是数组？它的行为与数组完全一样，但可以调整大小。

用法示例：

using namespace std;
Node *a = new Node;
vector<Node*> vec;
vec.push_back(a);

Answer 2

与二维数组一样，array[row][column]，您可以使用 2D vector 即。 vector< vector<int> > V 是向量的向量。

在vector< vector<int> > V中，内部向量表示行，外部向量表示列(for your understanding I just tell)。

此处二维矢量可以调整大小。不必每个列大小都相等。您可以处理 push, pop 并且可以根据您的内存大小存储数据。

示例：

您可以这样调整大小：

int num_of_col = 5;
int num_of_row = 9;
double init_value = 3.14;

vector< vector<double> > matrix;
//now we have an empty 2D-matrix of size (0,0). Resizing it with one single command:
matrix.resize( num_of col , vector<double>( num_of_row , init_value ) );
// and we are good to go ...

你可以在这里学习vector

构建一个不完整的二叉树

Building an incomplete binary tree

c++

binary-tree

data-structures