数据结构初阶--二叉树（前中后序遍历递归+非递归实现+相关求算结点实现）

前一篇博客介绍了二叉树的顺序结构，是通数组来存储的，这里我们通过创建链式结构来存储，在堆上申请空间，结构如下：

template <class DateType>
struct BinaryTreeNode
{
	DateType data;//数据域
	BinaryTreeNode* leftChild;//左树指针
	BinaryTreeNode* rightChild;//右树种子很
};

二叉树的创建

通过前序遍历的数组"ABD##E#H##CF##G##"，给定一串字符串，#代表的是空树，其他的都是节点。

这里我们只需要前序遍历这串字符串来构建这棵树即可。
同样是用递归来解决这个问题：
CreatBinaryTree(root->leftChild)；让当前这个节点的左指向给递归构建左子树
CreatBinaryTree(root->rightChild)；让当前这个节点的右指向给递归构建左子树，如果当前节点为空就直接返回NULL。

//构造函数
BinaryTree()
{
	cout << "请输入根节点: " << endl;
	cout << "输入#代表结点指针指向空" << endl;
	CreatBinaryTree(root);
	if (root != NULL)
	{
		cout << "root = " << root->data << endl;
	}
	else
	{
		cout << "The BinaryTree is empty" << endl;
	}
}
//创建二叉树
void CreatBinaryTree(BinaryTreeNode<DateType>* &root)
{
	DateType ch;
	cin >> ch;
	if (ch == '#')
	{
		root = NULL;
	}
	else
	{
		root = new BinaryTreeNode<DateType>;
		root->data = ch;
		cout << "调用左孩子" << endl;
		CreatBinaryTree(root->leftChild);
		cout << "调用右孩子" << endl;
		CreatBinaryTree(root->rightChild);
	}
}

二叉树的递归遍历

前序遍历(递归实现)

前序遍历指的是先遍历根，再遍历左子树，再遍历右子树。

思想： 二叉树本身就是一种递归结构，所以通过递归来遍历这棵树，如何递归遍历呢？
是这样的，先遍历根，再遍历左子树，左子树又可以分解为，根、左子树和右子树，直到把所以左子树的部分遍历完，然后就遍历右子树，右子树又可以分解为，根、左子树和右子树。

其实在计算机中，入栈的不是结点，而是函数，当进入函数入口的时候，函数就会入栈，此时如果在函数内调用了其他函数，计算机会标记当前函数执行到哪一步，随后将调用的函数入栈，转去执行栈顶的函数，当调用函数执行完毕之后，计算机返回当前函数会查看标记执行到哪一步，继续执行，直到函数彻底执行完毕，该函数出栈

但为了更直观的理解这个过程，下面会通过图解结点入栈的方式，描述二叉树前序、中序和后序遍历的过程，下面的程序不是以函数是否结束为结点出栈的标准，而是以是否访问到该结点的data值”cout<< ->data“元素为出栈标准，更直观

图解前序遍历的递归算法

（1）假定给定的二叉树结构如下，如何对二叉树进行先序遍历

（2）首先将根节点传入，A！=NULL，遍历了A，并且指向A的指针入栈（递归的实现利用了栈），遍历A的左子树

（3）A的左子树不为空，遍历B，将B入栈，遍历B的左子树，同样，B的左子树不为空，遍历D，将D入栈，遍历D的左子树

（4）D的左子树为空，不遍历，然后D出栈开始遍历D的右子树，但是D的右子树也为空，不遍历，故D的左右子树以及本身都遍历完

（5）然后B出栈，遍历B的右子树，B的右子树不为空，遍历E，E入栈，遍历E的左子树

（6）E的左子树不为空，遍历G，G入栈，遍历G的左子树

（7）G的左子树为空，不遍历，G出栈遍历G的右子树，G的右子树也为空，故不遍历

（8）此时栈中存在E和A，E出栈，遍历E的右子树，但是E的右子树为空，故不进行遍历

（9）栈中仅存A，A出栈，A的右子树不为空，遍历A的右子树，遍历C，C入栈，遍历C的左子树

（10）C的左子树为空，不遍历，C出栈，遍历C的右子树，F不为空，F入栈

（11）遍历F的左子树，为空，F出栈，遍历F的右子树，F的右子树为空，不遍历，此时栈没空，结束遍历，二叉树的全部结点有且仅有一次被访问

