二叉树

二叉树和链表类似，它是一种基于链表的数据结构。当二叉树所有节点都偏向一侧时，二叉树就退化为“链表”。

二叉树中插入与删除节点可以通过修改指针来实现。

二叉树遍历方式可以分为层序遍历、前序遍历、中序遍历和后序遍历等。

层序遍历是从顶部到底部，逐层遍历二叉树，并且从左往右，属于是广度优先遍历；前序、中序以及后序遍历是深度优先遍历。

读完这个遍历的分类后，就觉得前序中序和后序遍历讲的不是很清楚。

为了特别区分，插入下图。这张图还是讲的很明显。

前序：ABDFECGH

中序：DFBEACHG

后序：FDEBHGCA

仔细认真琢磨一下，其实挺简单的。

总结：无论是哪种遍历方法，都可以从二叉树顶端的根节点出发，然后执行根左右、左根右或者左右根，然而无论是哪种顺序，如果先执行的这个节点又是下个子树的根节点，那么应该继续按照根左右、左根右或者左右根的执行顺序，直到完成。

二叉搜索树满足以下条件：对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。（2）任意节点的左、右子树也是二叉搜索树。

可以发现，二叉搜索树在进行中序遍历时，总是会优先遍历下一个最小节点，所以二叉搜索树的中序遍历序列是升序的。

它的常见应用有：系统中的多级索引，实现高效的查找、插入、删除等操作；也可以作为一些算法的底层搜索算法的数据结构；也可以存储数据流，保持其有序的状态。

AVL树旋转为了让二叉树保持平衡。其目的是降低时间复杂度，有多种旋转方式。

本文来自论坛，点击查看完整帖子内容。