将按顺序表存储的数组转化为链式二叉树并且按照先序、中序、后序排列分别输出

提示：侵权请联系作者删除

---

前言

提示：这里可以添加本文要记录的大概内容：

在学习二叉树的时候，将按顺序表存储的数组转化为链式二叉树并且按照先序、中序、后序排列分别输出的学习重点知识，是我们要始终注意进行练习的

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、实现按顺序表存储的数组转化为链式二叉树

首先我们在这里的数组是按照二叉树的层序排列的方式进行的，层序排列是什么意思呢？

例如在这里先给定一个数组，里面数字的排列是按照二叉树的层序排列进行的，那么按这种方式存放的数组，在转化为二叉树的时候，就可以转化为

 那么这个时候一个树的根结点和左子节点、右字子节点有什么关系呢？

他们的关系如下：

 

 所以在这里就可以用递归的方式：

struct BiNode {
	char data;
	BiNode* lchild, * rchild;
};       //定义二叉树
BiNode* BiTree;
BiNode* CreateBiTree(char* c, int i, int n)   
{
	if ((i > n) || i == '0')
		return NULL;
	BiNode* T;
	T = new BiNode;
	T->data = c[i];
	T->lchild = CreateBiTree(c, 2 * i, n);
	T->rchild = CreateBiTree(c, 2 * i+1, n);
	return T;
}
//在这个函数当中我们是先从数组的第一个元素开始遍历，然后不断使用递归

二、先序排列

按照上面的思想，那么先序排列就是可以使用递归方法，先返回根结点，再返回左子节点，最后再返回右节点，代码如下：

//（先根遍历）  根 左子树 右子树
void PrevOrderTraverse(BiNode* T)
{
	if (T!=NULL) {
		if (T->data!= '0') {
			cout << T->data;
		}
		PrevOrderTraverse(T->lchild);
		PrevOrderTraverse(T->rchild);
	}
 
}

三.中序排列

按照上面的思想，那么先序排列就是可以使用递归方法，先返回左子结点，再返回根结点，最后再返回右节点，代码如下：

//中序遍历
void InOrderTraverse(BiNode* T)
{
	if (T!=NULL) {
		InOrderTraverse(T->lchild);
		if (T->data!= '0') {
			cout << T->data;
		}
		InOrderTraverse(T->rchild);
	}	
}

---

四、后序排列

按照上面的思想，那么先序排列就是可以使用递归方法，先返回左子结点，再返回右子结点，最后再返回根节点，代码如下：

//后序遍历
void PostOrderTraverse(BiNode* T)
{
	if (T!=NULL) {
		PostOrderTraverse(T->lchild);
		PostOrderTraverse(T->rchild);
		if (T->data!= '0') {
			cout << T->data;
		}
	}
}

五、最终代码

从数组的输入创建，到输出二叉树的先序排列、中序排列、后序排列

#include<iostream>
using namespace std;
struct BiNode {
	char data;
	BiNode* lchild, * rchild;
};
BiNode* BiTree;
BiNode* CreateBiTree(char* c, int i, int n)
{
	if ((i > n) || i == '0')
		return NULL;
	BiNode* T;
	T = new BiNode;
	T->data = c[i];
	T->lchild = CreateBiTree(c, 2 * i, n);
	T->rchild = CreateBiTree(c, 2 * i+1, n);
	return T;
 
}
 
//（先根遍历）  根 左子树 右子树
void PrevOrderTraverse(BiNode* T)
{
	if (T!=NULL) {
		cout << T->data;
		PrevOrderTraverse(T->lchild);
		PrevOrderTraverse(T->rchild);
	}
 
}
 
//中序遍历
void InOrderTraverse(BiNode* T)
{
	if (T!=NULL) {
		PrevOrderTraverse(T->lchild);
		cout << T->data;
		PrevOrderTraverse(T->rchild);
	}	
}
 
 
//后序遍历
void PostOrderTraverse(BiNode* T)
{
	if (T!=NULL) {
		PrevOrderTraverse(T->lchild);
		PrevOrderTraverse(T->rchild);
		cout << T->data;
	}
}
int main() {
	int i, SampleNum;
	char c[100];
	cin >> SampleNum;  //在这里指的是输入二叉树结点个数
	for (i = 1; i <=SampleNum; i++) {
		cin >> c[i];
	}
	BiTree = CreateBiTree(c, 1, SampleNum);
	PrevOrderTraverse(BiTree);
	cout << endl;
	InOrderTraverse(BiTree);
	cout << endl;
	PostOrderTraverse(BiTree);
	cout << endl;
	return 0;
}