二叉树的递归实现-创新互联

二叉树是一种非常有用的结构，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

 一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。详细定义见百度百科

 二叉树的结构使其在排序算法中非常有用，最有用的当属平衡二叉树，平衡二叉树将会在本人的博客中讨论。

说起二叉树，就不得不讨论一下二叉树的遍历，一般来说，二叉树的遍历方式有4种：

 假设我们的树是这样的：

（一）前序遍历

  首先我们得分析先序遍历的顺序：A,B,D,E,C,F,G。

  树的遍历利用递归来实现会简单一点，我们将遍历一整棵树分解成遍历左子树和右子树的子问题。

	void PrevOrder()//前序遍历
	{
		_PrevOrder(_root);
	}
	void _PrevOrder(BinaryTreeNode* root)
	{
		if (root == NULL)
		{
			return;
		}
		cout << root->_data <<" ";//先输出根节点
		_PrevOrder(root->_left);//在输出左子树
		_PrevOrder(root->_right);//最后右子树
	}

（二）中序遍历

  遍历的顺序：D,B,E,A,F,C,G

	void MidOrder()//中序遍历
	{
		_MidOrder(_root);
	}
	void _MidOrder(BinaryTreeNode* root)
	{
		if (root == NULL)
		{
			return;
		}
		_MidOrder(root->_left);
		cout << root->_data << " ";
		_MidOrder(root->_right);
	}

（三）后序遍历

  遍历顺序：D,E,B,F,G,C,A

	void RearOrder()//后序遍历
	{
		_RearOrder(_root);
	}
	void _RearOrder(BinaryTreeNode* root)
	{
		if (root == NULL)
		{
			return;
		}
		_RearOrder(root->_left);
		_RearOrder(root->_right);
		cout << root->_data << " ";
	}

（四）层序遍历

  遍历顺序：A,B,C,D,E,F,G

  层序遍历的话可以利用队列先进先出的特点，将每一层的节点入队列，只要队列不为空，就出一次队列。

void SequenceOrder()//层序遍历
	{
		queue*> q;
		if (_root)
			q.push(_root);
		while (!q.empty())
		{
			if (q.front()->_left)
			{
				q.push(q.front()->_left);
			}
			if (q.front()->_right)
			{
				q.push(q.front()->_right);
			}
			cout << q.front()->_data<< " ";
			q.pop();
		}
	}

树的遍历是比较简单的，下面我们看一下有点难度的：

（一）求树的叶子节点的个数：

 数的叶子节点总是在最深的一层。，每次当一个子问题的根节点的左右子树都为NULL时，我们就将戒子节点的个数加一，当然，可以把叶子节点定义为一个静态变量，这样，每次加的都是同一个变量上。

也可以不用定义静态的变量，因为静态变量会有线程的安全问题。

        size_t LeafCount()
	{
		return _LeafCount(_root);
	}
	size_t _LeafCount(BinaryTreeNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		if (root->_left==NULL && root->_right ==NULL)
		{
			return 1;
		}

		return (_LeafCount(root->_left)+_LeafCount(root->_right));
	}
	

（二）求树的深度

 求树的深度是一个比较有难度的问题，因为我们要比较不同子树的深度的大小，然后取大的哪一个，但是在一个递归程序中很难保证一个变量不会改变。在这里我们只要比较每个子问题中的左右字数的深度，每次返回使深度大值加一，最后的值就是树的深度。

	size_t Deepth()
	{
		return _Deepth(_root);
	}
	size_t _Deepth(BinaryTreeNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		size_t leftDeep = _Deepth(root->_left)+1;
		size_t rightDeep = _Deepth(root->_right)+1;
		return leftDeep > rightDeep ? leftDeep: rightDeep;
	}

（三）求树的节点的个数

  这个问题是比较容易的，我们可以用任意一种遍历方式遍历这棵树，每遍历到一个节点，个数就加以。

	size_t Size()
	{
		return _Size(_root);
	}
	size_t _Size(BinaryTreeNode* root)
	{
		if (root == NULL)
		{
			return 0;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;
	}

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。