数据结构--二叉树详解

一，概念

1，结点的度：一个结点含有子树的个数称为该结点的度

2， 树的度：一棵树中，所有结点度的最大值称为树的度；

3，叶子结点或终端结点：度为0的结点称为叶结点； 

4，双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点,

5，孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点；

6，根结点：一棵树中，没有双亲结点的结点；

7，树的高度或深度：树中结点的最大层次；

二，二叉树的分类

1，满二叉树

每层的结点数都达到最大值，则这棵二叉树就是满二叉树。满二叉树是一种特殊的完全二叉树

2，完全二叉树

从上到下，从左到右一次排列

三，二叉树的基本性

1，若规定根节点的层数为1，则一颗非空二叉树的第i层上最多有2^i-1个节点

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

3，对任意一颗二叉树，如果其叶节点的个数为n0，度为2的非叶节点个数为n2，则有n0=n2+1

4,具有n个节点的完全二叉树的深度为log2（n+1）上取整

5，对于具有n个节点的完全二叉树，如果按照从上至下从左至右所有节点从0开始编号，如果父节点的下标为i，则孩子节点为2i+1，2i+2。但是如果2i+1>=n,左无左孩子，若2i+2>=n，否则没有右孩子

6，知道孩子的下标，父节点的下标为（i-1）/2,如果i=0，则无则无双亲节点 

7, 二叉树存储分为顺序存储，和链式储存，链式储存是通过一个一个节点的引用起来的。

以链式储存为例：

例如：

public class BinaryTree {
    public TreeNode root;
    static class TreeNode{
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }
}

四，二叉树的遍历

分类：

二叉树的遍历分为大体四种：前序遍历，中序遍历，后序遍历，层序遍历。前三种遍历的方式又可以写为递归的形式和非递归的形式

前序遍历：

二叉树中的每一棵树都要符合先遍历根，然后遍历左树，最后是右树（根左右）

递归：

如果根为空，直接return。先打印根，然后打印左树，最后是右树

public void preOrder(TreeNode root){
    if (root==null){
        return;
    }
    System.out.print(root.val+" ");
    preOrder(root.left);
    preOrder(root.right);
}

非递归：

法一：

借助栈。先将根放到栈中，然后弹出，记录下来（赋值给cur），并打印。然后先将cur的右根放到栈中，再放cur的左根。在再弹出栈顶元素也就是左根，重复上述步骤（记录下来，并打印，将其右左树再放到栈中）

注意：

1，一定是先放右树，再放左树

2，将左右树放到栈中时要分别判断左右树是否为空，如果为空则不进栈

public void preOrder2(TreeNode root){
    Stack<TreeNode> stack=new Stack<>();
    stack.push(root);
    TreeNode cur=stack.pop();
    stack.push(cur.right);
    stack.push(cur.left);
    System.out.print(cur.val+" ");
    while (!stack.isEmpty()){
        cur=stack.pop();
        if (cur.right!=null){
            stack.push(cur.right);
        }
        if (cur.left!=null) {
            stack.push(cur.left);
        }
        System.out.print(cur.val+" ");
    }
}

法二：

借助栈。将root赋值给cur，进入两次循环，内循环是找到cur最左边的树并把过程中经过的每一个节点放到栈中，直到找到null。因为这里是前序遍历，所以每找到一个节点就要打印出来。当找到null时，走出循环。这时弹出栈顶元素，cur等于栈顶元素的右树（通过前面步骤，已知栈顶元素的左树为空）。然后cur开始外循环。由于内循环的条件是cur!=null，所以当右树为空时，不进入内循环，直接再次弹出栈顶元素。如果不为空是，则进入内循环，寻找它的左树……

public void preOrder3(TreeNode root){
    Stack<TreeNode> stack=new Stack<>();
    TreeNode cur=root;
    while (cur!=null||!stack.isEmpty()){
        while (cur!=null){
            stack.push(cur);
            System.out.print(cur.val+" ");
            cur=cur.left;
        }
        TreeNode old=stack.pop();
        cur=old.right;
    }
    System.out.println();
}

中序遍历：

二叉树中的每一棵树都要符合先遍历左树，然后遍历根，最后是右树（左根右）

递归：

