【数据结构周周练】009 二叉树的先序、中序、后序遍历（递归算法实现）

た入场券 2021-06-11 15:13 425阅读 0赞

# 一、前言 #

上一篇周周练博客讲了二叉树的链式创建，通过创建栈来存放结点，方便二叉树的创建过程，同时呢，二叉树的创建过程就是二叉树的遍历过程，如果创建好一个二叉树之后，就无需再通过那么麻烦的算法，可以直接通过递归来实现，算法原理比较简单，实现也很简单。

大家如果学过数据结构，相信大家对二叉树的三种遍历方式都有所了解，分别是：先序遍历，中序遍历以及后序遍历。详细的概念在此就不过多赘述，只教给大家一个记忆的小技巧：**先左后右，根看名称**。这八个字什么意思呢？大家详细看一下三种遍历方式就能看出来，我们日常习惯都是从左往右，所以**不管是哪种遍历方法，都是左子树先于右子树遍历，所以是先左后右**。然后再看访问根节点：**先序遍历，最先访问根节点；中序遍历，根节点在中间；后序遍历，最后访问根节点，访问根节点的顺序与名称相同，所以是根看名称**。

我们在遍历二叉树时会用到这三种遍历方式。

# 二、题目 #

将下图用二叉树存入，并通过三种遍历方式对该树进行遍历。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。要求遍历每个结点时能够查询当前结点的数据、编号以及双亲结点和孩子结点的编号。

![70][]

#  三、代码 #

