一、前言

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

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

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

二、题目

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

三、代码

#include
   
    #include
    
     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
     
      isAsk = 0;		t->lChild = NULL;		t->rChild = NULL;		cout << "当前结点标号为"<
      
       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);}

四、实现效果

你可能感兴趣的文章