一、树 & 二叉树

树是由节点和边构成，储存元素的集合。节点分根节点、父节点和子节点的概念。

如图：树深=4; 5是根节点；同样8与3的关系是父子节点关系。

二叉树binary tree，则加了“二叉”（binary），意思是在树中作区分。每个节点至多有两个子（child）,left child & right child。二叉树在很多例子中使用，比如二叉树表示算术表达式。

如图：1/8是左节点；2/3是右节点；

二、二叉搜索树 BST

顾名思义，二叉树上又加了个搜索的限制。其要求：每个节点比其左子树元素大，比其右子树元素小。

如图：每个节点比它左子树的任意节点大，而且比它右子树的任意节点小

Java 实现代码如下：

public class BinarySearchTree {    

/**    * 根节点    */    

public static TreeNode root;    

publicBinarySearchTree() {        

this.root = null;    

}   

 /**    * 查找    *      树深(N) O(lgN)    

 *      1\. 从root节点开始    

 *      2\. 比当前节点值小,则找其左节点    

 *      3\. 比当前节点值大,则找其右节点    

 *      4\. 与当前节点值相等,查找到返回TRUE    

 *      5\. 查找完毕未找到,    

 * @param key    

 * @return

*/    public TreeNode search (int key) {        

TreeNode current = root;

while(current != null                && key != current.value)

 {if(key < current.value )                

current = current.left;

else current = current.right;        

}returncurrent;    

}    

/**    * 插入   

*      1\. 从root节点开始    

 *      2\. 如果root为空,root为插入值    

 *      循环:   

 *      3\. 如果当前节点值大于插入值,找左节点    

 *      4\. 如果当前节点值小于插入值,找右节点    

 * @param key   

 * @return

*/    

public TreeNode insert (int key) {        

// 新增节点        

TreeNode newNode = new TreeNode(key);        

// 当前节点        

TreeNode current = root;        

// 上个节点        

TreeNode parent  = null;       

 // 如果根节点为空if(current == null) {            

root = newNode;returnnewNode;        

}while(true) {            

parent = current;if(key < current.value) {               

 current = current.left;if(current == null) {                    

parent.left = newNode;returnnewNode;                

}            

}else{                

current = current.right;if(current == null) {                    

parent.right = newNode;returnnewNode;               

 }            

}       

 }   

 }   

 /**    * 删除节点    

 *      1.找到删除节点    

 *      2.如果删除节点左节点为空 , 右节点也为空;    

 *      3.如果删除节点只有一个子节点 右节点 或者 左节点    

 *      4.如果删除节点左右子节点都不为空    

 * @param key    

 * @return

*/    

public TreeNode delete (int key) {        

TreeNode parent  = root;        

TreeNode current = root;        

boolean isLeftChild =false;        

// 找到删除节点 及 是否在左子树

while(current.value != key) {            

parent = current;if(current.value > key) {                

isLeftChild =true;                

current = current.left;            

}else{               

 isLeftChild =false;                

current = current.right;            

}if(current == null) {

return current;            

}        

}        

// 如果删除节点左节点为空 , 右节点也为空

if(current.left == null && current.right == null) {

if(current == root) {                

root = null;            

}            

// 在左子树

if(isLeftChild ==true) {                

parent.left = null;            

}else{                

parent.right = null;            

}        

}        

// 如果删除节点只有一个子节点 右节点 或者 左节点

else if(current.right == null) {

if(current == root) {               

 root = current.left;            

}else if(isLeftChild) {                

parent.left = current.left;            

}else{                

parent.right = current.left;            

}        

}else if(current.left == null) {

if(current == root) {                

root = current.right;            

}else if(isLeftChild) {                

parent.left = current.right;             

}else{                

parent.right = current.right;            

}        

}        

// 如果删除节点左右子节点都不为空

else if(current.left != null && current.right != null) {            

// 找到删除节点的后继者            

TreeNode successor = getDeleteSuccessor(current);

if(current == root) {                

root = successor;            

}else if(isLeftChild) {                

parent.left = successor;            

}else{                

parent.right = successor;            

}            

successor.left = current.left;        

}

return current;    }   

 /**    

 * 获取删除节点的后继者    

 *      删除节点的后继者是在其右节点树种最小的节点    

 * @param deleteNode    

 * @return

*/    

