二叉树的基本知识就不说了，谈一些有意思的问题！
想要存储一棵二叉树，我们有两种方法
一种是基于指针或者引用的二叉链式存储法，
一种是基于数组的顺序存储法。
链式存储 大部分二叉树代码都是通过这种结构来实现的。
链式存储
每个节点有 3 个字段，data 存储数据，另外两个是指向左右子节点的指针
顺序存储 存储适用性不强，一般只用于完全二叉树
顺序存储
二叉树的遍历
二叉树的遍历方式有很多，如果限制了从左到右的习惯方式，那么主要就分为四种：
-
前序遍历(DLR)：根结点，遍历左子树，遍历右子树【根左右】百度百科
前序遍历: ABDGHCEIF
-
中序遍历(LDR)：遍历左子树，根结点，遍历右子树【左根右】百度百科
中序遍历: GDHBAEICF
-
后序遍历(LRD)：遍历左子树，遍历右子树，根结点【左右根】百度百科
后序遍历：GHDBIEFCA
-
层序遍历：从根结点，从上而下逐层遍历
层序遍历：ABCDEFGHI
那为什么要有这么多遍历方法呢
我们用图形的方式来表现树的结构，可以非常直观的理解，但是对于计算机来说，它只有循环、判断等方式来处理，换种方式说，就是它只会处理线性序列，而刚才四种遍历方法，都是把树中的结点变成某种意义的线性结构。
推导二叉树
很多面试会问这个问题。给出前序ABCDEF，中序CBAEDF，问后序是什么？
其实很简单前序先访问根结点 A，中序 A 左边就是左子树，可以根据上面的图自己推导着画一下，结果CBEFDA
简单的二叉树代码实现
class node
{
public $data = null;
public $left = null;
public $right = null;
public $parent = null;
function __construct($data)
{
$this->data = $data;
}
}
class tree
{
public $root = null;
public $size = 0;
public $depth = null;
function __construct($data)
{
$this->root = new node($data);
$this->size++;
$this->depth++;
}
function addNode($arr)
{
foreach ($arr as $value) {
$current = $this->root;
$parent = null;
$currentDept = 1;
while ($current !== null) {
$parent = $current;
if ($value == $current->data) {
continue 2;
} elseif ($current->data > $value) {
$current = $current->left;
} else {
$current = $current->right;
}
$currentDept++;
}
$node = new node($value);
$node->parent = $parent;
if ($parent->data > $value) {
$parent->left = $node;
} else {
$parent->right = $node;
}
if ($this->depth < $currentDept) {
$this->depth++;
}
$this->size++;
}
return true;
}
function showTree()
{
return $this->root;
}
}
二叉查找树
查找树其实就是在规则上限制了数据。它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。
它是怎么做到这些的呢？
二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
时间复杂度其实都跟树的高度成正比 O(logn)
散列表和二叉查找树
散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 O(1)
二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度才是 O(logn)
相对散列表，好像并没有什么优势，那我们为什么还要用二叉查找树呢？
- 如果要输出有序数据，散列表就要先排序，二叉树则可以通过中序遍历在 O(n) 时间复杂度内输出
- 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
- 尽管散列表的查找等操作的时间复杂度是常量级的，平衡二叉查找树是 O(logn) 但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定快
- 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
- 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。
平衡二叉查找树，红黑树？红黑树
网友评论