public void midOrder(TreeNode root){
    if (root==null){
        return;
    }
    midOrder(root.left);
    System.out.print(root.val+" ");
    midOrder(root.right);

非递归：

与前序遍历非递归的法二原理相似，只是根打印的位置不相同，所以在走内循环时不打印节点，走完后，在打印，这样保证先打印的是左树。

public void midOrder2(TreeNode root){
    Stack<TreeNode>stack=new Stack<>();
    TreeNode cur=root;
    while (cur!=null||!stack.isEmpty()){
        while (cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        TreeNode old=stack.pop();
        System.out.print(old.val+" ");
        cur=old.right;
    }
    System.out.println();
}

后序遍历：

二叉树中的每一棵树都要符合先遍历左树，然后遍历右树，最后是根（左右根）

递归：

public void postOrder(TreeNode root){
    if (root==null){
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val+" ");
}

非递归：

与中序遍历非递归思路相似，只是根打印的位置不相同，所以在走内循环，及走完内循环后均不打印，完成内循环后，直接判断栈顶元素右树是否为空，如果为空，就可以弹出栈顶元素，并且打印。但是如果不为空，就要先走右树（因为后序遍历的顺序是左右根，已知没有左树，所以要先打印右树）。

注意：要把每次遍历完的节点储存一下。因为每次内循环走完左树为空时，到判断栈顶元素A右树时（在右树不为空的情况下），这时会开始遍历右树，当遍历完右树后，又会回到这个起点（判断该栈顶元素A是否有右树），这时就会进入死循环，所以这里的判断条件进行丰富，即栈顶元素既有右树且之前没有遍历过【注意栈顶元素A,只是举了一个例子，方便理解！】

public void postOrder2(TreeNode root){
    Stack<TreeNode>stack=new Stack<>();
    TreeNode cur=root;
    TreeNode prev=null;
    while (cur!=null||!stack.isEmpty()){
        while (cur!=null){
            stack.push(cur);
            cur=cur.left;
        }
        TreeNode old=stack.peek();
        if (old.right==null||prev==old.right){
            stack.pop();
            System.out.print(old.val+" ");
            prev=old;
        }else {
            cur=old.right;

        }
    }
    System.out.println();
}

层序遍历：

一层一层的进行遍历

这里我们用到了队列，先把根放进去，弹出时，记录下来（赋值到ret中）并打印，然后根据ret，将ret的左树和右树也放到队列里面，重复上述步骤（弹出，记录下来，并打印，将其左右树再放到队列中），循环上述步骤，直到队列为空，则遍历完成。需要注意的是：将左右树放到队列中时要分别判断左右树是否为空，如果为空则不进队列，只有不为空时，才能放入。

法一：

public void levelOrder(TreeNode root){
    Queue<TreeNode> queue=new LinkedList<>();
    if (root==null){
        return;
    }
    queue.offer(root);
    while (!queue.isEmpty()){
        TreeNode ret=queue.peek();
        if (ret.left!=null){
            queue.offer(ret.left);
        }
        if (ret.right!=null){
            queue.offer(ret.right);
        }
        System.out.print(queue.poll().val+" ");
    }
    System.out.println();
}

法二：

这种方法是将每一层的节点放到一个链表中，然后将每一层的的链表放到一个“大的链表”中。先将根放到队列中，计算这一层的大小size，则决定着这一层的的链表的大小。然后循环size次，从而将这一层的每个元素均放到该层链表中。然后将这一层的每个元素的左右树再放到队列中，重复上述步骤，直到链表为空。

public List<List<Character>> levelOrder2(TreeNode root){
    List<List<Character>> ret=new LinkedList<>();
    if (root==null){
        return ret;
    }
    Queue<TreeNode> queue=new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()){
        int size= queue.size();
        List<Character> list=new LinkedList<>();
        while (size>0){
            TreeNode node=queue.peek();
            if (node.left!=null){
                queue.offer(node.left);
            }
            if (node.right!=null) {
                queue.offer(node.right);
            }
            list.add(queue.poll().val);
            size--;
        }
        ret.add(list);
    }
    return ret;

}

五，求二叉树的简单性质

1，一棵树的节点个数

法一：

我们遍历二叉树时，遍历了每个节点，所以只需要将遍历中打印的步骤改为count++，就可以得到节点的个数

public static  int sizeNode;
public void size2(TreeNode root) {
    if (root==null){
        return ;
    }
    sizeNode++;
    size2(root.left);
    size2(root.right);
}

法二：

一棵树的节点个数=这棵树的左子树的节点个数+右子树的节点个数+1.（这个1是根节点）

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

2，求叶子节点的个数

法一：

叶子结点的性质是左子树和右子树均为null，所以当遇到这样的节点时，返回1。整颗树的叶子结点个数=左子树叶子节点的个数+右子树叶子结点个数

public int getLeafNodeCount(TreeNode root){
    if (root==null){
      return 0;
    }
   if (root.left==null&&root.right==null){
       return 1;
   }
   return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);
}

法二：

也可以遍历二叉树，找到左子树和右子树均为null的节点，count++.

public static  int sizeLeafNode;
public void getLeafNodeCount2(TreeNode root){
    if (root==null){
        return ;
    }
    if (root.left==null&&root.right==null){
       sizeLeafNode++;
    }
    getLeafNodeCount2(root.left);
    getLeafNodeCount2(root.right);

}

3，获取k层节点的个数

我们每递归一层时，让参数k-1，这样当k==1时，就是k层的节点，我们只需要返回1，整颗树的k层结点个数=左子树的k层节点的个数+右子树的k层结点个数

public int getKLevelNodeCount(TreeNode root,int k){
   if (root==null ){
       return 0;
   }
   if (k==1){
       return 1;
   }
   return getKLevelNodeCount(root.left,k-1)
           +getKLevelNodeCount(root.right,k-1);
}

4，树的高度

树的高度=左子树高度和右子树高度的最大值+1

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

5，找到某个节点

