【数据结构与算法】—

一、树

1、初识树

2、树的一些概念

3、树的表示形式

二、二叉树

1、初识二叉树

2、两种特殊的二叉树

3、二叉树的性质

4、二叉树的遍历

5、实现一棵二叉树

6、二叉树题目（没代码的后面会给补上）

一、树

1、初识树

（1）根节点没有前驱。

（2）子树的根节点只有一个前驱，可以有0个或多个后继。

（3）每个子树都是不相交的，子树之间不能有交集。

（4）N个结点有N-1条边

2、树的一些概念

1、结点的度：这个结点有几个子树，度就为几

2、树的度：所有结点度的最大值就是树的度

3、根结点：没有前驱的结点

4、叶子结点或终端结点：没有后继的结点（没有子树），即度为0的结点

5、分支结点或非终端结点：有后继的结点（有子树），即度不为0的结点

6、双亲结点或父结点：结点的前驱就是该结点的父结点

7、孩子结点或子结点：结点的后继就是该结点的子结点

8、兄弟结点：具有相同父结点的结点互为兄弟结点

9、堂兄弟结点：父结点在同一层的结点互为堂兄弟结点

10、结点的祖先：从根结点到该结点一路上经过的所有结点都是该结点的祖先，如：根结点是除自身外所有结点的祖先

11、子孙：该结点后面的所有结点都是该结点的子孙，如：除根结点外所有结点都是根结点的子孙

12、结点的层次：根为第1层，以此类推

13、深度：该结点的层次就是深度

14、树的高度：树中结点的最大层次就是树的高度

15、森林：由m（m>=0）棵互不相交的树组成的集合称为森林，空树也叫森林

3、树的表示形式

树可以有：双亲表示法，孩子表示法，孩子双亲表示法，孩子兄弟表示法等等

二、二叉树

1、初识二叉树

（1）二叉树是树

（2）二叉树的每个根结点都只有两棵子树，分别为左子树和右子树

（3）二叉树也可以是空树

（4）二叉树的度 <=2，所以二叉树的结点个数 = 度为0的结点个数+度为1的结点个数+度为2的结点个数

2、两种特殊的二叉树

（1）满二叉树

除叶子结点外，结点的度都为2，结点总数为：(2^k)-1，k为树的高度

（2）完全二叉树

从上到下，从左到右，中间不少结点。

满二叉树是特殊的完全二叉树。

完全二叉树中，度为1的结点个数要么为0，要么为1 —— 结点总数是偶数时，度为1的结点个数为 1，结点总数是奇数时，度为1的结点个数为 0

3、二叉树的性质

1、二叉树的第 k 层，最多有 2^(k-1) 个结点（空树除外）

2、深度为 k 的二叉树，最多有(2^k)-1个结点

3、任意一棵二叉树，叶子结点的个数比度为2的结点的个数多 1

4、n个结点的完全二叉树，深度k为：(2^k) -1= n，k为 log以2为底n+1的对数，向上取整

5、完全二叉树，

若父结点下标为 i，则左孩子下标为：2^i+1，右孩子下标为：2^i+2

若子结点下标为 i，则父结点下标为：i-1/2

题目：

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B、 200 ）199+1

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（A、n）2n = n0+1+n0-1

3.一个具有767个节点的完全二叉树，其叶子节点个数为（B、384）767 = n0+0+n0-1

4、二叉树的遍历

前序遍历：根，左子树，右子树

中序遍历：左子树，根，右子树

后序遍历：左子树，右子树，根

层序遍历：从上到下，从左到右

如：写出下面这棵二叉树的前序遍历，中序遍历，后序遍历，层序遍历的结果

前序遍历：A B D E H C F G

中序遍历：D B E H A F C G

后序遍历：D H E B F G C A

层序遍历：A B C D E F G H

题目：

1、设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为(D)

A: adbce B: decab C: debac D: abcde

后序遍历，从后往前，每一个结点都是根结点。拿着根结点，去中序遍历里看，根结点的左边属于左子树的结点，根结点的右边属于右子树的结点。

如，后序遍历从后往前第一个结点就是整棵树的根结点 a，然后看中序遍历，则，b 属于左子树的结点，dce 属于右子树的结点。然后再看后序遍历从后往前第二个结点，以此类推。