#include<iostream>
    #include<malloc.h>
    
    using namespace std;
    
    typedef struct BiTNode {
    	int data;
    	int number;
    	int isAsk;
    	struct BiTNode * lChild, * rChild, * parent;
    }BiTNode,*BiTree;
    
    typedef struct LNode{
    	BiTree stackData;
    	struct LNode *next;
    }LNode, *LinkStack;
    
    int Push(LinkStack &S, BiTree &bt) {
    	LinkStack p = (LinkStack)malloc(sizeof(LNode));
    	S->stackData = bt;
    	p->next = S;
    	S = p;
    	return 1;
    }
    
    int Pop(LinkStack &S/*, BiTree &bt*/) {
    	if (!S->next)
    	{
    		cout << "栈已空" << endl;
    		return 0;
    	}
    	LinkStack p = S->next;
    	//bt = p->stackData;
    	S->next = p->next;
    	free(p);
    }
    
    BiTree GetTopTree(LinkStack S) {
    	if (S->next)
    	{
    		return S->next->stackData;
    	}
    	return NULL;
    }
    
    int InitBiTree(BiTree &BT,int e) {
    	BT = (BiTree)malloc(sizeof(BiTNode));
    	if (!BT)
    	{
    		cout << "空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    	BT->data = e;
    	BT->number = 0;
    	BT->isAsk = 0;
    	BT->lChild = NULL;
    	BT->rChild = NULL;
    	BT->parent = NULL;
    	
    }
    
    int CreatBiTree(BiTree &BT) {
    	//创建一个辅助空间栈，用来创建树
    	LinkStack S = (LinkStack)malloc(sizeof(LNode));
    	if (!S)
    	{
    		cout << "栈空间分配失败" << endl;
    		exit(OVERFLOW);
    	}
    
    	BiTree tree = BT;
    	Push(S, tree);
    	BiTree t;
    	//创建剩余结点
    	int e; 
    	int num = 1;
    	int yesOrNo;
    	int nodeNum;
    
    	cout << "请输入该树有多少个结点：";
    	cin >> nodeNum;
    	loop:while (num<nodeNum)
    	{
    		t = (BiTree)malloc(sizeof(BiTNode));
    		t->isAsk = 0;
    		t->lChild = NULL;
    		t->rChild = NULL;
    		cout << "当前结点标号为"<<tree->number<<"，该结点是否有左子树，有请输入1，没有请输入0：";
    		cin >> yesOrNo;
    		tree->isAsk = (tree->isAsk + 1) * 10;
    		if (yesOrNo)
    		{
    			cout << "请输入当前结点 " << tree->number << " 的左孩子的值：";
    			cin >> e;
    			t->data = e;
    			t->number = num;
    			//t->parent = GetTopTree(S);
    			t->parent = tree;
    			tree->lChild = t;
    			tree = t;
    			num++;
    			Push(S, tree);
    			goto loop;
    		}
    
    		loopRC:if (tree->isAsk%10 == 0)
    		{
    			cout << "当前结点标号为" << tree->number << "，该结点是否有右子树，有请输入1，没有请输入0：";
    			cin >> yesOrNo;
    			tree->isAsk++;
    			if (yesOrNo)
    			{
    				cout << "请输入当前结点 " << tree->number << " 的右孩子的值：";
    				cin >> e;
    				t->data = e;
    				t->number = num;
    				//t->parent = GetTopTree(S);
    				t->parent = tree;
    				tree->rChild = t;
    				tree = t;
    				num++;
    				Push(S, tree);
    				goto loop;
    			}
    			else
    			{
    				tree = tree->parent;
    				Pop(S);
    				goto loopRC;
    			}
    		}
    		else
    		{
    			tree = tree->parent;
    			Pop(S);
    			goto loopRC;
    		}
    		
    	}
    
    }
    
    void VisitBiTree(BiTree BT) {
    	cout << "\n**********************************************************\n";
    	cout << "当前结点的编号为：" << BT->number<<", ";
    	cout << "数据为：" << BT->data << ",\n";
    	if (BT->parent)
    		cout << "当前结点有双亲结点，结点编号为：" << BT->parent->number << ",\n";
    	else
    		cout << "当前结点为根节点，无双亲结点\n";
    	if (BT->lChild)
    		cout << "当前结点有左孩子结点，结点编号为：" << BT->lChild->number << ",\n";
    	if (BT->rChild)
    		cout << "当前结点有右孩子结点，结点编号为：" << BT->rChild->number << ",\n";
    	
    }
    
    //先序遍历
    void PreOrderBiTree(BiTree BT) {
    	if (BT)
    	{
    		VisitBiTree(BT);
    		PreOrderBiTree(BT->lChild);
    		PreOrderBiTree(BT->rChild);
    	}
    }
    
    //中序遍历
    void InOrderBiTree(BiTree BT) {
    	if (BT)
    	{
    		InOrderBiTree(BT->lChild);
    		VisitBiTree(BT);
    		InOrderBiTree(BT->rChild);
    	}
    }
    
    //后序遍历
    void PostOrderBiTree(BiTree BT) {
    	if (BT)
    	{
    		PostOrderBiTree(BT->lChild);
    		PostOrderBiTree(BT->rChild);
    		VisitBiTree(BT);
    	}
    }
    
    void main() {
    	BiTree BT;
    	int e;
    	cout << "请输入根结点数据 : ";
    	cin >> e;
    	InitBiTree(BT, e);
    	CreatBiTree(BT);
    	cout << "\n**********************遍历二叉树开始**********************\n" ;
    	cout << "\n**********************先序遍历二叉树**********************\n";
    	PreOrderBiTree(BT);
    	cout << "\n**********************中序遍历二叉树**********************\n";
    	InOrderBiTree(BT);
    	cout << "\n**********************后序遍历二叉树**********************\n";
    	PostOrderBiTree(BT);
    }

# 四、实现效果 #

![70 1][] 图1、二叉树的创建过程

![70 2][] 图2、先序遍历二叉树

![70 3][] 图3、中序遍历二叉树

![70 4][] 图4、后序遍历二叉树

[70]: /images/20210516/8b0e1598c25d40d491c2bdacc87d200e.png
[70 1]: /images/20210516/e49adc89c2c348e8a470b057cdd9f088.png
[70 2]: /images/20210516/93bcaecb55b44920872ed7b94c02ee96.png
[70 3]: /images/20210516/59fdb5263c114ee5874d249b4904693b.png
[70 4]: /images/20210516/aadf34e021f54269ba9d885f08235e50.png