代码实现：

//递归前序遍历
void BinaryTreePrevOrder(BinaryTreeNode<DateType>* root)
{
    // 遍历到NULL就返回
	if (root == NULL)
	{
		return;
	}
	else
	{
		// 先遍历根
		cout << root->data <<" ";
		// 左子树交给BinaryTreePrevOrder这个函数去遍历
		BinaryTreePrevOrder(root->leftChild);
		// 右子树交给BinaryTreePrevOrder这个函数去遍历
		BinaryTreePrevOrder(root->rightChild);
	}
}

中序遍历（递归实现）

中序遍历指的是先遍历左子树，再遍历根，再遍历右子树。
思想： 二叉树本身就是一种递归结构，所以通过递归来遍历这棵树，如何递归遍历呢？
是这样的，先遍历左子树，左子树又可以分解为，左子树、根和右子树，直到把所以左子树的部分遍历完，然后就遍历根，再遍历右子树，右子树又可以分解为，左子树、根和右子树。

图解前序遍历的递归算法

（1）将A入栈，遍历A的左子树，但是不遍历A，因为访问A的语句是在遍历A的左子树之后

（2）A的左子树不为空，B入栈，遍历B的左子树，同样不遍历B，B的左子树不为空，D入栈，遍历D的左子树

（3）D的左子树为空，不进行遍历，D出栈并访问D，接着遍历D的右子树

（4）D的右子树为空，不遍历，此时B出栈并且访问B，然后遍历B的右子树，B的右子树不为空，E入栈，遍历E的左子树

（5）E的左子树不为空，G入栈，遍历G的左子树

(6)G的左子树为空，不遍历，G出栈并且访问，接着遍历G的右子树，G的右子树为空，不遍历，随后E出栈并且访问，遍历E的右子树

（7）E的右子树为空，不遍历，随后A出栈并且访问，遍历A的右子树，A的右子树不为空，C入栈

（8）遍历C的左子树，C的左子树为空，不遍历，C出栈并访问，遍历C的右子树，将F入栈，F是最后一个元素，出栈并访问即可

代码实现：

//递归中序遍历
void BinaryTreeInOrder(BinaryTreeNode<DateType>* root)
{
	// 遍历到NULL就返回
	if (root == NULL)
	{
		return;
	}
	else
	{
		// 左子树交给BinaryTreeInOrder这个函数去遍历
		BinaryTreeInOrder(root->leftChild);
		// 遍历根
		cout << root->data<<" ";
		// 右子树交给BinaryTreeInvOrder这个函数去遍历
		BinaryTreeInOrder(root->rightChild);
	}
}

后序遍历（递归实现）

后序遍历指的是先遍历左子树，再遍历右子树，最后遍历根。
思想： 二叉树本身就是一种递归结构，所以通过递归来遍历这棵树，如何递归遍历呢？
是这样的，先遍历左子树，左子树又可以分解为，左子树、右子树和根，直到把所以左子树的部分遍历完，然后遍历右子树，右子树又可以分解为，左子树、右子树和根,最后遍历根。

图解前序遍历的递归算法

（1）首先A入栈进行遍历左子树，A的左子树不为空，B入栈，遍历B的左子树，B的左子树不为空，D入栈，遍历D的左子树

（2）D的左子树为空，不遍历，D出栈遍历D的右子树，但由于在函数最后还需遍历自身，故出栈后紧接着入栈

（3）但由于D的右子树为空，不遍历，故D出栈并且访问，至此D访问完毕，然后B出栈访问右子树，紧接着入栈，准备执行最后的出栈访问

（4）B的右子树不为空，E入栈，并遍历E的左子树，E的左子树不为空，G入栈，并遍历G的左子树

（5）G的左子树为空，不遍历，G出栈遍历右子树，紧接着入栈（此时还没有访问G本身），G的右子树为空，不遍历，此时G的左右子树均遍历完，G出栈访问

（6）紧接着E出栈遍历右子树，紧接着入栈，为后续的出栈访问自身做准备，E的右子树为空，不遍历，E的左右子树遍历完，E出栈访问，此时栈中剩下B和A

.........................后续不再展示（懒了），最后的结果是

代码实现：

