根据二叉树遍历的先序序列和中序序列，建立二叉树的二叉链表

绝地灬酷狼 2021-11-05 00:54 289阅读 0赞

题目描述：设一棵二叉树各结点的值各不相同，其先序遍历序列和中序遍历序列分别存于两个一维数组A\[1...n\]和B\[1..n\]中，试编写算法建立该二叉树的二叉链表。

算法思想：根据二叉树的先序遍历序列和中序遍历序列可以创建一棵唯一的二叉树。先序遍历的第一个结点，是二叉树的根节点，在中序遍历找到根结点后，可以知道根节点的左右子树的结点和左右子树的结点数(用llen和rlen表示），然后递归分别建立其左右子树，依次扫描二叉树先序序列，然后在中序序列中找到该结点从而确定该结点下的左右子树，直到左右子树的结点数为0时(llen==0和rlen==0)，二叉树建立完毕。

算法代码：

typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode,*BiTree;
    BiTree create_BiTree(ElemType A[], ElemType B[],int la,int ha,int lb,int hb){
    	//A[]存放前序序列，B[]存放中序序列。la和ha分别表示前序序列的起始位置和最终位置，lb和hb分别表示中序序列的起始位置和最终位置
    	int llen, rlen;  //中序序列中左右子树的长度
    	int s=0;
    	BiTree T = (BiTree)malloc(sizeof(BiTNode));
    	T->data = A[la];
    	T->lchild = T->rchild = NULL;
    	while (A[la] != B[s]) //s表示跟结点在中序序列中的位置
    		s++; 
    	llen = s - lb;
    	rlen = hb - s;
    	if (llen != 0){
    		T->lchild = create_BiTree(A, B, la + 1,la+llen, lb ,lb + llen - 1);
    	}else{
    		T->lchild = NULL; //左子树长度为零时，左孩子为空
    	}
    
    	if (rlen != 0){
    		T->rchild = create_BiTree(A, B, ha - rlen+1, ha, hb - rlen+1, hb);
    	}else{
    		T->rchild = NULL;//右子树长度为零时，有孩子为空
    	}
    	return T;
    }

完整代码：

#include<stdio.h>
    #include<stdlib.h>
    #include<iostream>
    using namespace std;
    typedef char ElemType;
    typedef struct BiTNode{
    	ElemType data;
    	struct BiTNode *lchild, *rchild;
    }BiTNode,*BiTree;
    BiTree create_BiTree(ElemType A[], ElemType B[],int la,int ha,int lb,int hb){
    	//A[]存放前序序列，B[]存放中序序列。la和ha分别表示前序序列的起始位置和最终位置，lb和hb分别表示中序序列的起始位置和最终位置
    	int llen, rlen;  //中序序列中左右子树的长度
    	int s=0;
    	BiTree T = (BiTree)malloc(sizeof(BiTNode));
    	T->data = A[la];
    	T->lchild = T->rchild = NULL;
    	while (A[la] != B[s]) //s表示跟结点在中序序列中的位置
    		s++; 
    	llen = s - lb;
    	rlen = hb - s;
    	if (llen != 0){
    		T->lchild = create_BiTree(A, B, la + 1,la+llen, lb ,lb + llen - 1);
    	}else{
    		T->lchild = NULL; //左子树长度为零时，左孩子为空
    	}
    
    	if (rlen != 0){
    		T->rchild = create_BiTree(A, B, ha - rlen+1, ha, hb - rlen+1, hb);
    	}else{
    		T->rchild = NULL;//右子树长度为零时，有孩子为空
    	}
    	return T;
    }
    void postoder(BiTree T){
    	if (T !=  NULL){
    		postoder(T->lchild);
    		postoder(T->rchild);
    		cout << T->data << "\t";
    	}
    }
    int main(){
    	int n;
    	cout << "输入二叉树总结点数：";
    	cin >> n;
    	char *A = (char *)malloc(sizeof(char)*n);
    	char *B = (char*)malloc(sizeof(char)*n);
    	cout << "\n" << "输入二叉树遍历的前序序列：";
    	for (int i = 0; i< n; i++){
    		cin >> A[i];
    	}
    	cout << "\n" << "输入二叉树遍历的中序序列：";
    	for (int i = 0; i < n; i++){
    		cin >> B[i];
    	}
    	BiTree T = create_BiTree(A, B,0,n-1,0,n-1);
    	cout << "\n" << "二叉树后序序列：";
    	postoder(T);//后序遍历二叉树检验结果
    	system("pause");
    	return 0;
    }

样例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70][]

二叉树先序序列：ABDEHCFIG

二叉树中序序列：DBHEAFICG

二叉树后序序列：DHEBIFGCA

结果显示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70]: /images/20211104/c64aebb74e2d47cf92ccce88b50d15aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjA3MDQ3Mw_size_16_color_FFFFFF_t_70 1]: /images/20211104/ee71b105f6b343f782f1edf804983f1c.png