二叉树的先序、中序、后序、层序递归及非递归遍历

  二叉树是一种树形结构，它每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）。

所谓度是结点拥有的子树数。

 对于二叉树，它具有以下的性质：

1、在二叉树的第i层上至多有2^(i-1)个结点（i>=1）。

2、深度为k的二叉树至多有2^k-1个结点。

3、对任何一棵二叉树，如果它的叶子结点个数为n0，度为2的结点为n2，那么m = n + 1;

  eg.如果设一个二叉树中度为1的结点个数为n1

故总结点数   N = n0 + n1 + n2;   (1)

  二叉树除了根结点外，其余结点都有一个分支，设M为分支总数，则 N = M + 1;由于这些分支是由度为1或2的结点射出的，则M = n1 + 2*n2;

   则有    N = n1 + 2*n2 + 1   (2)

   由（1）（2）得 n0 = n2 + 1;

4、具有n个结点的完全二叉树的深度为∟log 2 n」+1.(其中“∟x」 ”表示不大于x的最大整数)。

5、如果对一棵有n个结点的完全二叉树的结点按层序编号（每一层从左到右，直到∟log 2 n」+1），则对任意一结点i（1=<i<=n）有

  （1）如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点∟i/2」.

  （2）如果2i>n,则结点i无左右孩子（结点i为叶子结点）否则其左孩子是结点2i；

  （3）如果2i+1>n，则结点i无左右孩子；否则其右孩子是结点2i+1；  

#pragma once #include<queue> #include<stack> #include<iostream> using namespace std; template<class T> struct BinaryTreeNode {	BinaryTreeNode<T> *_left;	BinaryTreeNode<T> *_right;	T _data; public:	BinaryTreeNode(const T& x)	:_data(x)	,_right(NULL)	,_left(NULL)	{} }; template<class T> class BinaryTree {	typedef BinaryTreeNode<T> Node; public:	BinaryTree()	:_root(NULL)	{}	BinaryTree<T>(const T* a, size_t size, const T& invalid)	{	size_t index = 0;	_root = _CreatTree(a, size, index, invalid);	}	BinaryTree<T>(const BinaryTree<T>& t)	{	_root=_Copy(t._root);	}	BinaryTree<T>& operator=( BinaryTree<T> t)	{	swap(_root, t._root);	return *this;	}	~BinaryTree()	{	_Clear(_root);	_root=NULL;	}	void PrevOrder()	{	cout << "先序：" << endl;	_PrevOrder(_root);	}	void InOrder()	{	cout << "中序：" << endl;	_InOrder(_root);	}	void PostOrder()	{	cout << "后序：" << endl;	_PostOrder(_root);	}     //层序      	//思想：队列	//1.先判断根节点是否为NULL	//2.如果根节点不为空，节点入队（不是入值）	//3.判断队列是否为空，如果不为空，出队	//4.判断左 右子树节点是否为空，	//5.如果不为空，入队 左右节点，跳至2	void LeveLorder()    //层序	{	cout << "层序：" << endl;	queue<Node*> tmp;	if (_root == NULL)	return;	else	{	tmp.push(_root);	while (!tmp.empty())	{	Node* Front = tmp.front();	cout << Front->_data << " ";	tmp.pop();	if (Front->_left)	{	tmp.push(Front->_left);	}	if (Front->_right)	{	tmp.push(Front->_right);	}	}	}	}	size_t Size()	{	return _Size(_root);	}	size_t Depth()	{	_Depth(_root);	}	size_t LeafSize()	{	return _leafSize(_root);	} protected:	Node* _CreatTree(const T*a, size_t size, size_t& index, const T& invalid)	{	Node* root = NULL;	if (a[index] != invalid&&index < size)	{	root = new Node(a[index]);	root->_left = _CreatTree(a, size, ++index, invalid);//++index 返回index  index++返回临时变量（在此编译不通过）	root->_right = _CreatTree(a, size, ++index, invalid);	}	return root;	}	//先序遍历  递归形式	void _PrevOrder(Node* root)   	{	if (root == NULL)	return;	cout << root->_data << " ";	_PrevOrder(root->_left);	_PrevOrder(root->_right);	}	//先序遍历 非递归  借助栈	//和层序实现差不多，只是一个是借助队，一个是借助栈	void _PrevOrder(Node* root)  	{	stack<Node*> cur;	if (root == NULL)  //1.先判断根结点是否为空	return;	else	{	cur.push(root);   //2,压栈	while (!cur.empty()) // 3.判断栈是否为空，不为空，先压右 再压左子树	{	Node* temp = cur.top();	cout << temp->_data << " ";	cur.pop();	if (temp->_right)	{	cur.push(temp->_right);	}	if (temp->_left)	{	cur.push(temp->_left);	}	}	}	}	 //中序遍历   递归形式	void _InOrder(Node* root)   	{	if (root == NULL)	return;	_InOrder(root->_left);	cout << root->_data << " ";	_InOrder(root->_right);	}	//中序遍历 非递归  借助栈	void _InOrder(Node* root)	{	Node* cur = root;	stack<Node*> tack;	while (cur || !tack.empty())	{	while (cur)	{	tack.push(cur);	cur = cur->_left;	}	if (!tack.empty())	{	Node* Top = tack.top();	tack.pop();	cout << Top->_data <<" ";	cur = Top->_right;	}	}	}	//后序遍历  递归形式	void _PostOrder(Node* root)  	{	if (root == NULL)	return;	_PostOrder(root->_left);	_PostOrder(root->_right);	cout << root->_data << " ";	}	//后序遍历 非递归  借助栈	void _PostOrder(Node* root)	{	Node* prev=NULL;	Node* cur = root;	stack<Node*> tmp;	while (cur || !tmp.empty())	{	while (cur)	{	tmp.push(cur);	cur = cur->_left;	}	Node* Top = tmp.top();	if (Top->_right == NULL||Top->_right==prev)	{	cout << Top->_data << " ";	tmp.pop();	prev = Top;	cur = NULL;	}	else	{	cur = Top->_right;	}	}	}	void _Size(Node* root)	{	if (root == NULL)	return 0;	return _Size(root->_left) + _Size(root->_right) + 1;	}	size_t _Depth(Node* root)	{	if (root == NULL)	return 0;	int leftdepth = _Depth(root->_left);	int rightdepth = _Depth(root->_right);	return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;	}	size_t _leafSize(Node* root)	{	static size_t size = 0;	if (root == NULL)	return 0;	if (root->_left == NULL&&root->_right == NULL)	{	++size;	return size;	}	_leafSize(root->_left);	_leafSize(root->_right);	return size;	}	void _Clear(Node* root)	{	if (root)	{	_Clear(root->_left);	_Clear(root->_right);	delete root;	}	}	Node* _Copy(Node* root)	{	if (root==NULL)	{	return NULL;	}	Node *tem = new Node(root->_data);	tem->_left=_Copy(root->_left);	tem->_right=_Copy(root->_right);	return  tem;	} private:	Node* _root; };