//递归后序遍历
void BinaryTreePostOrder(BinaryTreeNode<DateType>* root)
{
	if (root == NULL)
	{
		return;
	}
	else
	{
		// 左子树交给BinaryTreePostOrder这个函数去遍历
		BinaryTreePostOrder(root->leftChild);
		// 右子树交给BinaryTreePostOrder这个函数去遍历
		BinaryTreePostOrder(root->rightChild);
		//遍历根
		cout << root->data<<" ";
    }
}

层序遍历

层序遍历：设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历用到的是队列来解决，先将根入队，然后把根取出，取出的同时分别再把不为空的左节点和右节点入队，直到队列为空时就说明二叉树已经遍历完了。为了方便大家理解我在这里做了个动图演示一下：

代码实现：

//层序遍历
void BinaryTreeLevelOrder(BinaryTreeNode<DateType>* root)
{
	if (root == NULL)
	{
		return;
	}
	queue<BinaryTreeNode<DateType>*> q;
	q.push(root);
	while (!q.empty())
	{
		BinaryTreeNode<DateType>* front = q.front();
		q.pop();
		cout << front->data << " ";
		if (front->leftChild)
			q.push(front->leftChild);
		if (front->rightChild)
			q.push(front->rightChild);
	}
}

二叉树的非递归遍历

中序遍历（非递归实现）

中序遍历的递归定义：先左子树，后根节点，再右子树。

假设，你面前有一棵二叉树，现要求你写出它的中序遍历序列。如果你对中序遍历理解透彻的话，你肯定先找到左子树的最下边的节点。那么下面的代码就是理所当然的：

stack<BinaryTreeNode<DateType>*> Stack;
BinaryTreeNode<DateType>* Pointer = root;
//一直遍历到左子树最下边，边遍历边保存根节点到栈中
while (Pointer)
{	
    Stack.push(Pointer);
	Pointer = Pointer->leftChild；
}

保存一路走过的根节点的理由是：中序遍历的需要，遍历完左子树后，需要借助根节点进入右子树，代码走到这里，指针p为空，此时无非两种情况：

二叉树的左子树，最下边是不是上图两种情况？不管怎样，此时都要出栈，并访问该节点。这个节点就是中序序列的第一个节点。根据我们的思维，代码应该是这样：

Pointer = Stack.top();
Stack.pop();
cout << Pointer->data << " ";

两图情形不同得区别对待：

1.情景一中访问的是一个左孩子，按中序遍历顺序，接下来应访问它的根节点。也就是图中的另一个节点，高兴的是它已被保存在栈中。我们只需这样的代码和上一步一样的代码：

Pointer = Stack.top();
Stack.pop();
cout << Pointer->data << " ";

左孩子和根都访问完了，接着就是右孩子了，接下来只需一句代码：Pointer = Pointer->rightChild；在右子树中，又会新一轮的代码段直到栈空且p空

2.再看情景2，由于没有左孩子，根节点就是中序序列中第一个，然后直接是进入右子树：Pointer = Pointer->rightChild；在右子树中，又会新一轮的代码段直到栈空且p空

Pointer = Stack.top();
Stack.pop();
cout << Pointer->data << " ";
Pointer = Pointer->rightChild;

看到这里我们思考一个问题，这两种情景的代码可以合成一个吗？

答案是可以的，我们回顾一下二叉树，是不是每个结点都可以看成是根节点，由于是叶子节点，Pointer =Pointer->rightChild；Pointer之后肯定为空。为空，还需要执行while循环，遍历它的左子树吗？显然不需要。换句话说，就算情景一的代码变成下面这样，加上Pointer = Pointer->rightChild，由于叶子结点右孩子一定是空，依旧会连续出栈两次，那么这两种情况的代码不就可以进行统一吗？

p = s.top();
s.pop();
cout << p->data;
p = p->rchild;
p = s.top();
s.pop();
cout << p->data;
p = p->rchild;

我们可以对这两种情况的代码进行统一

Pointer = Stack.top();
Stack.pop();
cout << Pointer->data << " ";
Pointer = Pointer->rightChild;

中序遍历非递归形式的完整代码是这样的:

//非递归的中序遍历
void InOrderWithoutRecusion()
{
	stack<BinaryTreeNode<DateType>*> Stack;
	BinaryTreeNode<DateType>* Pointer = root;
	while (!Stack.empty() || Pointer)
	{
		if (Pointer)
		{
			Stack.push(Pointer);
			Pointer = Pointer->leftChild;
		}
		else
		{
			Pointer = Stack.top();
			Stack.pop();
			cout << Pointer->data << " ";
			Pointer = Pointer->rightChild;
		}
	}
	cout << endl;
}

