二叉树的初始化

问题:

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

比如我们给定这样的一组数据:{ 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<TreeNode*> 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];
}

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

头文件声明(tree.h):

#pragma once
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//Definition for binary tree
struct 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<int> &result);
//树的中序遍历
void inOrder(TreeNode *root, vector<int> &result);
//树的后序遍历
void postOrder(TreeNode *root, vector<int> &result);
//vector的遍历
void traverse(vector<int> 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<TreeNode*> 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<int> &result)
{
	if (root)
	{
		result.push_back(root->val);
		preOrder(root->left, result);
		preOrder(root->right, result);
	}
}

void inOrder(TreeNode *root, vector<int> &result)
{
	if (root)
	{
		inOrder(root->left, result);
		result.push_back(root->val);
		inOrder(root->right, result);
	}
}

void postOrder(TreeNode *root, vector<int> &result)
{
	if (root)
	{
		postOrder(root->left, result);
		postOrder(root->right, result);
		result.push_back(root->val);
	}
}

void traverse(vector<int> nums)
{
	vector<int>::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<int> preResult;
	vector<int> inResult;
	vector<int> postResult;
	preOrder(root, preResult);
	inOrder(root, inResult);
	postOrder(root, postResult);
	cout << "前序遍历的结果:" << '\n';
	traverse(preResult);
	cout << "中序遍历的结果:" << '\n';
	traverse(inResult);
	cout << "后序遍历的结果:" << '\n';
	traverse(postResult);
	return 0;
}

运行结果如下:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券