Java——二叉树_生成满二叉树

目录

树的相关概念 

树的表示形式

二叉树

二叉树的基本形态 

两种特殊的二叉树

二叉树的性质 

二叉树的存储

二叉树的遍历

基本操作： 

二叉树的前序遍历

获取节点个数 

叶子节点的个数 

获取第K层节点的个数​编辑

获取二叉树的高度

检测为value的值是否存在

判断一棵树是否是完全二叉树

相同的树

另一棵树的子树

平衡二叉树

 对称二叉树

二叉树的层序遍历

​编辑

---

idea统一改变量名 : shift+F6+回车 /  ctrl+R .

树的相关概念 

1.子树是不相交的；

2.除了根节点外，每个节点都有且只有一个父节点；

3.一个N节点的树有N-1个边；

   mkm

节点的度 ：一个节点含有的 子树的个数 称为该节点的度； 如上图： A 的为 6

树的度 ：一棵树中，最大的节点的度称为树的度； 如上图：树的度为 6

叶子节点或终端节点 ：度为 0 的节点称为叶节点； 如上图： B 、 C 、 H 、 I... 等节点为叶节点

双亲节点或父节点 ：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图： A 是 B 的父节点

孩子节点或子节点 ：一个节点含有的子树的根节点称为该节点的子节点； 如上图： B 是 A 的孩子节点

根结点 ：一棵树中，没有双亲结点的结点；如上图： A

节点的层次 ：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；

树的高度或深度 ：树中节点的最大层次； 如上图：树的高度为 4，最大的深度就是树的高度；

非终端节点或分支节点 ：度不为 0 的节点； 如上图： D 、 E 、 F 、 G... 等节点为分支节点

兄弟节点 ：具有相同父节点的节点互称为兄弟节点； 如上图： B 、 C 是兄弟节点

堂兄弟节点 ：双亲在同一层的节点互为堂兄弟；如上图： H 、 I 互为兄弟节点

节点的祖先 ：从根到该节点所经分支上的所有节点；如上图： A 是所有节点的祖先

子孙 ：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是 A 的子孙

森林 ：由 m （ m>=0 ）棵互不相交的树的集合称为森林

树的表示形式

class Node {

int value ; // 树中存储的数据

Node firstChild ; // 第一个孩子引用

Node nextBrother ; // 下一个兄弟引用

}

 树通常应用于文件系统管理

二叉树

一颗二叉树是一个结点的有限集合，该集合：

1.或者为空；

2.或者是由一个根节点加上两颗别称为左子树和右子树的二叉树组成； 

二叉树不存在度大于2的节点，二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

二叉树的基本形态 

两种特殊的二叉树

1. 满二叉树 : 一个二叉树，如果 每一个层的结点数都达到最大值，则这个二叉树就是满二叉树 。也就是说， 如果 一个二叉树的层数为 K ，且结点总数是2^K-1 ，则它就是满二叉树 。

2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n 个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全 二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

二叉树的性质 

1. 若规定 根节点的层数为 1 ，则一棵 非空二叉树的第 i 层上最多有 2^(i-1) (i>0) 个结点;

2. 若规定只有 根节点的二叉树的深度为 1 ，则 深度为 K 的二叉树的最大结点数是2^k - 1

(k>=0);

3. 对任何一棵二叉树 , 如果其 叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有 n0 ＝ n2 ＋ 1;

假设二叉树有N个节点，一棵二叉树，有n0（度为0的节点）,n1（度为1的节点）,n2（度为2）有N=n0+n1+n2;

一个有N个节点的二叉树，共有N-1条边；

度为0的节点产生0条边，度为1的节点有n1个 产生n1条边，度为2的节点有n2个 产生2*n2条边，N-1=n1+2*n2;

联立得n0=n2+1;

对于任意一个二叉树，叶子节点的个数比度为2的节点多一个。

4. 具有 n 个结点的完全二叉树的深度 k 为log₂(n+1)  上取整;

2^k-1=n->k=log₂(n+1) 

5. 对于具有 n 个结点的完全二叉树 ，如果按照 从上至下从左至右的顺序对所有节点从 0 开始编号 ，则对于 序号为 i 的结点有 ：

若 i>0 ， 双亲序号： (i-1)/2 ； i=0 ， i 为根节点编号 ，无双亲节点

若 2i+1<n ，左孩子序号： 2i+1 ，否则无左孩子;

若 2i+2<n ，右孩子序号： 2i+2 ，否则无右孩子。

比如：

2.在具有2n个节点的完全二叉树中，叶子节点的个数是 （n ）个

对于奇数个节点假设为 N，N=n0+n2->N=2n0-1，

二叉树的存储

顺序存储和类似于链表的链式存储 ，二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉（孩子表示法）和三叉（孩子双亲表示法）表示方式

// 孩子表示法
class Node {
 int val; // 数据域
 Node left; // 左孩子的引用
 Node right; // 右孩子的引用
}
// 孩子双亲表示法
class Node {
 int val; // 数据域
 Node left; // 左孩子的引用
 Node right; // 右孩子的引用
 Node parent; // 当前节点的根节点
}

