根据树的前序和后序表达式构造唯一树

根据树的前序和后序表达式构造唯一树

原题是“根据树的前序和后序表达式求中序表达式”,构造出了树求中序表达式还是问题吗?

构造树是需要一定技巧的,需要不断的递归分析。将大规模分为小规模,将每个小规模再细分,直到不可再分,树也就构建好了。就跟 归并排序 一样

前序和中序分别是:

pre: A B D E G C F

on: D B G E A C F

分析(选择题)

从前序表达式入手:我们知道前序遍历的第一个节点是根节点,由此确定 A 就是根节点

再来看中序表达式,根据中序表达式规则,先遍历左子节点,再遍历父节点,再遍历右子节点,我们可以确定 A 左边的都是左子树,右边的都是右子树。

在 on 中看得出 A 的左子树个数是 4,于是我们可以在 pre 中定位 A 的左子树和右子树:

A 的左子树前序序列是 B D E G,右子树前序序列是 C F,根据前序表达式规则,每一个序列的第一个是整个序列的根节点,于是可以推断出 A 的左子树的根节点和右子树的根节点分别是 B、C

循环上面的的方法,分析 B 的左子树。(右子树暂时不管,等左子树分析完毕之后再分析。)

pre: B D E G

on: D B G E

由 B 的左边只有 D 可推导出 D 是 B 的左子树,并且是唯一节点。E 是 B 的右子树的根节点。

然后推断 B 的右子树

pre: E G ——> (序列的第一个是头,因为总是从头先遍历)E 是 G 的父节点

on: G E ——> “左、父、右” 推导出 G 是 E 的左子节点

至此,根节点 A 的左子树有了归宿,现在分析右子树:

pre: C F ——> C 是 F 的头节点

on: C F ——> “先左再头再右” 推导出 F 是 C 的右子节点

一个树分析出来了

所以它的后序表达式是:DGEBFCA

归纳

  1. 对于一串前序表达式和中序表达式,我们总是先取前序表达式的第一个节点,因为它是头。

  2. 再根据这个头在中序中的位置来 划分 头的左子树和右子树,根据中序中的左子树和右子树的个数在前序中确定左子树范围和右子树范围。

  3. 每一个范围的序列都有前序表达式和中序表达式,循环调用步骤 1 ,直到序列只有一个。

代码实现(编程题)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class TreeTraversal {

/**
* 根据前序和中序表达式构建树
*/
public static TreeNode createTreeByPreOrderAndInOrder(String preOrder, String inOrder) {
if (preOrder.isEmpty()) {
return null;
}

char root = preOrder.charAt(0); // 获取前序的第一个字符
int rootIndex = inOrder.indexOf(root); // 获取根节点在中序中的位置
TreeNode rootNode = new TreeNode(preOrder.substring(0, 1)); // 创建根节点

int leftCount = rootIndex; // 根节点的左子树的中序表达式字符数量

// 递归构建左子树
rootNode.setLeftNode(createTreeByPreOrderAndInOrder(
preOrder.substring(1, leftCount + 1), // 截取前序表达式中 根节点 左边的字符串
inOrder.substring(0, leftCount)) // 截取中序表达式中 根节点 左边的字符串
);

// 递归构建右子树
rootNode.setRightNode(createTreeByPreOrderAndInOrder(
preOrder.substring(leftCount + 1), // 截取前序表达式中 根节点 右边的字符串
inOrder.substring(leftCount + 1) // 截取前序表达式中 根节点 右边的字符串
));

return rootNode;
}

public static void main(String[] args) {
// 构造树
TreeNode root = TreeCreator.getInstance();
System.out.print("pre: \t");
preOrder(root);
System.out.println();

System.out.print("in: \t");
inOrder(root);
System.out.println();

System.out.print("post: \t");
postOrder(root);

// 根据前序和中序求后序
System.out.println("\n---------- createTreeByPreOrderAndInOrder ----------");
TreeNode rootNode = createTreeByPreOrderAndInOrder("ABDEGCF", "DBGEACF");
postOrder(rootNode);
}
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×