由此题引出两个问题，

问题一：如果只给一个遍历，能否创建一棵二叉树？

不能。因为有可能存在两棵不同的树，某一个遍历是一样的。

问题二：如果只给前序遍历和后序遍历，能否创建一棵二叉树？

不能。前序遍历和后序遍历都是只能确定根的位置，但不能确定左子树或右子树。

5、实现一棵二叉树

二叉树的存储结构（物理结构）有：顺序存储和链式存储

这里我们使用孩子表示法来实现一个链式存储结构的二叉树。

1、前序遍历 2、中序遍历 3、后序遍历
4、获取树中结点的个数 5、获取叶子结点的个数 6、获取第 k层 结点的个数
7、获取二叉树的高度
8、获取第k层的所有结点：有点 带返回值的前序遍历 和 获取第 k层 结点的个数 的结合版
9、找到值为value的元素
10、层序遍历：和层序遍历相关的想到用 队列，用队列会比较方便
11、判断这棵树是不是完全二叉树：用 队列

public class MyBinaryTree {
    static class TreeNode{
        public char val;
        public TreeNode leftTree;//存储左子树的引用
        public TreeNode rightTree;//存储右子树的引用
        public TreeNode(char val){
            this.val = val;
        }
    }
    //创建一棵树
    public TreeNode createTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.leftTree = B;
        A.rightTree = C;
        B.leftTree = D;
        B.rightTree = E;
        C.leftTree = F;
        C.rightTree = G;
        E.rightTree = H;
        return A;
    }
    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val+" ");
        preOrder(root.leftTree);
        preOrder(root.rightTree);
    }
    //带返回值
    public List<Character> preorderTraversal(TreeNode root) {
        //子问题思路：先放根，然后放左子树，然后放右子树
        List<Character> list = new ArrayList<>();
        //递归的终止条件
        if(root == null){
            return list;
        }
        list.add(root.val);
        list.addAll(preorderTraversal(root.leftTree));
        list.addAll(preorderTraversal(root.rightTree));
        return list;
    }
    //中序遍历
    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.leftTree);
        System.out.print(root.val+" ");
        inOrder(root.rightTree);
    }
    //后序遍历
    public void postOrder(TreeNode root){
        if(root == null){
            return;
        }
        postOrder(root.leftTree);
        postOrder(root.rightTree);
        System.out.print(root.val+" ");
    }
    //获取树中结点的个数
    public int size(TreeNode root){
        //左子树结点的个数+右子树结点的个数+1
        //递归的终止条件
        if(root == null){
            return 0;
        }
        return size(root.leftTree)+size(root.rightTree)+1;
    }
    //获取叶子结点的个数
    public int getLeafNodeCount(TreeNode root){
        //左子树叶子结点的个数+右子树叶子结点的个数
        if(root == null){
            return 0;
        }
        //满足下面条件的就是叶子结点,递归的终止条件
        if(root.leftTree == null && root.rightTree == null){
            return 1;
        }
        return getLeafNodeCount(root.leftTree) + getLeafNodeCount(root.rightTree);
    }
    //获取第 k层 结点的个数
    public int getKLevelNodeCount(TreeNode root,int k){
        //第k层结点的个数 = 左子树第k-1层结点的个数+右子树第k-1层结点的个数
        if(k <= 0){
            throw new KWrongFulException("k不合法异常");
        }
        //如果k大于树的高度，k还没减到0，root先变成null，返回0
        //下面两个都算循环的终止条件
        if(root == null){
            return 0;
        }
        if(k == 1){
            return 1;
        }
        return getKLevelNodeCount(root.leftTree,k-1)
                +getKLevelNodeCount(root.rightTree,k-1);
    }
    //获取二叉树的高度
    public int getHeight(TreeNode root){
        //左子树的高度，右子树的高度的最大值 +1
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.leftTree);
        int rightHeight = getHeight(root.rightTree);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }
    //获取第 k 层的所有结点
    //有点像 带返回值的前序遍历 和 获取第 k层 结点的个数 的结合
    public List<Character> KLevel(TreeNode root,int k){
        List<Character> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        //把 第 k 层的每一个结点都 add 进 list，返回给父结点
        if(k == 1){
            list.add(root.val);
            return list;
        }
        //父结点接收到两个子结点返回的 list，add到自己的list里
        list.addAll(KLevel(root.leftTree,k-1));
        list.addAll(KLevel(root.rightTree,k-1));
        //然后返回给他的父结点，于是层层递进，最后根结点的list里 放的就是 第k层 的所有结点
        return list;
    }
    //找到值为value的元素
    public TreeNode find(TreeNode root,char val){
        //先找根，然后找左子树，然后找右子树，找到就返回，找不到返回null
        //下面两个都是递归的终止条件
        if(root == null){
            return null;
        }
        if(root.val == val){
            return root;
        }
        TreeNode ret1 = find(root.leftTree,val);
        //如果 ret1 里面不是空，说明找到了
        //如果 ret1 里面是空，说明没找到
        if (ret1 != null){
            return ret1;
        }
        TreeNode ret2 = find(root.rightTree,val);
        if (ret2 != null){
            return ret2;
        }
        return null;
    }
    //层序遍历：用到队列，先进先出
    //层序遍历不用递归比较方便，本来就是按顺序（从上到下，从左到右）输出的呀，
    // 不像前序中序和后序遍历，必须得递归
    public void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode ret = queue.poll();
            System.out.print(ret+" ");
            if(ret.leftTree != null){
                queue.offer(ret.leftTree);
            }
            if(ret.leftTree != null){
                queue.offer(ret.rightTree);
            }
        }
    }
    //有返回值的层序遍历：用到队列比较方便
    //难点在如何确定每一层，这里我们用到了队列中的size
    //每一轮都要定义一个size
    public List<List<Character>> levelOrderTraversal(TreeNode root){
        List<List<Character>> tmp = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return tmp;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Character> list = new ArrayList<>();
            while(size > 0) {
                TreeNode ret = queue.poll();
                size--;
                list.add(ret.val);
                if (ret.leftTree != null) {
                    queue.offer(ret.leftTree);
                }
                if (ret.rightTree != null) {
                    queue.offer(ret.rightTree);
                }
            }
            tmp.add(list);
        }
        return tmp;
    }
    //判断这棵树是不是完全二叉树：用队列
    public boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return true;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode ret = queue.peek();
            if(ret == null){
                break;
            }
            queue.poll();
            queue.offer(ret.leftTree);
            queue.offer(ret.rightTree);
        }
        //走到这，队列里要么都是null，要么除了null还有结点，后者说明不是完全二叉树
        while(!queue.isEmpty()){
            TreeNode ret = queue.poll();
            if(ret != null){
                return false;
            }
        }
        return true;
    }
}

