树

概念

要了解二叉树，首先了解一下树，罗列一下树常用到的概念

树：树是一些节点的集合

根：通俗的看，最上面的节点称为根

边：除根节点外，每一个节点都会有来自另一个节点指向的有向的边

树：一棵树是N个节点和N-1条边的集合，其中的一个节点叫做根

父亲：指向自己的节点称为父亲，父节点

儿子：自己指向的节点称为儿子，子节点

兄弟：具有相同父亲的子节点称为兄弟

树叶：没有儿子的节点称为树叶，也就是度为0的节点，也成为叶子节点

度：如果一个节点有三个子节点，称这个节点的度为3。所以这个度是广度

深度：二叉树任意一个节点到根节点的距离，叫做深度。根节点的深度为1（也有书称根节点的深度为0，仅仅是一个规则哈），根节点的子节点的深度为1

高：二叉树中任意一个节点到叶子节点的距离，叫做高。所有树叶的高都是1（也有书称根节点的深度为0，仅仅是一个规则哈），空节点的高度是0。一棵树的高等于根节点的高

树的遍历

• 先序遍历

• 先序遍历中，对节点的处理工作都是在它的诸儿子节点被处理之前进行的

• 后序遍历

• 后序遍历中，对节点的处理工作都是在它的诸儿子节点被处理之后进行的

二叉树

概念

二叉树是一棵树，其中每个节点都不能有有多余两个的儿子

二叉树的种类

满二叉树

如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵树被称为满二叉树

完全二叉树

除了底层节点可能没有填满，期许每层的节点度为2，并且底层的节点都集中在该层最左边的若干位置

满二叉树一定是完全二叉树

优先级队列(堆)就是一个完全二叉树

二叉搜索树

对树中的每个节点，它的左子树所有项的值小于X中的项，而它的右子树中的所有项的值大于X中的项

二叉查找树要求所有的项都能够排序

平衡二叉搜索树

首先它是一棵二叉搜索树

它是一棵空树，或者某节点的左右两个子树的高度查绝对值不超过1

二叉树的存储方式

• 链式存储

• 使用指针的方式
• 一般情况下用链式存储比较多

• 顺序存储

• 使用数组

二叉树的遍历方式

二叉树的遍历方式跟图论中的遍历方式一致，一个是深度优先遍历，一个是广度优先遍历

深度优先遍历：先往深处遍历，遇到叶子节点时再往回遍历

前序遍历（递归法、迭代法）

中序遍历（递归法、迭代法）

后序遍历（递归法、迭代法）

广度优先遍历：一层一层遍历

层次遍历

深度优先遍历一般使用递归的方式实现，另一种就是借助栈使用非递归的方式实现

理论上来说二叉树中每一种可以用递归法解决题目的都可以使用相应的迭代法

广度优先遍历一般使用队列实现，用一个队列来实现堆二叉树一层一层的遍历

层序遍历就是迭代法