算法练习题45---蓝桥杯树的遍历

• 前言
• 一、题目描述
• 二、思路
• 三、具体代码

树的存储和遍历一直是数据结构和算法领域内非常重要的一个知识点。这次的蓝桥杯B组C++省赛没有考察树的相关知识，因此准备国赛的时候不能掉以轻心，个人感觉在国赛里很可能会对树的知识进行考察。

给定一个棵二叉树，请输出树的前序、中序和后序遍历序列。

题目描述:

给定一个棵二叉树，请输出树的前序遍历序列。

输入描述:

输入的第一行包含1个整数 n 表示共计 n 个节点和 n-1 条边
然后输入 n 个字母作为其节点的数据。
接下来的 n-1 行，每行两个数字 a b 代表 a 和 b 之间有一条边，在前的为子树的根节点。
然后输入一个数字 r 代表 根节点的序号。
约定 a b n 和 r 均小于 100 ，右子树存在左子树一定存在，即仅有一个子树时一定为左子树。

输出描述:

一行字母表示访问顺序，每个字母之间采用空格隔开。

输入输出样例:

输入示例：

9
A B C D E F G H I
1 2
1 3
2 4
2 6
6 5
3 7
3 9
7 8
1

输出示例：
前序遍历：A B D F E C G H I
中序遍历：D B E F A H G C I
后序遍历：D E F B H G I C A

运行限制:

最大运行时间：1s
最大运行内存: 256M

例题参考树：

树的前中后序遍历主要用到的是递归思想，大致的思路就是逐层遍历从根节点的左孩子开始，然后再把左孩子当做新的根节点，继续向左递归，直到某一节点没有左孩子为止，这个时候回溯，再去寻找右孩子，然后把右孩子当做新的根节点，再去向下递归，回溯。

前序，中序，后序遍历唯一不同的地方就在于，访问节点的时刻不同，也就是题目中输出该节点的名称这一过程。

树的数据结构是重中之重，其数据结构的版本有很多，但是共同的核心就是节点指针和节点名称，节点指针用来存放子节点的地址，而节点名称用来标记该节点的信息。

#include 
using namespace std;

struct tree_node
{
	int child;
	tree_node *next;
	tree_node()
	{
		child=1;
		next=nullptr;  //空指针关键字
	}
};

struct head_node
{
	string data;
	tree_node *firstchild;
	head_node()
	{
		data="";
		firstchild=NULL;
	}
};

head_node Nodes[100];  //声明结点数组

void add(int a,int b)
{
	tree_node* tempTreeNode=new tree_node(); //创建一个新的节点
	tempTreeNode->child=b;  //孩子先设为b
	tree_node* tempPtr=Nodes[a].firstchild; //创建一个临时结点指针，指向以a为根的子树的左子树
	if(tempPtr!=NULL)  //说明有左子树
	{
		Nodes[a].firstchild->next=tempTreeNode; //a已经存在左子树，新的节点就是a的右子树
	}
	else  //a没有左子树,因此新引入的b为左子树
	{
		Nodes[a].firstchild=tempTreeNode;
	}
}
int n;
int root;

void preorder(int n)  //前序遍历结果
{
	cout<
		preorder(tempPtr->child);  //继续递归，寻找该结点的左孩子
		tempPtr=tempPtr->next;  //寻找完毕，寻找该结点的右孩子
		if(tempPtr!=NULL)
		{
			preorder(tempPtr->child);
		}
	}
}


void inorder(int n)  //中序遍历结果
{
	tree_node* tempPtr=Nodes[n].firstchild;
	if(tempPtr!=NULL)
	{
		inorder(tempPtr->child);  //继续递归，寻找该结点的左孩子
		cout<next;  //寻找该结点的右孩子
		if(tempPtr!=NULL)
		{
			inorder(tempPtr->child);
		}
	}
	else cout<
	tree_node* tempPtr=Nodes[n].firstchild;
	if(tempPtr!=NULL)
	{
		posorder(tempPtr->child);  //继续递归，寻找该结点的左孩子
		tempPtr=tempPtr->next;  //寻找完毕，寻找该结点的右孩子
		if(tempPtr!=NULL)
		{
			posorder(tempPtr->child);
		}
	}
	cout<
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>> Nodes[i].data;
    }
    for(int i=1; i
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cin>>root;
    cout<<"前序遍历：";
    preorder(root);
    cout< 
参考：蓝桥杯国赛 14 天夺奖冲刺营 - 树的存储与遍历 - 蓝桥云课 (lanqiao.cn)