树

一、后序遍历 后序遍历逻辑：优先访问左、右子节点，然后访问当前节点。 一个后序遍历的示例，它的后序遍历结果为 [4, 2, 5, 6, 3, 1]： 二、非递归实现 后序遍历的非递归实现比前序和中序的非递归实现要复杂很多，因为每个节点都可能有 2 个子节点，遍历的时候节点中并没有保存当前的状态，无法确定两 ... 阅读更多

一、中序遍历 中序遍历过程：先访问左子节点，然后访问当前节点，最后访问右子节点。 以下试一次中序遍历过程： 二、非递归实现 非递归方式遍历依赖栈来实现，因为要先访问子节点，然后访问父节点，因此必须要有一个数据结构来保存已经父节点。 实现原理： 每次遍历到一个节点，不访问它，先压栈，然后对左子树循环做 ... 阅读更多

一、先序遍历 先序遍历的意思是：先遍历当前节点，再分别遍历左、右子节点。 例如一棵二叉树为： 它的先序遍历序列 （红色虚线标出来的） 为：[1, 2, 4, 3, 5 6] 。 二、递归实现 递归的实现很简单，先访问当前节点，然后分别递归访问左右子节点。 [crayon-695ba801c12f84581 ... 阅读更多

一、 B 树的基本概念 B 树是一种多叉树，被广泛应用于数据库索引中。它也是一种特殊的搜索树，和搜索树最大的不同在于它的每个节点都包含了 n 个关键字和 n+1 个指向子节点的指针。它的表现形式为： B 树的特点： 假设 x.key 为当前节点中的关键字，x.child.key 是子节点中的关键字，那么它们之间存在以下关 ... 阅读更多

一、二叉搜索树 1.1 什么是二叉搜索树 算法导论中对二叉搜索树 （Binary Search Tree, 简称 BST） 的定义： 设 x 是二叉搜索树中的一个节点，如果 y 是 x 左子树中的一个节点，那么 y.key<=x.key 。如果 y 是 x 右子树中的一个节点，那么 y.key>=x.key 。 以下两棵 ... 阅读更多