什么是二叉树的前序序列 二叉树的前序序列和中序序列的关系


只要是搞计算机的,对数据结构中二叉树遍历都不陌生,但是如果用到的机会不多那么就会慢慢淡忘,温故而之新才是最好的学习方式,现在就重新温习一下这方面的知识 。
遍历解析
首先我想先改变这几个遍历的名字(前根序遍历,中根序遍历,后根序遍历);前中后本来就是相对于根结点来说的,少一个字会产生很多不必要的误解 。
1. 前根序遍历:先遍历根结点,然后遍历左子树,最后遍历右子树 。
ABDHECFG
【什么是二叉树的前序序列 二叉树的前序序列和中序序列的关系】 2.中根序遍历:先遍历左子树,然后遍历根结点,最后遍历右子树 。
HDBEAFCG
3.后根序遍历:先遍历左子树,然后遍历右子树,最后遍历根节点 。
HDEBFGCA
已知一棵二叉树的前根序序列和中根序序列,构造该二叉树的过程如下:
1. 根据前根序序列的第一个元素建立根结点;
2. 在中根序序列中找到该元素,确定根结点的左右子树的中根序序列;
3. 在前根序序列中确定左右子树的前根序序列;
4. 由左子树的前根序序列和中根序序列建立左子树;
5. 由右子树的前根序序列和中根序序列建立右子树 。
已知一棵二叉树的后根序序列和中根序序列,构造该二叉树的过程如下:
1. 根据后根序序列的最后一个元素建立根结点;
2. 在中根序序列中找到该元素,确定根结点的左右子树的中根序序列;
3. 在后根序序列中确定左右子树的后根序序列;
4. 由左子树的后根序序列和中根序序列建立左子树;
5. 由右子树的后根序序列和中根序序列建立右子树 。
-- 展开阅读全文 --

    推荐阅读