前序遍历（非递归实现）

前序遍历的递归定义：先根节点，后左子树，再右子树。

首先，我们遍历左子树，边遍历边打印，并把根节点存入栈中，以后需借助这些节点进入右子树开启新一轮的循环。

while(pointer)
{
	//访问当前结点并入栈
	cout << pointer->data << " ";
	Stack.push(pointer);
	pointer = pointer->leftChild;//左孩子不空，一直向左
}

接下来就是：出栈，根据栈顶节点进入右子树

while (!Stack.empty())
{
	//出栈，并转向出栈结点的右子树
	pointer = Stack.top();
	Stack.pop();
	pointer = pointer->rightChild;
}

不难写出完整的前序遍历的非递归写法

//非递归的前序遍历
void PreOrderWithoutRecusion()
{
	//初始化一个栈
	stack<BinaryTreeNode<DateType>*> Stack;
	BinaryTreeNode<DateType>* pointer = root;//pointer为遍历指针
	//栈不为空或遍历指针不为空时循环
	while (pointer || !Stack.empty())
	{
		//一路向左
		if (pointer)
		{
			//访问当前结点并入栈
			cout << pointer->data << " ";
			Stack.push(pointer);
			pointer = pointer->leftChild;//左孩子不空，一直向左
		}
		else
		{
			//出栈，并转向出栈结点的右子树
			pointer = Stack.top();
			Stack.pop();
			pointer = pointer->rightChild;
		}
	}
	cout << endl;
}

后序遍历（非递归实现）

后序遍历递归定义：先左子树，后右子树，再根节点。

后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。

故这里我在代码中附加了一个标记（Left和Right）。如果该节点的左子树已被访问过则置标记为left；若右子树被访问过，则置标记为right。显然，只有当节点的标记位是right时，才可访问该节点；否则，必须先进入它的右子树。

小伙伴们可以结合图解以及注释好好理解一下后序遍历的思想和过程

//--------------- 非递归后续遍历的标志位-------------------
enum Tags
{
	Left, Right //Left为左标志位,Right为右标志位
};
//-----------------非递归后续遍历的栈类--------------------
//自定义新的类型，将二叉树结点和标记封装在一起
template <class DateType>
class StackElement
{
public:
	BinaryTreeNode<DateType>* pointer;
	Tags tag;
};
//非递归的后续遍历
void PostOrderWithoutRecusion()
{
	StackElement<DateType> element;
	//生成一个栈
	stack<StackElement<DateType>> Stack;
	BinaryTreeNode<DateType>* pointer;
	pointer = root;
	while (!Stack.empty() || pointer)
	{
		//这个while循环就是一路遍历左子树，
		while (pointer != NULL)
		{
			element.pointer = pointer;
			//该节点的左子树被访问
			element.tag = Left;
			Stack.push(element);
			pointer = pointer->leftChild;
		}
		element = Stack.top();
		Stack.pop();
		//左子树被访问过，则还需要进入右子树
		pointer = element.pointer;
		if (element.tag == Left)
		{
			//更改标记
			element.tag = Right;
			//再次入栈
			Stack.push(element);
			//进入右子树
			pointer = pointer->rightChild;
		}
		else//右子树已经被访问过，则可以访问当前结点
		{
			cout << pointer->data << " ";
			//置空，再次出栈
			pointer = NULL;
		}
	}
	cout << endl;
}

二叉树的节点个数和高度

二叉树的节点个数

此问题可以分解为求左子树节点个数+右子树节点个数+1，然后左子树节点个数又可以继续分，所以这里可以用递归来求解这个问题，下面我们就来实现一下这个接口

//二叉树结点个数
int BinaryTreeSize(BinaryTreeNode<DateType>* root)
{
	return root == NULL ? 0 : BinaryTreeSize(root->leftChild) + BinaryTreeSize(root->rightChild) + 1;
}

二叉树的叶子节点个数

问题可以分解为求左子树叶子节点个数+右子树叶子节点个数，也是一个递归的问题，这里就直接实现了。

