什么是排序二叉树?
- 首先它是二叉树,二叉树的每个结点最多有两个子节点
- 排序二叉树就是左节点(如果存在的话)一定小于父节点,右节点(如果存在的话)一定大于父节点的二叉树
常用遍历方法
- 前序遍历(复制一个排序二叉树最快)
- 中序遍历(得到二叉树从小到大排序的数据)
- 后序遍历(文件系统常用)
引用一张图片作为例子
image
算法思想和例子
前序遍历
- 思想:先访问根节点,再访问左孩子,最后访问右孩子
- 以上图为例:得到 [8, 3, 1, 6, 4, 7, 10, 14, 13]
- 伪代码:
// 根 --> 左 --> 右
// root是根节点或者是当前节点
function Traversal(root) {
//访问输出根节点
print(root)
// 左节点存在
if (root.left) {
Traversal(root.left)
}
//右节点存在
if (root.right) {
// root.right作为根节点
Traversal(root.right)
}
}
中序遍历
- 思想:先访问左孩子,再访问根节点,最后访问右孩子
- 以上图为例:得到 [1, 3, 4, 6, 7, 8, 10, 13, 14]
- 伪代码:
// 左 --> 根 --> 右
function Traversal(root){
if (root.left) {
Traversal(root.left)
}
print(root)
if (root.right) {
Traversal(root.right)
}
}
后序遍历
- 思想:先访问左孩子,再访问右孩子,最后访问根节点
- 以上图为例:得到 [1, 4, 7, 6, 3, 13, 14, 10, 8]
- 伪代码:
// 左 --> 右 --> 根
function Traversal(root){
if (root.left) {
Traversal(root.left)
}
if (root.right) {
Traversal(root.right)
}
print(root)
}
总结帮助记忆
- X序遍历一定都是先访问左子树再访问右子树的
- 前序遍历:根 --> 左 --> 右
- 中序遍历:左 --> 根 --> 右
- 后序遍历:左 --> 右 --> 根
- X序遍历是指访问根的顺序
网友评论