已知先序中序构树

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 50;
int pre[N], in[N], post[N];        //存放先序，中序，后序的数组 
int n;//树中元素个数
struct node {
	int data;//数据
	node* lchild;//左子数指针
	node* rchild;//右子树指针
};
node* create(int prel, int prer, int inl, int inr)  //根据先序和中序建立树 
{           //4个参数  先序的左右边界，中序的左右边界  
	if (prel>prer)                              //已经遍历完了，返回 
	{
		return NULL;//返回空指针
	}
	node* root = new node;                      //建立一个根结点，用来存放当前的树结点
	root->data = pre[prel];                     // 因为是已知先序，所以当前树的值，一定等于先序的最左边的点 
	int k;                                    //记录当前根节点在中序的下标
	for (k = inl; k <= inr; k++)
	{
		if (in[k] == pre[prel])                 //找到位置，跳出，k不再++
			break;
	}
	int numleft = k - inl;                        //当前树的左子树的数量
	root->lchild = create(prel + 1, prel + numleft, inl, k - 1);     //将这部分存入左子树 
	root->rchild = create(prel + numleft + 1, prer, k + 1, inr);     // 将这部分存入右子树
	return root;                //返回根结点的地址，将整个树的结点连接起来
}

已知后序中序构树

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
const int N = 50;
int pre[N], in[N], post[N];//in中序，post后序
int n;//结点个数
struct Node {
	int data;//数据
	Node* lchild;//左子树指针
	Node* rchild;//右子树指针
};
Node* create(int postl, int postr, int inl, int inr)//4个参数  后序的左右边界，中序的左右边界  
{
	if (postl>postr) //已经遍历完了，返回 
	{
		return NULL;
	}
	Node* root = new Node; //建立一个根结点，用来存放当前的树结点
	root->data = post[postr];  // 因为是已知后序，所以当前树的值，一定等于先序的最右边
	int k;
	for (k = inl; k<=inr; k++)
	{
		if (in[k] == post[postr]) //找到位置，跳出，k不再++  
			break;
	}
	int numleft = k - inl;//当前树的左子树的数量  
	root->lchild = create(postl, postl + numleft - 1, inl, k - 1);//将这部分存入左子树   
	root->rchild = create(postl + numleft, postr - 1, k + 1, inr);// 将这部分存入右子树  
	return root; //返回根结点的地址，将整个树的结点连接起来 
}

先序中序后序输出

void printfpost(node* root)               
{
	if (root == NULL)return;//遇到空指针返回
 
	printfpost(root->lchild);
	printfpost(root->rchild);
 
	printf("%d", root->data);//这三行放后面为后序，前面先序，中间中序输出
	num++;
	if (num<n) printf(" ");
}

层次遍历输出

void bfs(Node* root)        //层次遍历输出 
{
	queue<Node*> q;
	int num = 0;
	q.push(root);//根结点入队
	while (!q.empty())
	{
		Node* now = q.front();
		q.pop();
		printf("%d", now->data);//输出此结点数据
		num++;
		if (num<n) printf(" ");
		if (now->lchild != NULL) q.push(now->lchild);//左右结点依次入队
		if (now->rchild != NULL) q.push(now->rchild);
	}
	putchar(10);//换行
}

树高度的求法

int gethight(node *root) {
	if (!root)return 0;
	return max(gethight(root->lchild) + 1, gethight(root->rchild) + 1);
}

主函数

int main()
{
	scanf("%d", &n);
	for (int i = 0; i<n; i++)//输入先序排列
	{
		scanf("%d", &pre[i]);//后序scanf("%d", &post[i]);
	}
	for (int i = 0; i<n; i++)//输入中序排列
	{
		scanf("%d", &in[i]);
	}
	node* root = create(0, n - 1, 0, n - 1);//构树，4个参数  先后序的左右边界，中序的左右边界  
	调用输出函数；
}