public TreeNode getDeleteSuccessor(TreeNode deleteNode) {       

 // 后继者        

TreeNode successor = null;        

TreeNode successorParent = null;       

 TreeNode current = deleteNode.right;while(current != null) {            

successorParent = successor;           

 successor = current;           

 current = current.left;        

}        

// 检查后继者(不可能有左节点树)是否有右节点树        

// 如果它有右节点树,则替换后继者位置,加到后继者父亲节点的左节点.

if(successor != deleteNode.right) {            

successorParent.left = successor.right;           

 successor.right = deleteNode.right;        

}

return successor;   

 }    

public void toString(TreeNode root) {

if(root != null) {           

 toString(root.left);            

System.out.print("value = "+ root.value +" -> ");            

toString(root.right);        

}    

}

}

/** * 节点 */

class TreeNode {    

/**    * 节点值    */    

int value;    

/**    * 左节点    */    

TreeNode left;    

/**    * 右节点    */    

TreeNode right;    

public TreeNode(int value) {       

this.value = value;        

left  = null;        

right = null;    

}

}

面试点一：理解 TreeNode 数据结构

节点数据结构，即节点分左节点和右节点及本身节点值。如图

面试点二：如何确定二叉树的最大深度或者最小深度

答案：简单的递归实现即可，代码如下：

int maxDeath(TreeNode node){

if(node==null){

return 0;    

}   

 int left = maxDeath(node.left);   

 int right = maxDeath(node.right);

returnMath.max(left,right) + 1;

}    

int getMinDepth(TreeNode root){

if(root == null){return0;        

}

return getMin(root);    

}   

 int getMin(TreeNode root){

if(root == null){

return Integer.MAX_VALUE;        

}

if(root.left == null&&root.right == null){

return1;        

}

return Math.min(getMin(root.left),getMin(root.right)) + 1;   

 }

面试点三：如何确定二叉树是否是平衡二叉树

答案：简单的递归实现即可，代码如下：

boolean isBalanced(TreeNode node){

returnmaxDeath2(node)!=-1;    

}    

int maxDeath2(TreeNode node){

if(node == null){

return 0;        

}        

int left = maxDeath2(node.left);        

int right = maxDeath2(node.right);

if(left==-1||right==-1||Math.abs(left-right)>1){

return-1;        

}

returnMath.max(left, right) + 1;    

}

前面面试点是 二叉树 的，后面面试点是 搜索二叉树 的。先运行搜搜二叉树代码：

public class BinarySearchTreeTest {    

public static void main(String[] args) {        

BinarySearchTree b = new BinarySearchTree();        

b.insert(3);

b.insert(8);

b.insert(1);

b.insert(4);

b.insert(6);        

b.insert(2);

b.insert(10);

b.insert(9);

b.insert(20);

b.insert(25);        

// 打印二叉树        

b.toString(b.root);        

System.out.println();        

// 是否存在节点值10        

TreeNode node01 = b.search(10);        

System.out.println("是否存在节点值为10 => "+ node01.value);        

// 是否存在节点值11        

TreeNode node02 = b.search(11);        

System.out.println("是否存在节点值为11 => "+ node02);        

// 删除节点8        

TreeNode node03 = b.delete(8);        

System.out.println("删除节点8 => "+ node03.value);        

b.toString(b.root);    

}

}

结果如下：

value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 8 -> value = 9 -> value = 10 -> value = 20 -> value = 25 -> 是否存在节点值为10 => 10是否存在节点值为11 => null删除节点8 => 8value = 1 -> value = 2 -> value = 3 -> value = 4 -> value = 6 -> value = 9 -> value = 10 -> value = 20 -> value = 25 ->

面试点四：搜索二叉树如何实现插入

插入，和删除一样会引起二叉搜索树的动态变化。插入相对删处理逻辑相对简单些。如图插入的逻辑：

从root节点开始

如果root为空,root为插入值

循环:

如果当前节点值大于插入值,找左节点

如果当前节点值小于插入值,找右节点

面试点五：搜索二叉树如何实现查找

其算法复杂度 : O(lgN),树深(N)。如图查找逻辑：

从root节点开始

比当前节点值小,则找其左节点

比当前节点值大,则找其右节点

与当前节点值相等,查找到返回TRUE

查找完毕未找到

面试点五：搜索二叉树如何实现删除

比较复杂了。首先找到删除节点，其寻找方法：删除节点的后继者是在其右节点树种最小的节点。如图删除对应逻辑：

结果为：

（1）找到删除节点

（2）如果删除节点左节点为空 , 右节点也为空

（3）如果删除节点只有一个子节点 右节点 或者 左节点

（4）如果删除节点左右子节点都不为空

三、小结

就像码出高效面试的程序媛偶尔吃一碗“老坛酸菜牛肉面”一样的味道，品味一个算法，比如 BST 的时候，总是那种说不出的味道。