6、二叉树题目（没代码的后面会给补上）

1、判断两棵树相不相等
2、判断其中一棵树是不是另一棵树的子树
3、翻转二叉树
4、判断是不是平衡二叉树
5、判断两棵二叉树是不是镜像对称
6、判断是不是轴对称二叉树
7、二叉树的层序遍历
8、二叉树的构建和遍历
9、给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
10、二叉搜索树转换成排序双向链表
11、二叉树前序非递归遍历实现
12、二叉树中序非递归遍历实现
13、二叉树后序非递归遍历实现
14、根据一棵树的前序遍历与中序遍历构造二叉树
15、根据一棵树的中序遍历与后序遍历构造二叉树
16、二叉树创建字符串

（1）判断两棵树是否相同链接

//时间复杂度：O(min(m,n))，其中 m和n 分别是两个二叉树的结点数
public boolean isSameTree(TreeNode p, TreeNode q) {
        //先判断根一样不，再判断左子树一样不，再判断右子树一样不，只有全一样(结构和值都一样)，才返回true
        //如果都是空树
        if(p == null && q == null){
            return true;
        }
        //如果一个是空树，一个不是
        if((p == null && q != null) || (p != null && q == null)){
            return false;
        }
        //走到这，则两个都不是空树
        //值不相等
        if(p.val != q.val){
            return false;
        }
        //走到这，既不是空树，根的值也相等
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}

