二叉树的深度与广度遍历及前序遍历递归非递归实现

一、深度优先遍历  

深度优先搜索算法（Depth First Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。

当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。

如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

如右图所示的二叉树：

A 是第一个访问的，然后顺序是 B、D，然后是 E。接着再是 C、F、G。

那么，怎么样才能来保证这个访问的顺序呢？

分析一下，在遍历了根结点后，就开始遍历左子树，最后才是右子树。

因此可以借助堆栈的数据结构，由于堆栈是后进先出的顺序，由此可以先将右子树压栈，然后再对左子树压栈，
这样一来，左子树结点就存在了栈顶上，因此某结点的左子树能在它的右子树遍历之前被遍历。

自己写的代码显然不够简便

void Depthinorder(BinaryTreeNode* root)
{
	if (root == NULL)return;
	BinaryTreeNode* node = root;
	stack<BinaryTreeNode*> s;
	while (node!=NULL||!s.empty())
	{
		while (node != NULL)
		{
			cout << node->value << endl;
			s.push(node);
			node = node->left;
		}
		if (!s.empty())
		{     
			node = s.top();
			while (node->right == NULL)
			{
				s.pop();
				if (s.empty())break;
				node = s.top();
			}
			if (s.empty())break;
			node = node->right;
			s.pop();
		}
	}
}

void depthFirstSearch(BinaryTreeNode* root){
	stack<BinaryTreeNode*> nodeStack; 
	nodeStack.push(root);
	BinaryTreeNode *node;
	while (!nodeStack.empty()){
		node = nodeStack.top();
		cout<<node->value;  //遍历根结点
		nodeStack.pop();
		if (node->right){
			nodeStack.push(node->right);  //先将右子树压栈
		}
		if (node->left){
			nodeStack.push(node->left);  //再将左子树压栈
		}
	}
}

如图输出A B C D E F G 

仿照上述很容易写出代码

 广度优先遍历

void G(BinaryTreeNode* root)
{
	if (root == NULL)return;
	queue<BinaryTreeNode*> q;
	q.push(root);
	BinaryTreeNode* node;
	while (!q.empty())
	{
		node = q.front();
		cout << node->value;
		q.pop();
		if (node->left)
			q.push(node->left);
		if (node->right)
			q.push(node->right);
	}
}

  三、前序遍历

递归实现

   前序遍历：ABDECFG

void Preorder(BinaryTreeNode* root)
{
	if (root == NULL)return;
	cout << root->value;
	if (root->left)
		Preorder(root->left);
	if (root->right)
		Preorder(root->right);
}

 非递归实现

void Preprint1(BinaryTreeNode* root)
{
	if (NULL == root)return;
	stack<BinaryTreeNode*> s;
	BinaryTreeNode* node =root;
	s.push(node);
	while (!s.empty())
	{
		node = s.top();
		cout << node->value;
		s.pop();
		if (node->right)s.push(node->right);
		if (node->left)s.push(node->left);
	}
}

非递归

void inorder1(BinaryTreeNode* root)
{
	if (root == NULL)return;
	stack<BinaryTreeNode*> s;
	BinaryTreeNode* node = root;
	while (node!=NULL||!s.empty())
	{
		while (node != NULL)
		{
			s.push(node);
			node = node->left;
		}
		if (!s.empty())
		{
			node = s.top();
			cout << node->value;
			s.pop();
			node = node->right;
		}
	}
}

void inorder(BinaryTreeNode* root)
{
	if (root == NULL)return;
	BinaryTreeNode* node = root;
	if (root->left)inorder(root->left);
	cout <<root->value << endl;
	if (root->right)inorder(root->right);
}

五、后序遍历

非递归

void postorder(BinaryTreenode* root)
{
   if(root==NULL)return;
   stack<BinaryTreeNode*> s;
   BinaryTreeNode* pre=NULL;
   BinaryTreeNode* cur=NULL;
   s.push(root);
   while(!s.empty())
  {
    cur=s.top();
    if((cur->left==NULL&&cur->right==NULL)||(pre!=NULL&&(pre==cur->left||pre==cur->right)))
    {
     cout<<cur->value;
     s.top();
     pre=cur;
    }
    else 
    {
      if(cur->right)
      s.push(cur->right);
     if(cur->left)
     s.push(cur->left)；
    }
   }
}