您的位置: 首页  >  文章  >  非递归实现二叉树遍历（附c++完整代码）

非递归实现二叉树遍历（附c++完整代码）

分类: 文章 • 2024-11-14 13:40:52

先序、中序和后序遍历过程：遍历过程中经过结点的路线一样，只是访问各结点的时机不同。
非递归实现二叉树遍历（附c++完整代码）

从图中可以看到，前序遍历在第一次遇见元素时输出，中序遍历在第二次遇见元素时输出，后序遍历在第三次遇见元素时输出。

非递归算法实现的基本思路：使用堆栈

一、前序遍历

1、递归实现

遍历过程为：

  1. 访问根结点；
  2. 先序遍历其左子树；
  3. 先序遍历其右子树。
void ProOrderTraverse(BiTree tree)
{
	if (tree == NULL)
		return;
	cout << tree->data << " ";
	ProOrderTraverse(tree->lchild);
	ProOrderTraverse(tree->rchild);
}

2、非递归实现

void ProOrder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	BiTree p = pRoot;
	stack<BiTree>s;

	while (p != NULL || !s.empty())
	{
		while (p != NULL)
		{
			s.push(p);
			cout << p->data << " ";
			p = p->lchild;
		}
		if (!s.empty())
		{
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
}

二、中序遍历

1、递归实现

遍历过程为：

  1. 中序遍历其左子树；
  2. 访问根结点；
  3. 中序遍历其右子树。
void midOrderTraverse(BiTree tree)
{
	if (tree == NULL)
		return;
	midOrderTraverse(tree->lchild);
	cout << tree->data << " ";
	midOrderTraverse(tree->rchild);
}

2、非递归实现

  1. 遇到一个结点，就把它压栈，并去遍历它的左子树；
  2. 当左子树遍历结束后，从栈顶弹出这个结点并访问它；
  3. 然后按其右指针再去中序遍历该结点的右子树。
void midOrder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	BiTree p = pRoot;
	stack<BiTree>s;
	while (p != NULL || !s.empty())
	{
		while (p!=NULL)
		{
			s.push(p);
			p = p->lchild;
		}
		if (!s.empty())
		{
			p = s.top();
			cout << p->data << " ";		//第二次遇见的时候输出
			s.pop();
			p = p->rchild;
		}
	}
}

三、后序遍历

1、递归实现

遍历过程为：

  1. 后序遍历其左子树；
  2. 后序遍历其右子树；
  3. 访问根结点。
void postOrderTraverse(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	postOrderTraverse(pRoot->lchild);
	postOrderTraverse(pRoot->rchild);
	cout << pRoot->data<<" ";
}

2、非递归实现

第一种思路：对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问， 因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理，当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问。这样就 保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。

typedef struct Node
{
	BiTree btnode;
	bool isfirst;
}Node,*node;

void postOrder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	stack<node>s;
	BiTree p = pRoot;
	node tmp;
	while (p!=NULL || !s.empty())
	{
		while (p != NULL)			//沿左子树一直往下搜索，直至出现没有左子树的结点
		{
			node btn = (node)malloc(sizeof(Node));
			btn->btnode = p;
			btn->isfirst = true;
			s.push(btn);
			p = p->lchild;
		}
		if (!s.empty())
		{
			tmp = s.top();
			s.pop();
			if (tmp->isfirst == true)	//第一次出现在栈顶
			{
				tmp->isfirst = false;
				s.push(tmp);
				p = tmp->btnode->rchild;
			}
			else				//第二次出现在栈顶
			{
				cout << tmp->btnode->data<<" ";
				p = NULL;
			}
		}
	}
}

第二种思路：要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。

void postorder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	stack<BiTree>s;
	BiTree cur = pRoot, pre = NULL;
	s.push(pRoot);
	while (!s.empty())
	{
		cur = s.top();
		if ((cur->lchild == NULL&&cur->rchild == NULL) ||
			((pre == cur->lchild || pre == cur->rchild) && pre != NULL))
		{
			cout << cur->data << " ";
			s.pop();
			pre = cur;
		}
		else
		{
			if (cur->rchild != NULL)
				s.push(cur->rchild);
			if (cur->lchild != NULL)
				s.push(cur->lchild);
		}
	}
}

四、c++完整代码

#include<iostream>
#include<stdlib.h>
#include<stack>
using namespace std;
#define len 15						//定义一个长度

typedef int ElemType;

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef struct Node
{
	BiTree btnode;
	bool isfirst;
}Node,*node;