//二叉树的叶子结点个数
int BinaryTreeLeafSize(BinaryTreeNode<DateType>* root)
{
	if (root == NULL)
		return 0;
	if (root->leftChild == NULL && root->rightChild == NULL)
		return 1;
	return BinaryTreeLeafSize(root->leftChild) + BinaryTreeLeafSize(root->rightChild);
}

二叉树第k层节点个数

求解第k层节点个数其实就是求解左子树的第k-1层节点个数+右子树的第k-1层节点个数，当k==1时，就可以直接返回1，节点为空就返回0。

//二叉树第K层结点个数
int BinaryTreeLevelKSize(BinaryTreeNode<DateType>* root, int k)
{
	if (k < 0)
		return -1;
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->leftChild, k - 1) + BinaryTreeLevelKSize(root->rightChild, k - 1);
}

二叉树查找值为x的节点

//二叉树查找值为x的结点
BinaryTreeNode<DateType>* BinaryTreeFind(BinaryTreeNode<DateType>* root, DateType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BinaryTreeNode<DateType>* leftRet = BinaryTreeFind(root->leftChild, x);
	if (leftRet)
		return leftRet;
	BinaryTreeNode<DateType>* rightRet = BinaryTreeFind(root->rightChild, x);
	if (rightRet)
		return rightRet;
}

二叉树的销毁

二叉树的销毁我们可以通过层序遍历来把节点逐个释放掉，由于与上面的层序遍历很相似，这里就不过多介绍了，直接上代码

//二叉树的销毁
void BinaryTreeDestory(BinaryTreeNode<DateType>* root)
{
	if (root == NULL)
	{
		return;
	}
	queue<BinaryTreeNode<DateType>*> q;
	q.push(root);
	while (!q.empty())
	{
		BinaryTreeNode<DateType>* front = q.front();
		q.pop();
		if (front->leftChild)
			q.push(front->leftChild);
		if (front->rightChild)
			q.push(front->rightChild);
		delete front;
		front = NULL;
	}
}

完整代码以及测试

