/*基础概念参照：*/

数据结构 --- c语言二叉树基础(无序二叉树)https://blog.csdn.net/weixin_60569662/article/details/123083815

pre：树框架的构建

template<class T>
struct Node
{
	T   data;
	Node* pLeft;//左孩子	
	Node* pRight;//右孩子
 
	Node(const T& data)
	{
		this->data = data;
		pLeft = pRight = nullptr;
	}
};
template<class T>
class Tree
{
public:
	Tree() { pRoot = nullptr; }
	~Tree() { _clear(pRoot); }
	void clear(Node*pDel) 
	{
		_clear(pDel)
	}
	bool insert(const T& data)
	{return _insert(data,pRoot); }
	void travel(int type);//-1前序遍历 0中序遍历 1后序遍历
 
private:	
	Node* pRoot;
private:    //也可以用二级指针完成，引用更常用一点
	bool _insert(const T& data,Node*&pRoot);
	void _clear(Node* pDel);
 
	//先序
	void _preTravel(TreeNode* root);
	//中序
	void _midTravel(TreeNode* root);
	//后序
	void _lstTravel(TreeNode* root);
};

一、无序二叉树的插入

注意：①利用二叉树的递归特性(不断成为新的根节点

           ②利用Ddata来限制是插左孩子还是右孩子->注意判断放置的位置！！同时利用bool返回值来控制。

           ③第一个if插成功了，记得return true；

template<class T>
bool Tree::_insert(const T& data, Node*& pRoot)
{
	//递归终止条件
	if (pRoot == nullptr)
	{
		Node* pNew = new Node(data);
		pRoot = pNew;
		return true;
	}
	//控制插入左孩子还是右孩子
	if (Ddata == pRoot->data)return false;
	//递归
	if (_insert(data, pRoot->pLeft))return true;
	return _insert(data, pRoot->pRight);
}

 测试代码：

	Tree<int> mytree;
	int arr[] = { 1,2,Ddata,4,5,Ddata,Ddata,Ddata,3,Ddata,6,Ddata,7,Ddata,Ddata};
	for (auto v : arr)
	{
		mytree.insert(v);
	}

 实现的二叉树如下图：

 二、无序二叉树的遍历：

1.简述：

• 前序遍历：根在前面，根左右

• 中序遍历：左根右

• 后序遍历：根在后面，左右根

2.以上图的二叉树为例，三种结果为：

        前序遍历
        1 2 4 5 3 6 7
        中序遍历
        2 5 4 1 3 6 7
        后序遍历
        5 4 2 7 6 3 1

3.利用递归，代码的实现十分简洁   

template<class T>
void Tree::travel(int type)
{
	switch (type)
	{
	case -1:
		cout << "前序遍历" << endl;
		_preTravel(pRoot); break;
	case 0:
		cout << "中序遍历" << endl;
		_midTravel(pRoot); break;
	case 1:
		cout << "后序遍历" << endl;
		_lstTravel(pRoot); break;
	}
	cout << endl;
}
template<class T>
void Tree::_preTravel( Node*& root)
{//前序遍历：根左右
	if (root == nullptr)return;//递归终止条件一定不能忘记
	cout << root->data << " ";
	_preTravel(root->pLeft);
	_preTravel(root->pRight);
}
template<class T>
void Tree::_midTravel( Node*& root)
{//前序遍历：左根右
	if (root == nullptr)return;
	_midTravel(root->pLeft);
	cout << root->data << " ";
	_midTravel(root->pRight);
}
template<class T>
void Tree::_lstTravel( Node*& root)
{//前序遍历：左右根
	if (root == nullptr)return;
	_lstTravel(root->pLeft);
	_lstTravel(root->pRight);
	cout << root->data << " ";
}

 注：因为有叶子结点（Ddata=9999）作为切换左右孩子的条件->所以，在此输出的时候，在上面的代码可以再添加一下控制，不让叶子结点的data输出。(为了代码的简洁可读性，此处没加)

三、无序二叉树遍历的理论分析

1.利用递归的思想，里面最先出来+前中后序遍历的限制，就很容易分析出！！！

        前序遍历
        1 2 4 5 3 6 7
        中序遍历
        2 5 4 1 3 6 7
        后序遍历
        5 4 2 7 6 3 1

 时时自测一下，以中序为例，很容易犯错的是，F在H前面，递归到最深处，也得满足左(H)根(F)右，H必定在F的左侧。

2.已知中序+前or后可推导出原树

    已知 中序遍历 和 先序遍历  能推导出  后序遍历
    已知 中序遍历 和 后序遍历  能推导出  先序遍历
    已知 先序遍历 和 后序遍历 , 推导不出

 其他参考：二叉树的前序、中序、后序遍历（个人笔记） - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/73438175

四、无序二叉树的释放

template<class T>
void Tree::_clear(Node*& pDel)
{
	//错误思路:遍历一遍，依次释放
	//利用递归特性:逐一释放
	if (pDel == nullptr)return;//注意递归终止条件
	_clear(pDel->pLeft);
	_clear(pDel->pRight);
	delete pDel;
	pDel = nullptr;
}

利用递归特性->递归释放！！！！！