1.1. 基本结构


1.1.1. 二叉树

二叉树是一种常用的数据结构,它的逻辑简单:除根节点外每个节点都有一个父节点,根节点没有父节点;除叶子节点外,所有节点都有一个或者多个子节点,叶子节点没有子节点。面试中出现的树结构,一般都是二叉树结构。在二叉树中,最重要几种遍历方式:

  • 前序遍历:根节点 >> 左节点 >> 右节点 10>>6>>4>>8>>14>>12>>16
  • 中序遍历:左节点 >> 根节点 >> 右节点 4>>6>>8>>10>>12>>14>>16
  • 后序遍历:左节点 >> 右节点 >> 根节点 4>>8>>6>>12>>16>>14>>10

PS:必须对这三种遍历方式的六种实现了如指掌(递归+遍历)

import java.util.ArrayList;
public class Main {
    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.initTree();
        //前序
        ArrayList<Integer> prelist = new ArrayList<>();
        prelist = tree.preOrder(tree.getRoot(),prelist);
        System.out.println("前序:"+prelist);
        //前序-非递归
        ArrayList<Integer> prelist2 = new ArrayList<>();
        prelist2 = tree.preOrder2(tree.getRoot(),prelist2);
        System.out.println("前序:"+prelist2);
        //中序
        ArrayList<Integer> inlist = new ArrayList<>();
        inlist = tree.inOrder(tree.getRoot(),inlist);
        System.out.println("中序:"+inlist);
        //中序-非递归
        ArrayList<Integer> inlist2 = new ArrayList<>();
        inlist2 = tree.inOrder(tree.getRoot(),inlist2);
        System.out.println("中序:"+inlist2);
        //后序
        ArrayList<Integer> postlist = new ArrayList<>();
        postlist = tree.postOrder(tree.getRoot(),postlist);
        System.out.println("后续:"+postlist);
        //后序-非递归
        ArrayList<Integer> postlist2 = new ArrayList<>();
        postlist2 = tree.postOrder2(tree.getRoot(),postlist2);
        System.out.println("后续:"+postlist2);

    }
}

import java.util.ArrayList;
import java.util.LinkedList;
public class Tree {
    private BinaryTreeNode root;
    public class BinaryTreeNode{
        private BinaryTreeNode llink = null;
        private BinaryTreeNode rlink = null;
        private int val;
        private boolean isFirst;
        BinaryTreeNode(int val){
            this.val = val;
        }
    }
    void initTree(){
        root = new BinaryTreeNode(10);
        root.llink = new BinaryTreeNode(6);
        root.rlink = new BinaryTreeNode(14);
        root.llink.llink = new BinaryTreeNode(4);
        root.llink.rlink = new BinaryTreeNode(8);
        root.rlink.llink = new BinaryTreeNode(12);
        root.rlink.rlink = new BinaryTreeNode(16);

    }
    public BinaryTreeNode getRoot(){
        return root;
    }

    //前序遍历--递归
    ArrayList preOrder(BinaryTreeNode cur,ArrayList<Integer> list){
        if (cur!=null){
            list.add(cur.val);
            preOrder(cur.llink,list);
            preOrder(cur.rlink,list);
        }
        return list;
    }
    //前序遍历--非递归
    ArrayList preOrder2(BinaryTreeNode cur,ArrayList<Integer> list){
        LinkedList<BinaryTreeNode> stack = new LinkedList<>();
        while (cur!=null || !stack.isEmpty()){
            if (cur != null){
                list.add(cur.val);
                stack.push(cur);//push 在队首添加元素,add在队尾添加元素
                cur = cur.llink;
            } else{
                BinaryTreeNode node = stack.pop();//pop在队首提取元素
                cur = node.rlink;
            }
        }
        return list;
    }
    //中遍历--递归
    ArrayList inOrder(BinaryTreeNode cur,ArrayList<Integer> list){
        if(cur != null){
            inOrder(cur.llink,list);
            list.add(cur.val);
            inOrder(cur.rlink,list);
        }
        return list;
    }

    //中遍历--递归
    ArrayList inOrder2(BinaryTreeNode cur,ArrayList<Integer> list){
        LinkedList<BinaryTreeNode> stack = new LinkedList<>();
        while (cur != null || !stack.isEmpty()){
            if(cur!=null){
                stack.push(cur);
                cur = cur.llink;
            }else{
                list.add(cur.val);
                BinaryTreeNode node = stack.pop();//pop在队首提取元素
                cur = node.rlink;
            }
        }
        return list;
    }

    //后续遍历--递归
    ArrayList postOrder(BinaryTreeNode cur,ArrayList<Integer> list){
        if (cur!=null){
            postOrder(cur.llink,list);
            postOrder(cur.rlink,list);
            list.add(cur.val);
        }
        return list;
    }
    //后续遍历--递归
    ArrayList postOrder2(BinaryTreeNode cur,ArrayList<Integer> list){
        if(cur == null){
            return list;
        }
        LinkedList<BinaryTreeNode> stack = new LinkedList<>();
        BinaryTreeNode last = null;////上次访问的结点

        //把cur移到左子树的最下边
        while (cur!=null){
            stack.push(cur);
            cur = cur.llink;
        }
        while(!stack.isEmpty()){
            cur = stack.pop();
            //一个根节点被访问的前提是:无右子树或右子树已被访问过
            if (cur.rlink!=null&&cur.rlink!=last){
                stack.push(cur);//根节点再次入栈
                cur = cur.rlink;//进入右子树,且可肯定右子树一定不为空
                while(cur!=null){
                    //再走到右子树的最左边
                    stack.push(cur);
                    cur = cur.llink;
                }
            }else{
                //访问
                list.add(cur.val);
                //修改最近被访问的节点
                last = cur;
            }
        }

        return list;
    }

}

二叉树有很多特例,

  • 二叉搜索树:左节点总是小于或等于根节点,而右节点总是大于或等于根节点。
  • 堆:堆分为最大堆和最小堆
  • 红黑树:把树的节点定义成红、黑两种颜色,并确保根节点到叶节点的最长距离的长度不超过最短路径的两倍。

1.1.2. 二叉搜索树

它是一种特殊的二叉树,改善了二叉树查找效率。

  • 左节点总是小于或等于根节点。
  • 右节点总是大于或等于根节点。

1.1.3. 平衡二叉树AVL

1.1.4. 红黑树

1.1.5. B树:B+、B-


1.2. 常见面试题

1.2.1. 重建二叉树

题目中给出二叉树前序遍历和中序遍历的数据,让我们得到二叉树的结构,我们可以根据二叉树遍历特性重建二叉树。

  • 前序:根-左-右。因此可以确定,当前树的根结点。
  • 中序:左-根-右。根据前序遍历得到的根节点,可以将当前这个树分成两个树,根节点左边的都是左子树,右边的都是右子树。

import java.util.Arrays;

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length==0||in.length==0){
            return null;
        }
        //此树的根
        TreeNode root=new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if(root.val==in[i]){
                //左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1),Arrays.copyOfRange(in, 0, i));
                //右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length),Arrays.copyOfRange(in, i + 1, in.length));
            }
        }

        return root;
    }

}

1.2.2. 二叉树的下一个节点

package wang.windranger.M8;

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            return null;
        } else if (pNode.right != null) {//1.有右子树,右子树最左的节点:b>h; e>I; a>f; c>g
            TreeLinkNode rNode = pNode.right;
            //找到最左节点
            while (rNode.left != null) {
                rNode = rNode.left;
            }
            return rNode;
        } else if (pNode.next != null && pNode.next.left == pNode) {
            return pNode.next;
        } else if (pNode.next != null) {
            TreeLinkNode fNode = pNode.next;
            while (fNode.next != null && fNode.next.right == fNode) {
                fNode = fNode.next;
            }
            return fNode.next;
        }
        return null;
    }

    public TreeLinkNode genTree() {
        TreeLinkNode a = new TreeLinkNode('a');
        TreeLinkNode b = new TreeLinkNode('b');
        TreeLinkNode c = new TreeLinkNode('c');
        TreeLinkNode d = new TreeLinkNode('d');
        TreeLinkNode e = new TreeLinkNode('e');
        TreeLinkNode f = new TreeLinkNode('f');
        TreeLinkNode g = new TreeLinkNode('g');
        TreeLinkNode h = new TreeLinkNode('h');
        TreeLinkNode i = new TreeLinkNode('i');
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        b.next = a;
        c.left = f;
        c.right = g;
        c.next = a;
        d.next = b;
        e.left = h;
        e.right = i;
        e.next = b;
        f.next = c;
        g.next = c;
        h.next = e;
        i.next = e;
        return g;
    }
}

results matching ""

    No results matching ""