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

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

文章目录

前言

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

二、先序排列

三.中序排列

四、后序排列

五、最终代码


前言

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

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


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

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

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

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

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

他们的关系如下:

 

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

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;
}

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式