[数据结构与算法]C++根据前序遍历建立二叉树与三种遍历操作

在看到数据结构二叉树部分时，想利用C++实现二叉树的建立与遍历操作，在参考部分网上代码后，自己进行了总结，直接贴代码：

首先要实现一个二叉树类，主要操作有三：1.创建二叉链表节点结构体 2.前序建立二叉树 3.三种遍历操作。

class BiTree /*这是一个最基本的二叉树类，所有的操作都在这个类里实现*/
{
public:
	BiTree()/*默认构造函数，对根节点进行初始化操作*/
	{
		root = new BiTreeNode(-1,nullptr,nullptr);
	}
	struct BiTreeNode /*定义一个基本二叉链表的节点*/
	{
		int val; //节点值//
		BiTreeNode *lchild; //左孩子节点
		BiTreeNode *rchild;//右孩子节点
		BiTreeNode(int val):val(val),lchild(nullptr),rchild(nullptr) {}//二叉链表构造函数1，一个参数
		BiTreeNode(int val, BiTreeNode *lchild, BiTreeNode *rchild) :val(val), lchild(lchild), rchild(rchild) {} //二叉链表构造函数2，三个参数
	};
	
    /*根据前序创建二叉链表*/
	void Create_BiTree(vector<int> &nums,int index)/*nums为需要建立的二叉树数值，index为索引下标*/
	{
		root = make_Tree(nums,index);//这里是重点，思路是递归
	}
	
/*这个函数是建立二叉树的重点，思想是通过不断递归实现前序二叉树建立*/
	BiTreeNode* make_Tree(vector<int> &nums, int &index)//nums传入引用以免nums进行复制占用内存。index必须传入引用，递归时索引的变化非常重要，必须要保证在同一块内存对索引进行操作。
	{
		BiTreeNode *T = NULL;//初始化为NULL
		if (index < nums.size() && nums[index] != -1)//索引不能超出数组。这里我们定义-1为一个空标志，其意味着某个二叉树节点为NULL；
		{
			T = new BiTreeNode(-1);//二叉链表构造函数1进行初始化，-1的数值无所谓，但是左右孩子节点必须为null。
			T->val = nums[index];//节点值进行赋值(先根节点)
			T->lchild = make_Tree(nums,++index);//左孩子递归(然后左子树)
			T->rchild = make_Tree(nums,++index);//右孩子递归(最后右子树)
		}//前序：根-左子树-右子树
		return T;//返回就是在回溯
	}
//很平常的前序遍历过程，同样利用递归
	void _PrevOrOrder(BiTreeNode *_root)
	{
		BiTreeNode *temp = _root;//定义一个中间指针
		if (temp == nullptr) return;//如果指针为null，回溯
		
		cout << temp->val << " ";//先输出根节点
		_PrevOrOrder(temp->lchild);//再递归左子树
		_PrevOrOrder(temp->rchild);//最后递归右子树
	}
//中序遍历
	void _InOrder(BiTreeNode *_root)
	{
		BiTreeNode *temp = _root;
		if (temp == nullptr) return;

		_InOrder(temp->lchild);
		cout << temp->val << " ";
		_InOrder(temp->rchild);
	}
//后序遍历
	void _PostOrder(BiTreeNode* _root)
	{
		BiTreeNode *temp = _root;
		if (temp == nullptr) return;
		_PostOrder(temp->lchild);
		_PostOrder(temp->rchild);
		cout<<temp->val<<" ";
	}
	/* 为根节点留一个访问接口*/
	BiTreeNode* Get_root()
	{
		return root;//返回根节点
	}
	
private:
	BiTreeNode *root;//将根节点进行私有封装
};

最后需要添加一个实例进行测试。如下图，紫色部分为实际需要建立的二叉树，但是在写程序时，必须要添加红色部分的节点。我们规定当递归到-1时(红色部分)，说明此时已经到头了，这个地方是个NULL，必须要进行回溯了。那么，你可能很奇怪为什么左子树叶子节点需要添加-1，右子树叶子加点不需要，难道右子树不需要知道何时停止递归进行回溯吗？当然不是啦，我们可以发现在make_Tree（）函数中有个判断条件（index < nums.size()）这其实就是在告诉右子树何时停止递归，索引超过数组当然不行了。

我们现在再次分析下，对于下图这样的二叉树(紫色部分)，其前序遍历结果为{1，2，3，4，5，6}，我们如果要实现按照前序遍历结果进行二叉树建立，那么一个数组必须定义为{1，2，3，-1，-1，4，-1，-1，5，6}，其中四个-1就是下图所注红色填充部分。

我们现在考虑一个问题，还是按照前序遍历建立二叉树，如果4(表示为5的左孩子)现在变为5的右孩子，那么传入的数组还是上面那个吗？直觉告诉我们这样是不对的。在那种情况下，一个数组{1,2，3，-1，-1,4，-1，-1,5，-1,6}需要被建立，多了一个-1。因为按照前序遍历要求，5后面下一个遍历的就是左孩子，虽然我们都知道这个不存在的左孩子就是NULL，但是我们仍然需要将其在数组里表示为-1，这样程序才知道此时需要停止遍历。所以说，传入数组的形式与按照什么次序建立二叉树有很大联系！！！！

这里有个技巧，你在进行遍历时就将所有的NULL都表示出来，比如本例的{1,2，3，NULL，NULL，4，NULL，NULL，5,6，NULL，NULL,NULL,NULL,NULL}，最后一个数字后面所有的NULL全部去除(通过判断索引即可)，数组内部的NULL变为-1。

#include <iostream>
#include <vector>

class BiTree 
{
   ......... //二叉树类实现过程如上
}

int main()
{
	vector<int> v = {1,2,3,-1,-1,4,-1,-1,5,6}; //对一个二叉树按照前序遍历方式设定好数组
	BiTree mytree;
	mytree.Create_BiTree(v,0);  //0表示最初的索引值
	
	mytree._PrevOrOrder(mytree.Get_root());//前序遍历
	cout << endl;
	mytree._InOrder(mytree.Get_root());//中序遍历
	cout << endl;
	mytree._PostOrder(mytree.Get_root());//后序遍历
	
	system("pause");
	return 0;
}

打印结果：