存储二叉树的建立

存储二叉树的建立（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;
}