C++实现二叉树层序输入 |21xrx.com

C++实现二叉树层序输入

2023-07-02 15:30:49 深夜i -- --

C++ 二叉树层序输入

二叉树是计算机科学领域中非常重要的数据结构之一。在编程中，二叉树可以用来解决很多问题，如搜索、排序和图形处理等。C++语言有丰富的数据结构库，可以很方便地实现二叉树。本文便是介绍如何使用C++实现二叉树的层序输入操作。

在二叉树层序输入中，我们需要按照二叉树的层次顺序逐个输入每个节点的数值。一般来说，我们可以使用队列来实现这一功能。下面简要介绍具体实现过程：

首先，我们需要定义一个结构体TreeNode，该结构体用于表示二叉树节点，并包括以下成员变量和方法：

struct TreeNode {

int val;

TreeNode* left;

TreeNode* right;

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

};

其中，val表示节点编号，left和right表示该节点的左右孩子。

下面，我们需要定义一个函数来实现二叉树的层序输入。该函数需要接受一个整型数组作为参数，并返回一个指向根节点的指针：

TreeNode* LevelOrderInput(vector & nums) {

if (nums.empty()) return nullptr; // 处理特殊情况，即数组为空

TreeNode* root = new TreeNode(nums[0]); // 创建根节点

queue q{{root}}; // 创建队列，将根节点加入队列

int i = 1; // i表示当前处理到的数组下标

while (i < nums.size()) {

TreeNode* cur = q.front(); // 取出队头节点

q.pop();

if (i < nums.size() && nums[i] != -1) { // 处理左孩子

cur->left = new TreeNode(nums[i]);

q.push(cur->left);

}

i++;

if (i < nums.size() && nums[i] != -1) { // 处理右孩子

cur->right = new TreeNode(nums[i]);

q.push(cur->right);

}

i++;

}

return root; // 返回根节点

}

在LevelOrderInput函数中，我们依次取出队列中的每个节点，处理其左右孩子，将孩子加入队列中。由于二叉树是顺序存储的，因此输入数组中我们需要加入一个特殊的标记（如-1），表示该节点下面没有孩子。

最后，我们需要编写一个测试代码来验证上述函数的正确性：

int main() {

vector nums = -1;

TreeNode* root = LevelOrderInput(nums);

// 打印树的结构

queue q{{root}};

while (!q.empty()) {

int n = q.size();

for (int i = 0; i < n; i++) {

TreeNode* node = q.front();

q.pop();

cout << node->val << ' ';

if (node->left) q.push(node->left);

if (node->right) q.push(node->right);

}

cout << endl;

}

return 0;

}

运行结果：

2 3

4 5 6

上述代码中，我们使用了队列来按照层序遍历的方式打印出输入的二叉树结构，以验证我们的输入代码的正确性。

通过以上步骤，我们可以成功地使用C++语言实现二叉树的层序输入。这样，在编写和调试二叉树的相关算法时，就能够简单、快速地完成二叉树的构造。

上一篇: idea打包java可执行jar包

下一篇: C++面向对象程序设计第二版与第三版有哪些不同？

评论区

()

相似文章