二叉树的遍历

1.前序遍历（先根遍历）根->左子树->右子树

2.中序： 左 根 右

3.后序： 左 右 根

4.层序遍历

注意：

根据二叉树的某一个遍历是不能完全确定二叉树的。

如果只给前序和后序是不能创建二叉树的。

---

eg:

前序：ABDEHCFG；

中序：DBEHAFCG;

后序：DEHBFGCA; DHEBFGCA

基本操作： 

二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

递归的遍历思路及其子问题思路

class Solution {
     List<Integer> list=new ArrayList<>();//因为你每一次递归都会new一个新的List
     public List<Integer> preorderTraversal(TreeNode root) {
         if(root==null){
             return list;
         }      
         list.add(root.val);
         preorderTraversal(root.left);
         preorderTraversal(root.right);
         return list;
    }
}

    List<Integer> res = new ArrayList<>();
    // 判断非空
    if(null == root){
        return res;
    }
    // 使用双端队列
    Deque<TreeNode> stack = new ArrayDeque<>();
    stack.add(root);
    while(!stack.isEmpty()){
        TreeNode node = stack.removeLast();
        res.add(node.val);
        // 要先加右孩子、再加左孩子
        if(null != node.right){
            stack.add(node.right);
        }
        if(null != node.left){
            stack.add(node.left);
        }
    }
    return res;        

获取节点个数 

 

    int size(Node root){
        if(root==null){
            return 0;
        }
        return size(root.left)+size(root.right);
    }

叶子节点的个数 

 

  int getLeafNodeCount(Node root){
        if(root==null){
            return 0;
        }
        if(root.left==null&&root.right==null){
            //是叶子节点
            return 1;
        }
        return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
    }

获取第K层节点的个数

 int getKLevelNodeCount(Node root,int k){
       if(root==null||k<=0){//自己写的时候忘了这个了
           return 0;
       }
        if(k==1){
            return 1;
        }
        return getKLevelNodeCount(root.right,k-1)+getKLevelNodeCount(root.left,k-1);
 }

获取二叉树的高度

 int getHeight(Node root){
        if(root==null){
            return 0;
        }
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
        //return root == null ? 0 : Math.max(getHeight(root.left),getHeight(root.right))+1;
    }

检测为value的值是否存在

先看根节点是不是要找的value，否则遍历整个二叉树。

    //先找根，然后左，然后右边找
    Node find(Node root,char val){
        if(root==null){
            return null;
        }
        if(root.val==val){
            return root;
        }
        Node ret = find(root.left,val);
        if(ret!=null){
            return ret;
        }
        ret=find(root.right,val);
        if(ret!=null){
            return ret;
        }
        return null;
    }

判断一棵树是否是完全二叉树

使用非递归的队列解决：

先把根节点放入队列，弹出栈顶元素放入cur；

当cur不为空的时候，放入cur的左右节点 ，若无放入null ......

当cur为空的时候，如果队列里面的值全是null，则是完全二叉树。 

    boolean isCompleteTree(Node root){
        if(root==null) return true;//空树就是完全二叉树；
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node cur=queue.poll();
            if(cur!=null){
                queue.offer(root.left);
                queue.offer(root.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            Node top=queue.peek();
            if(top!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }

相同的树

节点的值相同，树的结构相同。

 //如果一个为空，一个不为空，结构不相同

 //p=null,q==null,pq是相同的树

 //p,q都不为空，但是p.val!=q.val,pq不是相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null||p!=null&&q==null) return false;
        if(p==null&&q==null){
            return true;
        }
        if(p.val!=q.val){
            return false;
        }
        //p!=null&&q!=null&&p.val==q.val
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

另一棵树的子树

 //先判断两棵树是不是相同的树；
 //如果不是。那麽分别判断 subRoot是不是root的左子树或者右子树；
 //是否相同？ 

 
class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==null) return false;
        if(isSameTree(root,subRoot)) return true;//本身是不是相同的树
        if(isSubtree(root.left,subRoot)) return true;
        if(isSubtree(root.right,subRoot)) return true;
        return false;
    }
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q!=null||p!=null&&q==null) return false;
        if(p==null&&q==null) return true;
        if(p.val!=q.val) return false;
        //p!=null&&q!=null&&p.val==q.val
        return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
    }
}

平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

如果是平衡二叉树，那么他的每一个子树都是平衡二叉树

 //一个二叉树要是平衡二叉树，那么他的每一个子树都应该是平衡二叉树
 //root左树的高度-右树的高度<=1;
 //root的左树是平衡，右树也是

 
 
class Solution {
    //求高度的时间复杂度：O（N）；
    public int height(TreeNode root){
        if(root==null) return 0;
        return Math.max(height(root.left),height(root.right))+1;
    }
    //O(N^2)
 
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;
        int left=height(root.left);
        int right=height(root.right);
        return Math.abs(left-right)<=1&&isBalanced(root.left)&&isBalanced(root.right)?true:false;
    }
}

---