©2020-2024 ioDraw All rights reserved,
Privacy Policy
typedef struct leaf { int data; struct leaf* lchild; struct leaf* rchild; }Leaf,
* lpLeaf; //这个值的作用是为当前申请的空间找到对应的先序序列位置 //也就是找到当前序列中的根节点位置 static int pos = 0;
//由先序遍历(a)和中序遍历(b)创建二叉树 lpLeaf create(int a[], int b[], int start, int end) { if
(start <= end) { int i = 0; lpLeaf p = (lpLeaf)malloc(sizeof(Leaf)); p->data = a
[pos]; for (i = start; i <= end; i++) if (b[i] == p->data) break; pos++;
//查找a中找到的根节点在b中的位置，一定能找到，找不到就错了 //查找顺序是根->左孩子->右孩子，所以要加一
//反之如果是后序则pos开始要置最大值pos-- //因为如果是后序的话（从后向前）顺序是根->右孩子->左孩子，所以p的右孩子赋值要在左孩子前面 p->
lchild= create(a, b, start, i - 1); p->rchild = create(a, b, i + 1, end); return
p; } return NULL; } //后序遍历 void look(lpLeaf root) { if (root) { look(root->
lchild); look(root->rchild); printf("%d ", root->data); } } int main() { int a[]
= { 1, 2, 3, 4, 5, 6 }; int b[] = { 3, 2, 1, 5, 4, 6 }; int i = 0; printf(
"先序序列："); for (i = 0; i < 6; i++) { printf("%d ", a[i]); } printf("\n中序序列：");
for (i = 0; i < 6; i++) { printf("%d ", b[i]); } lpLeaf root = create(a, b, 0, 5
); printf("\n后序序列："); look(root); return 0; }