完全二叉树 -- 已知先序遍历,求中序遍历

大体思路

1. 一直*2, 直到小于总结点数, – 左节点
2. 在(1)不成立的情况下+1, 并且要注意临界点(下标不能超过总结点数和因为是先序, 所以父节点存在) – 右节点
3. 由左节点产生的树遍历完, 要找其兄弟节点

详细思路见代码

具体实现

#include <stdio.h>

#define MAX 100

int tree[MAX];
int tmp[MAX];

void inPrintTree(int i, int n){
	if(i <= n){
		inPrintTree(2*i, n);
		printf("%d ", tree[i]);
		inPrintTree(2*i+1, n);
	}
}

int main(){

	int n;
	scanf("%d", &n);

	for(int i = 1; i <= n; ++i){
		scanf("%d", &tmp[i]);
	}// 默认节点值 > 0

	int cur = 1;
	tree[cur] = tmp[cur];
	for(int i = 2; i <= n; ++i){
		
		if(cur * 2 <= n){ // 一直*2 知道小于总结点树
			cur *= 2;
			tree[cur] = tmp[i];
			printf("左节点的值为: %d , cur = %d\n", tree[cur], cur);
		}else if( cur+1 <= n && tree[cur+1] == 0 && tree[(cur+1)/2] != 0) {	// cur + 1 即右节点, 但有前提, cur + 1 <= n和tree[(cur+1)/2] != 0
			cur ++;
			tree[cur] = tmp[i];
			printf("右节点的值为: %d, cur = %d\n", tree[cur], cur);
		}else{
			// 当前是左节点. 上一级就是直接找到兄弟节点
			// 当前是右节点. 就需要循环至当前节点是左节点位置. 判断依据为 cur是否是奇数, 是奇数表示是右节点
			while( 1 == cur%2){
				cur /= 2;
			}
			cur ++;		
				
			tree[cur] = tmp[i];
			printf("上一层右节点的值为: %d, cur = %d\n", tree[cur], cur);
		}
	}
	printf("层次遍历: \n");
	for(int i = 1; i <= n; ++i){
		printf("%d ", tree[i]);
	}
	printf("\n");

	printf("中序遍历: \n");
	inPrintTree(1, n);
	printf("\n");

	return 0;
}

运行结果

输入从data.in读取, 数据见下面
我取的数据为层次遍历是递增的结果. 方便校验.