一文读懂什么是二叉搜索树(BST)、中序遍历、前序遍历、后序遍历 |
您所在的位置:网站首页 › 遍历输出是什么意思啊英文 › 一文读懂什么是二叉搜索树(BST)、中序遍历、前序遍历、后序遍历 |
目录
什么是二叉搜索树(BST)?什么是中序遍历?如果用前序、后序遍历这棵树呢?
什么是二叉搜索树(BST)?
其实这个概念非常简单,二叉树里每个节点都是一个爸爸,每个爸爸有两个儿子 而二叉“搜索”树就是要满足一个额外的条件:所有左儿子的数字都比爸爸数字小,所有右儿子的数字都比爸爸数字大。 示例: “前序遍历”、“中序遍历”、“后序遍历”里说的遍历,实际上是我们遍历二叉树的方式。 其实一张图就能给你解释什么叫中序遍历: (其中,箭头表示遍历顺序。二叉树本身的箭头没画。) 我们发现,这个“前”、“中”、“后”其实指的就是ROOT在遍历当中的位置嘛,左右两部分一直都是从左到右。 比如中序遍历的过程,我们来看一个例子: 如下一棵随便画的二叉树,搞得很丑但我不管: 注意,遍历的时候,记住一个关键点:我们遍历的是树而不是节点 这么说有点抽象,具体一点说:每次遍历的时候,要把子树看成一个整体, 比如我们来看一个最大的格局:爸爸节点是1号,那么左子树是2、4、5、7、8整个整体,右子树是3、6、9、10整个整体, 在这个最大格局上进行遍历,那就是左子树整体->1号->右子树整体 所以我们现在知道要从左子树开始,那么左子树也要遵循中序遍历,所以顺序应该是 4、7整体 -> 2 -> 5、8整体 然后进入1 然后进入右子树,右子树也遵循中序遍历: 空白(3开头的右子树并没有左边部分) -> 3 -> 6、9、10整体 依此类推,如果你能理解完整的顺序: 4、7、2、8、5、1、3、9、6、10 说明你已经理解了中序遍历,记住每次进入一个子树的时候,不要急着先遍历这个子树的爸爸,每个子树也都是要从左边开始才能是中序遍历的! 如果用前序、后序遍历这棵树呢?其实是一样的道理,只要每次遵循前序、后序遍历的规则,而不是用中序的规则而已。 前序:1、2、4、7、5、8、3、6、9、10 后序:7、4、8、5、2、9、10、6、3、1 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |