树

• TreeMap和TreeSet在排序时如何比较元素？Collections工具类中的sort()方法如何比较元素？

考察点：Tree
参考回答：

TreeSet要求存放的对象所属的类必须实现Comparable接口，该接口提供了比较元素的compareTo()方法，当插入元素时会回调该方法比较元素的大小。TreeMap要求存放的键值对映射的键必须实现Comparable接口从而根据键对元素进行排序。Collections工具类的sort方法有两种重载的形式，第一种要求传入的待排序容器中存放的对象比较实现Comparable接口以实现元素的比较；第二种不强制性的要求容器中的元素必须可比较，但是要求传入第二个参数，参数是Comparator接口的子类型（需要重写compare方法实现元素的比较），相当于一个临时定义的排序规则，其实就是通过接口注入比较元素大小的算法，也是对回调模式的应用（Java中对函数式编程的支持）。

代码示例：

public class
Student implements Comparable<Student> {
     private String
name;        // 姓名
     private int
age;            // 年龄
     public Student(String name, int age) {
         this.name = name;
         this.age = age;
     }
     @Override
     public String toString() {
         return "Student [name=" +
name + ", age=" + age + "]";
     }
     @Override
     public int compareTo(Student o) {
         return this.age - o.age; // 比较年龄(年龄的升序)
     }
 }
 import java.util.Set;
 import java.util.TreeSet;
 class Test01 {
     public static void main(String[] args) {
         Set<Student> set = new
TreeSet<>();     // Java 7
     }
 }
 import java.util.Set;
 import java.util.TreeSet;
 class Test01 {
     public static void main(String[] args) {
         Set<Student> set = new
TreeSet<>();     // Java 7的钻石语法(构造器后面的尖括号中不需要写类型)
         set.add(new Student("Hao
LUO", 33));
         set.add(new Student("XJ
WANG", 32));
         set.add(new Student("Bruce
LEE", 60));
         set.add(new Student("Bob
YANG", 22));
  
         for(Student stu : set) {
             
System.out.println(stu);
         }
 //     
         set.add(new Student("Hao
LUO", 33));
         set.add(new Student("XJ
WANG", 32));
         set.add(new Student("Bruce
LEE", 60));
         set.add(new Student("Bob
YANG", 22));
         for(Student stu : set) {
             
System.out.println(stu);
         }
 //      输出结果: 
 //      Student [name=Bob YANG, age=22]
 //      Student [name=XJ WANG, age=32]
 //      Student [name=Hao LUO, age=33]
 //      Student [name=Bruce LEE, age=60]
     }
 }
 //      Student [name=Bob YANG, age=22]
 //      Student [name=XJ WANG, age=32]
 //      Student [name=Hao LUO, age=33]
 //      Student [name=Bruce LEE, age=60]
     }
 }

• 如何打印二叉树每层的节点？

考察点：二叉树
参考回答：

实现代码：

import
java.util.ArrayList;
import
java.util.Scanner;
public class Main
{
    // 定义节点
    class Node{
        int
val;
        Node
left;
        Node
right;
        public
Node(int val) {
            this.val = val;
        }
    }
    
    public 
ArrayList<Integer> gzy; // 保存根左右的序列
    public 
ArrayList<Integer> zgy; // 保存左跟右的序列
    public 
ArrayList<Node> pack;       // 保存已经排好的节点
    
    public static void main(String[] args) {
        Main
main = new Main();
        main.getResult();
        
    }
    
    public void getResult() {
        //
init
        Scanner
scanner = new Scanner(System.in);
        int
count = scanner.nextInt();
        gzy
= new ArrayList<>();
        zgy
= new ArrayList<>();
        for(int
i = 0; i < count; i++) {
            gzy.add(scanner.nextInt());
        }
        for(int
j = 0; j < count; j++) {
            zgy.add(scanner.nextInt());
        }
        pack
= new ArrayList<>();       // 已经还原的节点
        
        //
exception
        if(count
== 1) {
            System.out.println(gzy.get(0));
            return;
        }
        // 构造最左侧节点的二叉树
        Node
node = new Node(gzy.get(0));
        pack.add(node);
        int
index1 = 1;     // 根左右的下标
        Node
tmp = node;
        while(gzy.get(index1)
!= zgy.get(0)) {      // 如果没访问到最左边的叶子节点,继续还原最左侧二叉树
            tmp.left = new Node(gzy.get(index1++));
            tmp = tmp.left;
            pack.add(tmp);
        }
        tmp.left
= new Node(gzy.get(index1++));
        pack.add(tmp.left);
        
        // 加入剩余的节点完善二叉树
        for(int
k = index1; k < gzy.size(); k++) {
            fillErCS(gzy.get(k));
        }
        
        // 层次遍历
        ArrayList<Node>
res = new ArrayList<>();
        res.add(node);
        int
num = 0;
        while(res.size()
!= num) {
            System.out.print(res.get(num).val + "
");
            if(res.get(num).left != null) {
                res.add(res.get(num).left);
            }
            if(res.get(num).right != null) {
                res.add(res.get(num).right);
            }
            num++;
        }
    }
    
    // 将值为val的节点加入二叉树
    private void fillErCS(int val) {
        int
index = zgy.indexOf(val);
        // 每一个遍历的节点都是val节点的根或者在其左边
        for(int
i = index-1; i >= 0; i--) {
            if(findNode(zgy.get(i)) != null) {  // 找到待插入节点的根节点或者其左边的节点
                Node
node = findNode(zgy.get(i));
                insert(node,
val);
                break;
            }      
        }
    }
    
    // 将节点val插入二叉树
    private void insert(Node node, int val) {
        if(zgy.indexOf(node.val)
> zgy.indexOf(val)) {  // node在待插入节点的右边
            if(node.left == null) {
                node.left
= new Node(val);
                pack.add(node.left);
                return;
            }
            insert(node.left, val);
        }else
{     //
node在待插入节点的左边或是其根
            if(node.right == null) {
                node.right
= new Node(val);
                pack.add(node.right);
                return;
            }
            insert(node.right, val);
        }
    }
    // 根据val找到pack里的节点
    private Node findNode(int val) {
        for(Node
node : pack) {
            if(node.val == val) {
                return
node;
            }
        }
        return
null;
    }
}

• 如何知道二叉树的深度？

考察点：二叉树
参考回答：

实现二叉树的深度方式有两种，递归以及非递归。

①递归实现：

为了求树的深度，可以先求其左子树的深度和右子树的深度，可以用递归实现，递归的出口就是节点为空。返回值为0；

②非递归实现：

利用层次遍历的算法，设置变量level记录当前节点所在的层数，设置变量last指向当前层的最后一个节点，当处理完当前层的最后一个节点，让level指向+1操作。设置变量cur记录当前层已经访问的节点的个数，当cur等于last时，表示该层访问结束。

层次遍历在求树的宽度、输出某一层节点，某一层节点个数，每一层节点个数都可以采取类似的算法。

树的宽度：在树的深度算法基础上，加一个记录访问过的层节点个数最多的变量max,在访问每层前max与last比较，如果max比较大，max不变，如果max小于last，把last赋值给max;

代码解释：

import
java.util.LinkedList;
public class Deep
{
    //递归实现1
  public int findDeep(BiTree root)
  {
      int
deep = 0;
      
if(root != null)
      {
          int lchilddeep = findDeep(root.left);
          int rchilddeep = findDeep(root.right);
          deep = lchilddeep > rchilddeep ?
lchilddeep + 1 : rchilddeep + 1;
      }
      
return deep;
  }
  
  
  //递归实现2
  public int findDeep1(BiTree root)
  {
    
      
if(root == null)
      {
          return 0;
      }
      else
      {
       int
lchilddeep = findDeep1(root.left);//求左子树的深度
       int
rchilddeep = findDeep1(root.left);//求右子树的深度
       
return lchilddeep > rchilddeep ? lchilddeep + 1 : rchilddeep + 1;//左子树和右子树深度较大的那个加一等于整个树的深度
      }
  }
  //非递归实现
  public int findDeep2(BiTree root)
  {
     if(root == null)
         return 0;
    
     BiTree current = null;
     LinkedList<BiTree> queue = new
LinkedList<BiTree>();
     queue.offer(root);
     int
cur,last;
     int
level = 0;
     while(!queue.isEmpty())
     {
         cur = 0;//记录本层已经遍历的节点个数
         last = queue.size();//当遍历完当前层以后，队列里元素全是下一层的元素，队列的长度是这一层的节点的个数
         while(cur < last)//当还没有遍历到本层最后一个节点时循环
         {
             current = queue.poll();//出队一个元素
             cur++;
             //把当前节点的左右节点入队（如果存在的话）
             if(current.left != null)
             {
                 queue.offer(current.left);
             }
             if(current.right != null)
             {
                 queue.offer(current.right);
             }
         }
         level++;//每遍历完一层level+1
     }
     return level;
  }
  public static void main(String[] args)
 {
    BiTree root = BiTree.buildTree();
    Deep deep = new Deep();
    System.out.println(deep.findDeep(root));
    System.out.println(deep.findDeep1(root));
    System.out.println(deep.findDeep2(root));  
 }
}

• 二叉树任意两个节点之间路径的最大长度

考察点：树
参考回答：

int maxDist(Tree
root) { 
    //如果树是空的，则返回0 
    if(root == NULL) 
        return 0; 
    if(root->left != NULL) { 
        root->lm = maxDist(root->left) +1; 
    } 
    if(root->right != NULL) 
        root->rm = maxDist(root->right) +1; 
    //如果以该节点为根的子树中有最大的距离，那就更新最大距离 
    int sum = root->rm + root->lm; 
    if(sum > max) { 
        max = sum; 
    } 
  
    return root->rm > root->lm ?
root->rm : root->lm; 
}  

● 算法题：二叉树层序遍历，进一步提问：要求每层打印出一个换行符

考察点：二叉树
参考回答：

public
List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res =
new ArrayList<List<Integer>>();
        LinkedList<TreeNode> queue = new
LinkedList<TreeNode>();
        if (root == null) {
            return res;
        }
        queue.offer(root);
        while (queue.size() != 0) {
            List<Integer> l = new
ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode temp = queue.poll();
                l.add(temp.val);
                if (temp.left != null) {
                    queue.offer(temp.left);
                }
                if (temp.right != null) {
                    queue.offer(temp.right);
                }
            }
            res.add(l);
        }
        return res;
}

• 怎么求一个二叉树的深度?手撕代码?

考察点：二叉树
参考回答：

public int
maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int bigger = Math.max(left, right);
        return bigger + 1;
    }

• 请你说一下，B+树和B-树？

考察点：树
参考回答：

b+树的中间节点不保存数据，所以磁盘页能容纳更多节点元素，更“矮胖”；

b+树查询必须查找到叶子节点，b树只要匹配到即可不用管元素位置，因此b+树查找更稳定（并不慢）；

对于范围查找来说，b+树只需遍历叶子节点链表即可，b树却需要重复地中序遍历。