算法：二叉树的三种遍历 二叉搜索树的遍历

js表示一个二叉树

interface ITreeNode {value: numberleft: ITreeNode | nullright: ITreeNode | null
}const bst: ITreeNode = {value: 5,left: {value: 3,left: {value: 2,left: null,right: null},right: {value: 4,left: null,right: null,}},right: {value: 7,left: {value: 6,left: null,right: null},right: {value: 8,left: null,right: null}}
}

思路

• 前序遍历：先根，再left，再right。例如5、324、768
• 中序遍历：先left，再根，再right。例如234、5、678
• 后序遍历：先left，再根，再right。例如243、687、5

代码

export interface ITreeNode {value: numberleft: ITreeNode | nullright: ITreeNode | null
}const arr: number[] = []/* 二叉树前序遍历* @param node tree node*/
function preOrderTraverse(node: ITreeNode | null) {if (node == null) returnconsole.log(node.value)arr.push(node.value)preOrderTraverse(node.left)preOrderTraverse(node.right)
}/* 二叉树中序遍历* @param node tree node*/
function inOrderTraverse(node: ITreeNode | null) {if (node == null) returninOrderTraverse(node.left)console.log(node.value)arr.push(node.value)inOrderTraverse(node.right)
}/* 二叉树后序遍历* @param node tree node*/
function postOrderTraverse(node: ITreeNode | null) {if (node == null) returnpostOrderTraverse(node.left)postOrderTraverse(node.right)console.log(node.value)arr.push(node.value)
}

测试

preOrderTraverse(bst)
inOrderTraverse(bst)
postOrderTraverse(bst)

打印结果，和思路里面的一样

二叉搜索树

二叉搜索树（Binary Search Tree），就是从做到右依次递增的一个二叉树。如：

遍历适合中序遍历，相当于拍平为一个有序的数组。

/* 寻找 BST 里的第 K 小值* @param node tree node* @param k 第几个值*/
export function getKthValue(node: ITreeNode, k: number): number | null {inOrderTraverse(node)return arr[k - 1] || null
}
console.log(getKthValue(bst, 3))

输出结果为 4

二叉树为什么这么重要

二分
尽量保持二叉树的平衡，否则如果这个二叉树只有左边，那不就成了链表了，没有二分的优势了

平衡二叉树：
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
红黑树就是一种平衡二叉树。