数据结构--二叉树详解

一，概念

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); }