二叉树的初始化

二叉树的初始化

问题：

给定二叉树的初始化数据，怎样动态建立一个二叉树呢？

比如我们给定这样的一组数据：{ 1, 2, 3, 4, 0, 5, 6, 0, 7 }（假设0代表空），则我们构建的二叉树是这样的:

1 / \ 2 3 / / \ 4 5 6 \ 7

思路分析：

我们可以使用一个队列，队首出一个元素，队未进两个元素，而这两个元素正好是这个队首元素的左右节点。

参考代码如下：

TreeNode* initBTree(int elements[], int size){ if (size < 1) { return NULL; } //动态申请size大小的指针数组 TreeNode **nodes = new TreeNode*[size]; //将int数据转换为TreeNode节点 for (int i = 0; i < size; i++) { if (elements[i] == 0) { nodes[i] = NULL; } else { nodes[i] = new TreeNode(elements[i]); } } queue nodeQueue; nodeQueue.push(nodes[0]); TreeNode *node; int index = 1; while (index < size) { node = nodeQueue.front(); nodeQueue.pop(); nodeQueue.push(nodes[index++]); node->left = nodeQueue.back(); nodeQueue.push(nodes[index++]); node->right = nodeQueue.back(); } return nodes[0];}

下面是一个测试代码，我们可以看看结果：

#pragma once#include #include #include using namespace std;//Definition for binary treestruct TreeNode{ int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};//初始化一个二叉树TreeNode* initBTree(int elements[], int size);//树的前序遍历void preOrder(TreeNode *root, vector &result);//树的中序遍历void inOrder(TreeNode *root, vector &result);//树的后序遍历void postOrder(TreeNode *root, vector &result);//vector的遍历void traverse(vector nums);

源代码实现：

#include "tree.h"TreeNode* initBTree(int elements[], int size){ if (size < 1) { return NULL; } //动态申请size大小的指针数组 TreeNode **nodes = new TreeNode*[size]; //将int数据转换为TreeNode节点 for (int i = 0; i < size; i++) { if (elements[i] == 0) { nodes[i] = NULL; } else { nodes[i] = new TreeNode(elements[i]); } } queue nodeQueue; nodeQueue.push(nodes[0]); TreeNode *node; int index = 1; while (index < size) { node = nodeQueue.front(); nodeQueue.pop(); nodeQueue.push(nodes[index++]); node->left = nodeQueue.back(); nodeQueue.push(nodes[index++]); node->right = nodeQueue.back(); } return nodes[0];}void preOrder(TreeNode *root, vector &result){ if (root) { result.push_back(root->val); preOrder(root->left, result); preOrder(root->right, result); }}void inOrder(TreeNode *root, vector &result){ if (root) { inOrder(root->left, result); result.push_back(root->val); inOrder(root->right, result); }}void postOrder(TreeNode *root, vector &result){ if (root) { postOrder(root->left, result); postOrder(root->right, result); result.push_back(root->val); }}void traverse(vector nums){ vector::size_type size = nums.size(); for (size_t i = 0; i < size; i++) { cout << nums[i] << ' '; } cout << endl;}int main(){ int nums[] = { 1, 2, 3, 4, 0, 5, 6, 0, 7 }; TreeNode *root = initBTree(nums, 9); vector preResult; vector inResult; vector postResult; preOrder(root, preResult); inOrder(root, inResult); postOrder(root, postResult); cout << "前序遍历的结果：" << '\n'; traverse(preResult); cout << "中序遍历的结果：" << '\n'; traverse(inResult); cout << "后序遍历的结果：" << '\n'; traverse(postResult); return 0;}

运行结果如下：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。