//向下遍历，找到节点s应该插入的位置，节点有重复时，忽略这个节点
void SearchTreeNode(BiTree &root, BiTree &s)	//注意：使用引用传递
{
	if (root == NULL)
		return;
	if (s->data > root->data)
	{
		if (root->rchild == NULL)
		{
			root->rchild = s;
			return;
		}
		SearchTreeNode(root->rchild, s);//s值大于根节点值，未到达叶子节点，继续向右孩子遍历
	}

	else if (s->data < root->data)
	{
		if (root->lchild == NULL)
		{
			root->lchild = s;
			return;
		}
		SearchTreeNode(root->lchild, s);//s值小于根节点值，未到达叶子节点，继续向左孩子遍历
	}
}

//插入一个节点，树为空，插入节点即为根节点，否则找合适的位置插入
void InsertNode(BiTree &tree, BiTree &s)		//注意：使用引用传递
{
	if (tree == NULL)
		tree = s;
	else
		SearchTreeNode(tree, s);
}

//二叉排序树创建，每次增加一个结点，插到现有的二叉树上去
void CreateOrderBinaryTree(BiTree &tree, int *a)
{
	for (int i = 0; i < len; i++)
	{
		BiTree s = (BiTree)malloc(sizeof(BiTNode));
		s->data = a[i];
		s->lchild = NULL;
		s->rchild = NULL;
		InsertNode(tree, s);
	}
}
//前序遍历
void ProOrderTraverse(BiTree tree)
{
	if (tree == NULL)
		return;
	cout << tree->data << " ";
	ProOrderTraverse(tree->lchild);
	ProOrderTraverse(tree->rchild);
}
//非递归前序遍历
void ProOrder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	BiTree p = pRoot;
	stack<BiTree>s;

	while (p != NULL || !s.empty())
	{
		while (p != NULL)
		{
			s.push(p);
			cout << p->data << " ";		//第一次遇见的时候输出
			p = p->lchild;
		}
		if (!s.empty())
		{
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
}

//中序遍历
void midOrderTraverse(BiTree tree)
{
	if (tree == NULL)
		return;
	midOrderTraverse(tree->lchild);
	cout << tree->data << " ";
	midOrderTraverse(tree->rchild);
}

//非递归中序遍历
void midOrder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	BiTree p = pRoot;
	stack<BiTree>s;
	while (p != NULL || !s.empty())
	{
		while (p!=NULL)
		{
			s.push(p);
			p = p->lchild;
		}
		if (!s.empty())
		{
			p = s.top();
			cout << p->data << " ";		//第二次遇见的时候输出
			s.pop();
			p = p->rchild;
		}
	}
}

//后序遍历
void postOrderTraverse(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	postOrderTraverse(pRoot->lchild);
	postOrderTraverse(pRoot->rchild);
	cout << pRoot->data<<" ";
}

//非递归实现后续遍历
void postOrder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	stack<node>s;
	BiTree p = pRoot;
	node tmp;
	while (p!=NULL || !s.empty())
	{
		while (p != NULL)		//沿左子树一直往下搜索，直至出现没有左子树的结点
		{
			node btn = (node)malloc(sizeof(Node));
			btn->btnode = p;
			btn->isfirst = true;
			s.push(btn);
			p = p->lchild;
		}
		if (!s.empty())
		{
			tmp = s.top();
			s.pop();
			if (tmp->isfirst == true)			//第一次出现在栈顶
			{
				tmp->isfirst = false;
				s.push(tmp);
				p = tmp->btnode->rchild;
			}
			else						//第二次出现在栈顶
			{
				cout << tmp->btnode->data<<" ";
				p = NULL;
			}
		}
	}
}

//非递归实现后续遍历
void postorder(BiTree pRoot)
{
	if (pRoot == NULL)
		return;
	stack<BiTree>s;
	BiTree cur = pRoot, pre = NULL;
	s.push(pRoot);
	while (!s.empty())
	{
		cur = s.top();
		if ((cur->lchild == NULL&&cur->rchild == NULL) ||
			((pre == cur->lchild || pre == cur->rchild) && pre != NULL))
		{
			cout << cur->data << " ";
			s.pop();
			pre = cur;
		}
		else
		{
			if (cur->rchild != NULL)
				s.push(cur->rchild);
			if (cur->lchild != NULL)
				s.push(cur->lchild);
		}
	}
}

int main()
{
	int a[len] = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93, 23, 27, 45, 21, 12 };

	BiTree tree = NULL;
	//创建一个二叉树，并中序遍历
	CreateOrderBinaryTree(tree, a);

	cout << "前序遍历" << endl;
	ProOrderTraverse(tree);
	cout << endl;
	ProOrder(tree);
	cout << endl<<endl;

	cout << "中序遍历" << endl;
	midOrderTraverse(tree);
	cout << endl;
	midOrder(tree);
	cout << endl<<endl;

	cout << "后序遍历" << endl;
	postOrderTraverse(tree);
	cout << endl;
	postOrder(tree);
	cout << endl;
	postorder(tree);
	cout << endl<<endl;

	return 0;
}

相关推荐