一、递归遍历

二叉树结构：

1
2
3
4
5
6
7
8
typedef char Element;
//二叉链式树节点
typedef struct BtNode
{
	Element data;				//数据域
	struct BtNode* leftchild;	//左孩子
	struct BtNode* rightchild;	//右孩子
}BtNode, *BinaryTree;

（1）先序

1
2
3
4
5
6
7
8
//前序遍历二叉树
void PreOrder(BinaryTree root)
{
	if (root == NULL) return;
	cout << root->data << " ";
	PreOrder(root->leftchild);
	PreOrder(root->rightchild);
}

（2）中序

1
2
3
4
5
6
7
8
//中序遍历二叉树
void MidOrder(BinaryTree root)
{
	if (root == NULL) return;
	MidOrder(root->leftchild);
	cout << root->data << " ";
	MidOrder(root->rightchild);
}

（3）后序

1
2
3
4
5
6
7
8
//后序遍历二叉树
void LastOrder(BinaryTree root)
{
	if (root == NULL) return;
	LastOrder(root->leftchild);
	LastOrder(root->rightchild);
	cout << root->data << " ";
}

二、非递归遍历

二叉树结构：

1
2
3
4
5
6
7
8
typedef char Element;
//二叉链式树节点
typedef struct BtNode
{
	Element data;				//数据域
	struct BtNode* leftchild;	//左孩子
	struct BtNode* rightchild;	//右孩子
}BtNode, *BinaryTree;

（1）先序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//非递归先序遍历
void Pre(BtNode* p)
{
	if (NULL == p) return;
	stack<BtNode*> st;
	st.push(p);
	while (!st.empty())
	{
		p = st.top();
		st.pop();
		cout << p->data << " ";
		//先入后出
		if (p->rightchild != NULL)
		{
			st.push(p->rightchild);
		}
		if (p->leftchild != NULL)
		{
			st.push(p->leftchild);
		}

	}
	cout << endl;
}

（2）中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//中序非递归遍历
void Mid(BtNode* p)
{
	if (NULL == p)
		return;

	stack<BtNode*> st;
	while (p != NULL || !st.empty())
	{
		while (p != NULL)
		{
			st.push(p);
			p = p->leftchild;
		}
		p = st.top();
		st.pop();
		cout << p->data << " ";
		p = p->rightchild;
	}
}

（3）后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//后序非递归遍历
void Last(BtNode* p)
{
	if (NULL == p)
		return;
	stack<BtNode*> st;
	BtNode* tag = NULL;
	while (p != NULL || !st.empty())
	{
		while (p != NULL)
		{
			st.push(p);
			p = p->leftchild;
		}
		p = st.top();
		st.pop();
		if (p->rightchild == NULL || p->rightchild == tag)
		{
			cout << p->data << " ";
			tag = p;
			p = NULL;
		}
		else
		{
			st.push(p);
			p = p->rightchild;
		}
	}
}

三、其他结构遍历

二叉树结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef char Element;
//二叉链式树节点
typedef struct BtNode
{
	Element data;				//数据域
	struct BtNode* leftchild;	//左孩子
	struct BtNode* rightchild;	//右孩子
}BtNode, *BinaryTree;


struct JieBtNode
{
	BtNode* pnode;	//节点
	int count;		//记录出栈次数：1代表左 2代表中 3代表右
public:
	JieBtNode(BtNode* p) :pnode(p), count(0)
	{}
};

（1）非递归中序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//非递归中序遍历
void NewMid(BtNode* p)
{
	if (NULL == p) return;
	stack<JieBtNode> st;
	st.push(JieBtNode(p));

	while (!st.empty())
	{
		JieBtNode jienode = st.top();
		st.pop();
		if (++jienode.count == 2)
		{
			cout << jienode.pnode->data << " ";
			if (jienode.pnode->rightchild != NULL)
			{
				st.push(JieBtNode(jienode.pnode->rightchild));
			}
		}
		else
		{
			st.push(jienode);
			if (jienode.count == 1 && jienode.pnode->leftchild != NULL)
			{
				st.push(JieBtNode(jienode.pnode->leftchild));
			}
		}
	}
	cout << endl;
}

（2）非递归后序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//非递归后序遍历
void NewLast(BtNode* p)
{
	if (NULL == p) return;
	stack<JieBtNode> st;
	st.push(JieBtNode(p));

	while (!st.empty())
	{
		JieBtNode jienode = st.top();
		st.pop();
		if (++jienode.count == 3)
		{
			cout << jienode.pnode->data << " ";
		}
		else
		{
			st.push(jienode);
			if (jienode.count == 1 && jienode.pnode->leftchild != NULL)
			{
				st.push(JieBtNode(jienode.pnode->leftchild));
			}
			else if(jienode.count == 2 && jienode.pnode->rightchild != NULL)
			{
				st.push(JieBtNode(jienode.pnode->rightchild));
			}
		}
	}
	cout << endl;
}