已知二叉树中序遍历序列，再加前序遍历序列或后序遍历序列的一种，可以{wy}确定一棵二叉树。（已知前序和后序得到的二叉树可能不{wy}。）
前序和后序遍历的作用类似，用于确定根节点，进而分割中序序列。
代码以前序遍历加中序遍历为例。
#include <stdio.h> #include <string.h> const int MaxN = 1001; char pre[MaxN] , in[MaxN]; int hash[128]; int cnt; typedef struct Node { char ch; Node *lch , *rch; } Node , *Tree; void DFS(Tree &T , int s , int r) { if (s > r) { T = NULL; return; } T = new Node; int i = cnt ++; T->ch = pre[i]; DFS(T->lch , s , hash[pre[i]] - 1); DFS(T->rch , hash[pre[i]] + 1 , r); } void PostOrderTraverse(Tree T) { if (T == NULL) return; PostOrderTraverse(T->lch); PostOrderTraverse(T->rch); printf("%c" , T->ch); } void __test() { puts("前序遍历序列："); scanf("%s" , pre); puts("中序遍历序列："); scanf("%s" , in); Tree T = NULL; int len = strlen(pre) , i; memset(hash , -1 , sizeof(hash)); cnt = 0; for (i = 0;i < len;i ++) { hash[in[i]] = i; } DFS(T , 0 , len - 1); puts("后序遍历序列："); PostOrderTraverse(T); } int main() { __test(); return 0; } |
Tags:
