二叉树

树的深度是O(log n)有左孩子，右孩子满二叉树，每个分支都是满的完全二叉树，去除满二叉树靠后的一些节点，保证最后一个节点之前的节点都是完整的可使用数组或链表表示

二叉树使用数组时的定位方法

当前节点n 左孩子 2n+1 右孩子 2n+2

反之，当前节点为其父节点左孩子，父节点(n-1)/2；右孩子，父节点(n-2)/2

二叉树应用

二叉查找树（二叉排序树），根节点大于左孩子，小于右孩子 1.查找 从根节点开始依次对比，类似二分查找，故复杂度O(log n)

2.维持相对顺序 按大小插入数据

二叉树遍历

1.深度优先

前序中序后序 适合使用迭代或者同样拥有“回溯”属性的栈来写代码

2.广度优先

层序遍历 适合使用队列来写

转载于:https://www.cnblogs.com/j-c-y/p/11544008.html

相关资源：数据结构课程设计-二叉树的基本操作