#define _CRT_SECURE_NO_WARNINGS
#include<iostream> //引入头文件
#include<string>//C++中的字符串
#include<queue>
#include<stack>
using namespace std; //标准命名空间
//--------------- 非递归后续遍历的标志位-------------------
enum Tags
{
	Left, Right //Left为左标志位,Right为右标志位
};
//-------------------二叉树结点结构体----------------------
template <class DateType>
struct BinaryTreeNode
{
	DateType data;//数据域
	BinaryTreeNode* leftChild;//左树指针
	BinaryTreeNode* rightChild;//右树种子很
};
//-----------------非递归后续遍历的栈类--------------------
template <class DateType>
class StackElement
{
public:
	BinaryTreeNode<DateType>* pointer;
	Tags tag;
};
//----------------------二叉树类---------------------------
template <class DateType>
class BinaryTree
{
public:
	//构造函数
	BinaryTree()
	{
		cout << "请输入根节点: " << endl;
		cout << "输入#代表结点指针指向空" << endl;
		CreatBinaryTree(root);
		if (root != NULL)
		{
			cout << "root = " << root->data << endl;
		}
		else
		{
			cout << "The BinaryTree is empty" << endl;
		}
	}
	//创建二叉树
	void CreatBinaryTree(BinaryTreeNode<DateType>* &root)
	{
		DateType ch;
		cin >> ch;
		if (ch == '#')
		{
			root = NULL;
		}
		else
		{
			root = new BinaryTreeNode<DateType>;
			root->data = ch;
			cout << "调用左孩子" << endl;
			CreatBinaryTree(root->leftChild);
			cout << "调用右孩子" << endl;
			CreatBinaryTree(root->rightChild);
		}
	}
	//递归前序遍历
	void BinaryTreePrevOrder(BinaryTreeNode<DateType>* root)
	{
		// 遍历到NULL就返回
		if (root == NULL)
		{
			return;
		}
		else
		{
			// 先遍历根
			cout << root->data <<" ";
			// 左子树交给BinaryTreePrevOrder这个函数去遍历
			BinaryTreePrevOrder(root->leftChild);
			// 右子树交给BinaryTreePrevOrder这个函数去遍历
			BinaryTreePrevOrder(root->rightChild);
		}
	}
	//递归中序遍历
	void BinaryTreeInOrder(BinaryTreeNode<DateType>* root)
	{
		// 遍历到NULL就返回
		if (root == NULL)
		{
			return;
		}
		else
		{
			// 左子树交给BinaryTreeInOrder这个函数去遍历
			BinaryTreeInOrder(root->leftChild);
			// 遍历根
			cout << root->data<<" ";
			// 右子树交给BinaryTreeInvOrder这个函数去遍历
			BinaryTreeInOrder(root->rightChild);
		}
	}
	//递归后序遍历
	void BinaryTreePostOrder(BinaryTreeNode<DateType>* root)
	{
		if (root == NULL)
		{
			return;
		}
		else
		{
			// 左子树交给BinaryTreePostOrder这个函数去遍历
			BinaryTreePostOrder(root->leftChild);
			// 右子树交给BinaryTreePostOrder这个函数去遍历
			BinaryTreePostOrder(root->rightChild);
			//遍历根
			cout << root->data<<" ";
	    }
	}
	//层序遍历
	void BinaryTreeLevelOrder(BinaryTreeNode<DateType>* root)
	{
		if (root == NULL)
		{
			return;
		}
		queue<BinaryTreeNode<DateType>*> q;
		q.push(root);
		while (!q.empty())
		{
			BinaryTreeNode<DateType>* front = q.front();
			q.pop();
			cout << front->data << " ";
			if (front->leftChild)
				q.push(front->leftChild);
			if (front->rightChild)
				q.push(front->rightChild);
		}
		cout << endl;
		cout << ">>============================================================================<<" << endl;
		cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
	}
	//非递归的前序遍历
	void PreOrderWithoutRecusion()
	{
		//初始化一个栈
		stack<BinaryTreeNode<DateType>*> Stack;
		BinaryTreeNode<DateType>* pointer = root;//pointer为遍历指针
		//栈不为空或遍历指针不为空时循环
		while (pointer || !Stack.empty())
		{
			//一路向左
			if (pointer)
			{
				//访问当前结点并入栈
				cout << pointer->data << " ";
				Stack.push(pointer);
				pointer = pointer->leftChild;//左孩子不空，一直向左
			}
			else
			{
				//出栈，并转向出栈结点的右子树
				pointer = Stack.top();
				Stack.pop();
				pointer = pointer->rightChild;
			}
		}
		cout << endl;
		cout << ">>============================================================================<<" << endl;
		cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
	}
	//非递归的中序遍历
	void InOrderWithoutRecusion()
	{
		stack<BinaryTreeNode<DateType>*> Stack;
		BinaryTreeNode<DateType>* Pointer = root;
		while (!Stack.empty() || Pointer)
		{
			if (Pointer)
			{
				Stack.push(Pointer);
				Pointer = Pointer->leftChild;
			}
			else
			{
				Pointer = Stack.top();
				Stack.pop();
				cout << Pointer->data << " ";
				Pointer = Pointer->rightChild;
			}
		}
		cout << endl;
		cout << ">>============================================================================<<" << endl;
		cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
	}
	//非递归的后续遍历
	void PostOrderWithoutRecusion()
	{
		StackElement<DateType> element;
		stack<StackElement<DateType>> Stack;
		BinaryTreeNode<DateType>* pointer;
		pointer = root;
		while (!Stack.empty() || pointer)
		{
			while (pointer != NULL)
			{
				element.pointer = pointer;
				element.tag = Left;
				Stack.push(element);
				pointer = pointer->leftChild;
			}
			element = Stack.top();
			Stack.pop();
			pointer = element.pointer;
			if (element.tag == Left)
			{
				element.tag = Right;
				Stack.push(element);
				pointer = pointer->rightChild;
			}
			else
			{
				cout << pointer->data << " ";
				pointer = NULL;
			}
		}
		cout << endl;
		cout << ">>============================================================================<<" << endl;
		cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
	}
	//二叉树结点个数
	int BinaryTreeSize(BinaryTreeNode<DateType>* root)
	{
		return root == NULL ? 0 : BinaryTreeSize(root->leftChild) + BinaryTreeSize(root->rightChild) + 1;
	}
	//二叉树的叶子结点个数
	int BinaryTreeLeafSize(BinaryTreeNode<DateType>* root)
	{
		if (root == NULL)
			return 0;
		if (root->leftChild == NULL && root->rightChild == NULL)
			return 1;
		return BinaryTreeLeafSize(root->leftChild) + BinaryTreeLeafSize(root->rightChild);
	}
	//二叉树第K层结点个数
	int BinaryTreeLevelKSize(BinaryTreeNode<DateType>* root, int k)
	{
		if (k < 0)
			return -1;
		if (root == NULL)
			return 0;
		if (k == 1)
			return 1;
		return BinaryTreeLevelKSize(root->leftChild, k - 1) + BinaryTreeLevelKSize(root->rightChild, k - 1);
	}
	//二叉树查找值为x的结点
	BinaryTreeNode<DateType>* BinaryTreeFind(BinaryTreeNode<DateType>* root, DateType x)
	{
		if (root == NULL)
			return NULL;
		if (root->data == x)
			return root;
		BinaryTreeNode<DateType>* leftRet = BinaryTreeFind(root->leftChild, x);
		if (leftRet)
			return leftRet;
		BinaryTreeNode<DateType>* rightRet = BinaryTreeFind(root->rightChild, x);
		if (rightRet)
			return rightRet;
	}
	//二叉树的销毁
	void BinaryTreeDestory(BinaryTreeNode<DateType>* root)
	{
		if (root == NULL)
		{
			return;
		}
		queue<BinaryTreeNode<DateType>*> q;
		q.push(root);
		while (!q.empty())
		{
			BinaryTreeNode<DateType>* front = q.front();
			q.pop();
			if (front->leftChild)
				q.push(front->leftChild);
			if (front->rightChild)
				q.push(front->rightChild);
			delete front;
			front = NULL;
		}
	}
	void print()
	{
		cout << ">>============================================================================<<" << endl;
		cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
		while (1)
		{
			cout << "请选择二叉树遍历方式" << endl;
			cout << "1:递归前序遍历" << endl;
			cout << "2:递归中序遍历" << endl;
			cout << "3:递归后续遍历" << endl;
			cout << "4:层序遍历" << endl;
			cout << "5:非递归前续遍历" << endl;
			cout << "6:非递归中续遍历" << endl;
			cout << "7:非递归后续遍历" << endl;
			cout << "8:二叉树结点个数" << endl;
			cout << "9:二叉树叶子结点个数" << endl;
			cout << "10:二叉树第K层结点个数" << endl;
			cout << "11:二叉树的销毁" << endl;
			int n;
			cin >> n;
			switch (n)
			{
			case 1:
				cout << "递归前序遍历:";
				BinaryTreePrevOrder(root);
				cout << endl;
				cout << ">>============================================================================<<"<<endl;
				cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
				break;
			case 2:
				cout << "递归中序遍历:";
				BinaryTreeInOrder(root);
				cout << endl;
				cout << ">>============================================================================<<" << endl;
				cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
				break;
			case 3:
				cout << "递归后序遍历:";
				BinaryTreePostOrder(root);
				cout << endl;
				cout << ">>============================================================================<<" << endl;
				cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
				break;
			case 4:
				cout << "层序遍历:";
				BinaryTreeLevelOrder(root);
				break;
			case 5:
				cout << "非递归前序遍历:";
				PreOrderWithoutRecusion();
				break;
			case 6:
				cout << "非递归中续遍历:";
				InOrderWithoutRecusion();
				break;
			case 7:
				cout << "非递归后续遍历:";
				PostOrderWithoutRecusion();
				break;
			case 8:
				cout << "二叉树结点个数:" ;
				cout << BinaryTreeSize(root) << endl;
				cout << ">>============================================================================<<" << endl;
				cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
				break;
			case 9:
				cout << "二叉树叶子结点个数:";
				cout << BinaryTreeLeafSize(root) << endl;
				cout << ">>============================================================================<<" << endl;
				cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
				break;
			case 10:
			{
				int b = 0;
				cout << "请输入你要查找的层数k:";
				cin >> b;
				cout << "第k层的节点数为：" << BinaryTreeLevelKSize(root, b) << endl;
				cout << ">>============================================================================<<" << endl;
				cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
				break;
			}
			case 11:
				BinaryTreeDestory(root);
				cout << "销毁成功" << endl;
				cout << ">>============================================================================<<" << endl;
				cout << "/*------------------------请输入你要选择的选项------------------------- */" << endl;
				break;
			default:
				break;
			}
		}
	}
private:
	BinaryTreeNode<DateType>* root;
};
int main()
{
	BinaryTree<char> tree;
	tree.print();
	system("pause");
	return EXIT_SUCCESS;
}