邢台专业网站建设公司,微网站和app的区别,梅河口建设局网站,网站仿通过序列构造二叉树 给出以下三个二叉树遍历的序列#xff1a; (1) 前序: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14 (2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12 (3) 后序: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1 前中序复原二叉树
所需序列 (1) 前序: 1 2 3 4 5 6 8 7 9 10 …通过序列构造二叉树 给出以下三个二叉树遍历的序列 (1) 前序: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14 (2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12 (3) 后序: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1 前中序复原二叉树
所需序列 (1) 前序: 1 2 3 4 5 6 8 7 9 10 11 12 13 15 14 (2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12 左子树复原
第一轮 通过前序 前序第一个访问的是根节点因此根节点就是1 通过中序中序遍历的特点就是根节点的左子树的元素都在根节点的左侧右子树的元素都在根节点的右侧从中序遍历序列结合前序序列可知中序序列1的左侧为左子树1的右侧为右子树。从而前序通过中序划分可知前序的左右子树。划分如下 中序序列划分 [3 4 8 6 7 5 2] 1 [ 10 9 11 15 13 14 12] 前序序列划分: 1 [2 3 4 5 6 8 7 ] [9 10 11 12 13 15 14] 分析 如何知道两个括号从哪里分开可参照中序的两个数组划分的。 前序中 7 之前的元素都在中序第一个数组中9之后的所有元素都在第二个数组中因此从7和9之间划分。 第一轮划分结果如下图 第二轮 我们先看前序和中序的第一个数组 前序: 2 3 4 5 6 8 7 中序: 3 4 8 6 7 5 2 通过上面的结论可知 根节点为2前序 然后可划分为 前序: 2 [3 4 5 6 8 7 ] 中序: [3 4 8 6 7 5 ] 2 第二轮划分结果如下图 第三轮 对 3 4 5 6 8 7 继续划分 前序: 3 [4 5 6 8 7] 中序: 3 [4 8 6 7 5] 第三轮划分结果如下图 第四轮 对 4 5 6 8 7 进行划分 前序4 [5 6 8 7] 中序4 [ 8 6 7 5 ] 第四轮划分结果如下图 第五轮 对 5 6 8 7 划分 前序5 [6 8 7] 中序[8 6 7] 5 第六轮 对 6 8 7 划分 前序6 [ 8 7 ] 中序 [8] 6 [7] 至此便可知左子树的树结构了。 左子树的树结构效果如下 左子树的复原结果如下 右子树复原
第一轮 由第一轮可知如下序列 前序 9 10 11 12 13 15 14 中序 10 9 11 15 13 14 12 对其进行划分结果如下 前序9 [ 10 11 12 13 15 14] 中序[10] 9 [11 15 13 14 12] 由结果可知10 是 9 的左子树11 15 13 14 12为还需划分的序列 第二轮 将序列11 12 13 15 14进行划分 前序11 [12 13 15 14] 中序11 [15 13 14 12] 第三轮 将12 13 15 14进行划分 前序12[13 15 14] 中序 [15 13 14]12 第四轮 将 13 15 14进行划分 前序13 [ 15 14] 中序 [15] 13 [14] 最终由中序获得结果15为13的左子树14为13的右子树 左右子树复原结果如下 中后序恢复二叉树 通过中后序恢复二叉树与前中序唯一的不同就是后续的最后一个是根节点中序的处理和上述相同。所需序列如下 (2) 中序: 3 4 8 6 7 5 2 1 10 9 11 15 13 14 12 (3) 后序: 8 7 6 5 4 3 2 10 15 14 13 12 11 9 1 左子树复原
第一轮 中序序列划分[3 4 8 6 7 5 2] 1 [10 9 11 15 13 14 12] 后序序列划分[8 7 6 5 4 3 2 ] [10 15 14 13 12 11 9 ]1 由于上述经过了上述分析对划分结果有所了解了因此此次划分就不画中间过程了 第二轮 对序列 8 7 6 5 4 3 2 进行划分 中序[3 4 8 6 7 5 ] 2 后序[8 7 6 5 4 3 ] 2 第三轮 对序列 8 7 6 5 4 3 进行划分: 中序3[4 8 6 7 5] 后序[8 7 6 5 4] 3 第四轮 对序列8 7 6 5 4进行划分 中序4 [8 6 7 5] 后序[8 7 6 5] 4 第五轮 对序列8 7 6 5进行划分 中序[8 6 7 ] 5 后序[8 7 6 ] 5 第六轮 对序列 8 7 6进行划分 中序[8] 6 [7] 后序[8 7] 6 最终由中序划分可知8是6的左子树7是6的右子树 左子树复原结果如下 右子树复原 右子树复原所需要的序列 中序10 9 11 15 13 14 12 后序10 15 14 13 12 11 9 第一轮 将序列10 15 14 13 12 11 9进行划分一般选择能确定根节点的那个节点 中序[10] 9 [11 15 13 14 12] 后序[10 15 14 13 12 11] 9 由此划分可知10为9的左节点11 15 13 14 12为9的右子树 第二轮 对序列15 14 13 12 11进行划分 中序11 [15 13 14 12] 后序[15 14 13 12] 11 第三轮 对序列15 14 13 12进行划分 中序[15 13 14] 12 后序[15 14 13] 12 第四轮 对序列15 14 13 进行划分 中序[15] 13 [14] 后序[15 14]13 从中序结果可知15为13的左子树14为13的右子树 左右子树复原结果如下 由此可知前中序和中后序恢复成 二叉树的过程有些不同但是所需的步骤和结果都是一致的。 知道了序列是如何构造成二叉树之后便可以将其使用代码实现了代码实现在下次总结。
