存储二叉树的建立

存储二叉树的建立,第1张

存储二叉树的建立(HHUclass="superseo">数据结构实验)
  • 要求
  • 实现
    • 思想
    • 代码

要求

创建二叉树结点数据的策略有三个,如下:

  1. 将第一个要创建的元素插入成为根节点。
  2. 将元素值与结点值比较,如果元素值大于结点值,将此元素送往结点的右儿子结点,如果右儿子结点不是空的,需要重复比较,否则创建结点将元素值插入。
    3)如果元素值小于结点值,将此元素送往结点的左儿子结点,如果左儿子结点不是空的,需要重复比较,否则创建结点将此元素值插入。
    例如:二叉树结点值输入的数据顺序是5,6,4,8,2,3,7,1,9。按照上述策略创建的二叉树,如下图所示:

实现 思想

通过递归的方式对传入的数组不断进行比较和递归

代码
/************************************************************************************************************/
/**************按【实现提示】内容创建线索二叉树,完成后使用中序遍历将二叉树的内容输出。**********************/
/************************************************************************************************************/

#include 
#include 
#include "TreeNode.h"
using namespace std;

class TreeSet {
public:
	
	void setNodeSave(TreeNode* currNode, int n) {
		if (currNode->val>n)
		{
			if (!currNode->left)
			{
				TreeNode* inside = new TreeNode(n);
				currNode->left = inside;
				return;
			}
			else
				setNodeSave(currNode->left, n);
		}
		else
		{
			if (!currNode->right) {
				TreeNode* inside = new TreeNode(n);
				currNode->right = inside;
				return;
			}
			else
				setNodeSave(currNode->right, n);
		}
	}
	TreeNode* treeSet(vector<int> nums) {
		TreeNode* root = NULL;
		if (!nums.empty())root = new TreeNode(nums[0]);
		for (int i = 1; i < nums.size(); i++)
		{
			setNodeSave(root, nums[i]);
		}
		return root;
	}
	void inorder(TreeNode* root, vector<int>& res) {
		if (!root) {
			return;
		}
		inorder(root->left, res);
		res.push_back(root->val);
		inorder(root->right, res);
	}

	std::vector<int> RecInorderTraversal(TreeNode* root)// 中序递归
	{
		vector<int> res;
		inorder(root, res);
		return res;
	}
};

int main() {
	TreeSet runWay;
	int num;
	vector<int> nums;
	cout << "开始测试函数,输入-1截止:" << endl;
	cin >> num;
	while (num != -1) {
		nums.push_back(num);
		cin >> num;
	}
	auto root = runWay.treeSet(nums);
	nums = runWay.RecInorderTraversal(root);
	for (int i = 0; i < nums.size(); i++)cout << nums[i] << ' ';
	return 0;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/874800.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-05-13
下一篇 2022-05-13

发表评论

登录后才能评论

评论列表(0条)

保存