【数据结构与算法】—— 二叉树

目录

一、树

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）二叉树的度 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 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) {
        //平衡二叉树：每棵子树的高度差都要