树的底层实现（上）
本片内容是根据Adam Drozdek编写的英文版教材《数据结构与算法》整理的，主要是树的底层实现，以及相关的一些内容。后面会再整理一些应用到了树的经典算法题。由于知识点较多，所以分成两篇文章。
1.基本介绍1.1树的出现先来看看其他几种数据结构，链表相对数组更灵活，尤其是插入和删除操作，但是链表不能表示封层对象；栈和队列可以反应出分层，当时仅限于一维。所以引入了一种新的数据结构：树，来表示分层的对象。
1.2树的一些定义Length：从根节点到目的节点的边（两个节点之间为一条边）的数量
Level：length+1
Height：level的最大值
1.3树的类别二叉树（binary tree）：每个节点最多有两个子节点，这两个子节点称为左节点、又节点
完全二叉树（complete binary tree）：非终结节点（树的最后一个节点）都有两个子节点，且所有的叶节点（leaves）都在同一层。
二叉搜索树（binary search tree）：对于所有的节点，左子节点比父节点的值小，右子结点比父节点的值大，（一个树里没有相同值的节点）
平衡树（balanced tree）：对于任何节点的左子树和右子树的高度差小于等于1
二叉树的应用很广泛，尤其是二叉搜索树，所以后面的代码示例大多都是针对二叉搜索树。
2.二叉树的实现2.1通过数组实现数组里存放的是对象：
Index
Value
leftPosition
rightPosition
0
13
1
2
1
14
-1
-1
2
15
-1
-1
缺点：具有Array的通病：当进行删除节点的操作时其他的节点需要移动；也可以不移动，而直接将对应位置的值删除留下一个hole，但是多次进行删除操作后，就会留下很多hole。
2.2通过链表实现先序：15 8 4 11 21 17 30
中序：4 8 11 15 17 21 30
后序：4 11 8 17 30 21 15
4.2.1使用递归实现深度遍历public Boolean delete(int i){ Node pre = null; Node tmp = root; //找到删除的那个节点以及它的父节点 while(tmp!=null&&tmp.value!=i){ pre=tmp; if(tmp.value<i) tmp=tmp.right; else tmp=tmp.left; } Node node = tmp; if(tmp==null){ System.out.println("the node isnot found"); return false; } else{ //如果待删节点的左节点为空，则直接将待删节点的右节点连到父节点 if(tmp.left==null) pre.right=tmp.right; else if(tmp.right == null) pre.left = tmp.left; //如果待删节点有左右节点，则首先找到左子节点的最右端的节点A， //将待删节点的右节点连到A，然后待删节点的父节点连到待删节点的左节点 else{ Node rightmost = tmp.left; while(rightmost.right!=null) rightmost=rightmost.right; rightmost.right = tmp.right; tmp=tmp.left; if(node == root) root = tmp; else if(pre.left==node) pre.left = tmp; else pre.right = tmp; } return true; } }
