遍历二叉树的几种思路
一、背景最近在公司面试（一面、二面）候选人的时候，大多数候选人基本都能正确的写出非递归版的前序遍历和中序遍历二叉树，但是大多数人都不能正确的写出非递归版的后续遍历。跟一个曾经拿过NOI银牌同事私下讨论了下后续遍历算法到底难不难。结论是，说难也难说不难也不难，说不难是因为，如果你看过相关解法，你可以很快就就理解解法的思路。说难，是如果你没看过，或者看了过了很久又忘了，要在15分钟左右写个Bug free的版本还是有点难的。 跟同事讨论下二叉树遍历的几种写法，所以就有了这篇文章。 二、二叉树几种解法的思考2.1 递归版前序遍历递归 func preOrderRecursion(node *TreeNode, ans *[]int) { if node == nil { return ..
更多B-Tree、B+Tree、B*Tree
一、B-Tree1.1 什么是B-Tree 1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树，其定义如下 根结点至少有两个子女。 每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m 每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m 所有的叶子结点都位于同一层。 每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。 M = 3 1.2 B-Tree 查找假设我们要查找的数据是 5 二、B+Tree2.1 什么是B+TreeB+ 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一棵B+树包含根节点、内部节点和叶子节点。根节点可..
更多二叉树、2-3 树、红黑树
有序数组的优势在于二分查找，链表的优势在于数据项的插入和数据项的删除。但是在有序数组中插入数据就会很慢，同样在链表中查找数据项效率就很低。综合以上情况，二叉树可以利用链表和有序数组的优势，同时可以合并有序数组和链表的优势，二叉树也是一种常用的数据结构。 一、满二叉树一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为 K，且结点总数是(2^k) -1 ，则它就是满二叉树。 二、完全二叉树若设二叉树的深度为 h，除第 h 层外，其它各层 (1 ～ h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。 三、二叉查找树二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树..
更多