前序递归建立二叉树

前序递归建立二叉树

目录

前言

思路 

代码

---

  前言

上午在写二叉搜索树的最近公共祖先时,很尴尬,发现手写不出来递归建立二叉树的版本,不禁开始怀疑自己到底会不会二叉树,连最基本的建立都不会.....(趁着没人发现赶紧补习一波!!!冲冲冲!)

思路 

其实递归建立二叉树和递归遍历二叉树思路基本是一样的,无非是将原来的"读出数据" 改成"创建节点并为节点赋值",后面都是一样的递归.

我们可以使用一个标志位'@'来表示nullptr.

代码

TreeNode* CreateBiTree()
{
	char ch;
	cin >> ch;
	if (ch == '@')
		return nullptr;
	TreeNode* tempNode = (TreeNode*)new TreeNode();
	if (tempNode == nullptr)
	{
		cout << "内存分配失败";
		return NULL;
	}
	tempNode->val = ch-'0';
	cout << "请输入节点 " << ch << " 的左节点： ";
	tempNode->left = CreateBiTree();
	cout << "请输入节点 " << ch << " 的右节点： ";
	tempNode->right = CreateBiTree();
	return tempNode;
}

void preOrder(TreeNode* root)
{
	if (!root)	return;
	cout << root->val<<" ";
	preOrder(root->left);
	preOrder(root->right);
	return;
 }


int  main()
{
	TreeNode* temp;
	TreeNode* root;
	cout << "请输入根节点的值： ";
	root = CreateBiTree();
	preOrder(root);
	return 0;
}