如果找到该节点，返回该节点的根。左子树递归完后，如果找到了，直接返回，如果没有找到，再右子树递归，这样可以提高效率

public TreeNode find(TreeNode root,char val){
    if (root==null){
        return null;
    }
    if (root.val==val){
        return root;
    }
    TreeNode ret=find(root.left,val);
    if (ret!=null){
        return ret;
    }
    ret=find(root.right,val);
    if (ret!=null){
        return ret;
    }else {
        return null;
    }
}

六，简单应用

1，检查两棵树是否相同

如果两棵树均为空，则相同。因为我们需要用递归来实现，所以写的时候我们用if语句（两棵树一定不相同的条件）来快速排除

排除条件

（1）如果一棵树为空，一棵树不为空，直接返回false

（2）如果对应节点的值不一样，直接返回false

当两棵树对应的左树与右树均相同，则两棵树相同

public boolean isSameTree(TreeNode p,TreeNode q){
    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，第二棵树是否是第一棵树的子树

我们先找到第一棵树是否有节点与第二棵树的根结点一致，如果有相同的节点，调用方法一，看两棵树是否相同。我们分别从左树和右树中寻找，只要有一边找到了，就说明第二棵树是第一棵树的子树

public boolean isSubTree(TreeNode root,TreeNode subRoot){
    if (root==null&&subRoot!=null){
        return false;
    }
    if (root.val== subRoot.val){
       return isSameTree(root,subRoot);
    }
    return isSubTree(root.left,subRoot)
            ||isSubTree(root.right,subRoot);
}

3，翻转二叉树

当根为空，或者根的左右树均为空，则直接返回根。如果不是，交换左右树

private void swap(TreeNode root){
    TreeNode tmp=root.left;
    root.left=root.right;
    root.right=tmp;
}
public TreeNode reverseTree(TreeNode root){
    if (root==null||root.left==null&&root.right==null){
        return root;
    }
    swap(root);
    reverseTree(root.left);
    reverseTree(root.right);
    return root;
}

4，判断一棵二叉树是否是平衡二叉树

即：所有节点的高度差小于等于一

法一：

算左右树的高度，如果差的绝对值小于1，且左树和右树每一棵子树的左右树的高度差的绝对值小于1，则是平衡二叉树

public boolean isBalanced(TreeNode root){
    if (root==null){
        return true;
    }
    int leftHeight=getHeight(root.left);
    int rightHeight=getHeight(root.right);
    return Math.abs(leftHeight-rightHeight)<=1
            &&isBalanced(root.left)&&isBalanced(root.right);
}

法二（优化）：

重写计算书的高度的方法，如果树的左右树的高度差小于1，则返回该树的高度，如果高度差大于1，返回-1，最后看树的高度是否大于0，如果大于0，则说明每一棵树的左右子树的高度差均小于1，如果小于0，则说明有树的左右子树的高度差均大于1，则不是平衡二叉树

public int getHeight2(TreeNode root){
   if (root==null){
       return 0;
   }
   int left=getHeight2(root.left);
   if (left<0){
       return -1;
   }
   int right=getHeight2(root.right);
   if (right<0){
       return -1;
   }
   if (Math.abs(left-right)<=1){
       return Math.max(left,right)+1;
   }else {
       return -1;
   }
}
public boolean isBalanced2(TreeNode root){
    if (root==null){
        return true;
    }
    return getHeight2(root)>0;

}

5，对称二叉树

如果根为空或者根的左树右树均为空，则是对称二叉树。

（1）如果跟的左树，右树一个为空一个不为空，则不是对称二叉树

（2）如果根的左树和右树的值不一样，则不是对称二叉树

然后判断左右，这两棵树是否镜面对称，我们再写一个子方法。

（1）如果这两棵树的左右树均为空，则是对称二叉树

（2）如果一棵树的左树，与一棵树的右树，一颗为空，一颗不为空，则不是对称二叉树

（3）如果一棵树的右树，与一棵树的左树，一颗为空，一颗不为空，则不是对称二叉树

（4）如果一棵树的左树，与另一棵树的右树的值不相同，或者一棵树的右树，与一棵树的左树的值不相同，则不是对称二叉树

private boolean isSymmetricChild(TreeNode p,TreeNode q){
    if (p.left==null&&p.right==null&&q.left==null&&q.right==null){
        return true;
    }
    if (p.left!=null&&q.right==null
            ||p.left==null&&q.right!=null
            ||p.right!=null&&q.left==null
            ||p.right==null&&q.left!=null){
        return false;
    }
    if (p.left.val!=q.right.val
            ||p.right.val!=q.left.val){
        return false;
    }
    return isSymmetricChild(p.left,q.right)
            &&isSymmetricChild(p.right,q.left);
}

public boolean isSymmetric(TreeNode root){
    if (root==null||root.left==null&&root.right==null){
        return true;
    }
    if (root.left==null&&root.right!=null
            ||root.left!=null&&root.right==null){
        return false;
    }
    if (root.left.val!=root.right.val){
        return false;
    }
    return isSymmetricChild(root.left,root.right);
}