（2）判断其中一棵树是不是另一棵树的子树链接


    /**
     * 2、判断其中一棵树是不是另一棵树的子树
     * 时间复杂度：O(m*n)，其中 m和n 分别是两个二叉树的结点数
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //题目中已经给出了：两棵树都不是空树
        //如果一直没有匹配，root就会一直root.left，root会为空
        if(root == null || subRoot == null){
            return false;
        }
        //先判断subRoot是否和root相等，
        if(isSameTree(root,subRoot)) return true;
        //再判断subRoot是否是root的左子树的子树
        if(isSubtree(root.left,subRoot)) return true;
        //再判断subroot是否是root的右子树的子树
        if(isSubtree(root.right,subRoot)) return true;
        return false;
    }
   public boolean isSameTree(TreeNode p, TreeNode q) {
        //先判断根一样不，再判断左子树一样不，再判断右子树一样不，只有全一样(结构和值都一样)，才返回true
        //如果都是空树
        if(p == null && q == null){
            return true;
        }
        //如果一个是空树，一个不是
        if((p == null && q != null) || (p != null && q == null)){
            return false;
        }
        //走到这，则两个都不是空树
        //值不相等
        if(p.val != q.val){
            return false;
        }
        //走到这，既不是空树，根的值也相等
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

（3）翻转二叉树链接

public TreeNode invertTree(TreeNode root) {
        //先翻转根结点的左子树和右子树，再翻转左子树的左子树和右子树，再翻转右子树的左子树和右子树
        if(root == null){
            return null;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
}

（4）判断是不是平衡二叉树链接

//判断是不是平衡二叉树，时间复杂度O(n)
    public boolean isBalanced(TreeNode root) {
        //平衡二叉树：每棵子树的高度差都要 <=1

        if(root == null){
            return true;
        }
        int ret = height(root);
        if(ret == -1){
            return false;
        }
        return true;
    }
    //求二叉树的高度，时间复杂度是O(n)
    //求根结点高度的时候，其实已经求了所有结点的高度，如果发现左树右树高度差大于1，说明已经不平衡了，就返回-1
    //否则就返回左树右树高度最大值+1
    //所以，我们需要在每次获得左树和右树高度的时候，都接收判断一下，如果发现接收到的是-1，说明已经出现了不平衡
    //如果一直没有接收到-1，说明这个二叉树的每棵子树都是平衡的，所以这棵二叉树是高度平衡的二叉树。
    //求二叉树的高度
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }
        //求左子树的高度
        int leftH = height(root.left);
        if(leftH == -1){
            return -1;
        }
        //求右子树的高度
        int rightH = height(root.right);
        if(rightH == -1){
            return -1;
        }
        //如果左右子树的高度差 <= 1，返回左右子树高度的最大值+1
        //如果左右子树的高度差 > 1，返回-1，说明已经出现不平衡了
        if(Math.abs(leftH - rightH) <= 1){
            return Math.max(leftH,rightH) + 1;
        }else{
            return -1;
        }
    }

（5）判断两棵树是不是镜像对称

public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){
        //如果两个都是空树
        if(leftTree == null && rightTree == null){
            return true;
        }
        //如果一个是空树一个不是
        if((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)){
            return false;
        }
        //到这，两个都不是空树
        if(leftTree.val != rightTree.val){
            return false;
        }
        //到这，两个都不是空树，且根的值相同
        return isMirrorSymmetry(leftTree.left,rightTree.right) &&
                isMirrorSymmetry(leftTree.right,rightTree.left);
}

（6）判断是不是轴对称二叉树链接

public boolean isSymmetric(TreeNode root) {
        
        if(root == null){
            return true;
        }
        //从第二层开始，比较左子树和右子树是否是镜像的
        return isMirrorSymmetry(root.left,root.right);
    }
    //先比较根是否是镜像的，再比较子树是否是镜像的
     public boolean isMirrorSymmetry(TreeNode leftTree,TreeNode rightTree){
        //如果两个都是空树
        if(leftTree == null && rightTree == null){
            return true;
        }
        //如果一个是空树一个不是
        if((leftTree == null && rightTree != null) || (leftTree != null && rightTree == null)){
            return false;
        }
        //到这，两个都不是空树
        if(leftTree.val != rightTree.val){
            return false;
        }
        //到这，两个都不是空树，且根的值相同
        return isMirrorSymmetry(leftTree.left,rightTree.right) &&
                isMirrorSymmetry(leftTree.right,rightTree.left);
    }

（7）二叉树的层序遍历链接

//有返回值的层序遍历：用到队列比较方便
//难点在如何确定每一层，这里我们用到了队列中的size
//每一轮都要定义一个size
 public List<List<Integer>> levelOrder(TreeNode root) {
       List<List<Integer>> tmp = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null){
            return tmp;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size > 0) {
                TreeNode ret = queue.poll();
                size--;
                list.add(ret.val);
                if (ret.left != null) {
                    queue.offer(ret.left);
                }
                if (ret.right != null) {
                    queue.offer(ret.right);
                }
            }
            tmp.add(list);
        }
        return tmp;
}

（8）二叉树的构建和遍历链接

public class Main {
    static class TreeNode{
        public char val;
        public TreeNode leftTree;//存储左子树的引用
        public TreeNode rightTree;//存储右子树的引用
        public TreeNode(char val){
            this.val = val;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) { 
            String str = scanner.nextLine();//str里存的就是读入的字符串

           //首先遍历字符串，拿到字符串中的每个元素，
           //并创建结点，通过前序遍历构造一棵二叉树
           TreeNode root = createTree(str);
           //然后再中序遍历输出
           inOrder(root);
        }
    }
    //通过前序遍历构造二叉树
    public static int i = 0;
    public static TreeNode createTree(String str){
        TreeNode root = null;
        //通过i拿到字符串中的每个字符
        char ch = str.charAt(i);
        i++;
        if(ch == '#'){
            return null;
        }
        //把拿到的元素创建成结点
        root = new TreeNode(ch);
        root.leftTree = createTree(str);
        root.rightTree = createTree(str);
        return root;   
    }
    //中序遍历输出
    public static void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.leftTree);
        System.out.print(root.val+" ");
        inOrder(root.rightTree);
    }
}

（9）给定一个二叉树, 找到该树中两个指定节点的最近公共祖先链接

 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        // p 和 q 其中有一个是root
        if(p == root || q == root){
            return root;
        }
        // p 和 q 分别在 root 的两侧
        // p 和 q 都在 root 的左侧 或 root 的右侧
        TreeNode ret1 = lowestCommonAncestor(root.left,p,q);
        TreeNode ret2 = lowestCommonAncestor(root.right,p,q);
        if(ret1 != null && ret2 != null){
            return root;
        }else if(ret1 != null){
            return ret1;
        }else if(ret2 != null){
            return ret2;
        }else{
            return null;
        }
}

（10）二叉搜索树转换成排序双向链表链接

public TreeNode convert(TreeNode pRootOfTree) {
        //二叉搜索树：根左边的比根小，根右边的比根大
        //中序遍历二叉搜索树是有序的，是从小到大的
        //所以，转换成排序的双向链表，采用中序遍历的方法
        if(pRootOfTree == null){
            return null;
        }
        convertChild(pRootOfTree);
        TreeNode head = pRootOfTree;
        //链表的头就是二叉搜素树最左边的那个结点
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
    public TreeNode prev = null;
    public void convertChild(TreeNode pRoot){
        if(pRoot == null){
            return;
        }
        convertChild(pRoot.left);

        if(prev != null){
            prev.right = pRoot;
        }
        pRoot.left = prev;
        prev = pRoot;
        convertChild(pRoot.right);
 }

（11）二叉树前序非递归遍历实现链接

public TreeNode cur = null;
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        //用到栈
        //前序遍历：根，左，右。往左走，一直入栈，只有这个节点没用了，才能出栈。
        if(root == null){
            return list;
        }
        cur = root;
        while(cur != null || !stack.empty()){
            while(cur != null){
                stack.push(cur);
                list.add(cur.val);
                cur = cur.left;
            }
            //cur 等于空，说明cur的左走完了，此时栈顶元素就是cur
            //根和左走完了，此时才能弹出栈顶元素（因为直到这时栈顶元素才没用了）
            cur = stack.pop();
            cur = cur.right;
        }
        return list;
 }

（12）二叉树中序非递归遍历实现链接

（13）二叉树后序非递归遍历实现链接

（14）根据一棵树的前序遍历与中序遍历构造二叉树链接

（15）根据一棵树的中序遍历与后序遍历构造二叉树链接

（16）二叉树创建字符串链接