数据结构---二叉树

一、二叉树的概念

二叉树是一个由结点构成的有限集合。

该集合可以为空，也可为由根节点和左子树右子树构成，且左子树和右子树本身又是一颗二叉树

从二叉树的定义可知，二叉树的构造是由递归实现的，所以对于二叉树的习题来说，递归往往是最容易实现的。

二叉树与树最大的区别是结点的最大的度为2，且左右子树顺序不能交换，如若交换，就是一颗新的二叉树.

二、二叉树的形状

两种特殊的二叉树

三、二叉树的性质

1.二叉树第K行的最大结点数为2^k-1,(K>=1).
2.二叉树前K行最多结点数为2^k-1.(K>=1)
3.对于任何一颗二叉树，no,n1,n2分别表示度为0，1，2的结点的个数，则有如下表达式：n0 = n2 + 1。

在一颗拥有N个结点的二叉树中，有N-1条边。 而二叉树由度为0，1，2的结点构成。 N = N₀+N₁+N₂
而边则是由度为1和度为2的结点产生。 边数 = 0 * N₀ + 1N₁+2N₂ = N₁+2N₂。
可得 N₀+N₁+N₂ = N₁+2N₂+1
即 N₀ = N₂ + 1 .

4.具有N个结点的完全二叉树是对怒为log₂（N+1)向上取整。
5.对于具有N个结点的完全二叉树来说，如果结点编号按层序遍历的顺序从1开始赋值。则对于结点i来说
当i = 1时，表示的是根节点。
当i > 1时，父亲结点为 i/2. 如果 2i > n，则该结点没有左孩子，如果2i +1 > n 则该结点没有右孩子。

四、二叉树的存储。

对于二叉树的存储来说，分为顺序存储和链式存储
存的目的是为了取，了解二叉树的存储，是为了了解取时的底层原理。

顺序存储
取一段连续的空间用来存储二叉树，例如数组，以根结点为0下标，按照层序遍历的方式依次存储。左孩子结点下标为父亲结点下标2+1，右孩子结点下标为父亲结点下标2+2.当结点不存在时，存入‘#’，代表该处结点不存在。

但顺序存储也有弊端，当二叉树为非完全二叉树时，使用顺序存储造成数组大量的空间浪费。

而对于如此情况，就该使用链式存储。
链式存储

对于每个结点来说，除了自身的数据域外，另外再添加两个指针域，分别指向左孩子和右孩子结点，再用一个头指针指向根结点。

五、二叉树的遍历

由二叉树的定义，遍历二叉树时，使用递归方法会轻松不少
1.前序遍历 （先访问根节点 -->再访问左孩子结点 -->再访问右孩子结点）
2.中序遍历 （先访问左孩子结点 --> 再访问根节点 -->再访问右孩子结点）
3.后序遍历 （先访问左孩子结点 --> 再访问右孩子结点 -->再访问根结点）

 //前序遍历
    public void  prevOrder(TreeNode root){
        if (root ==  null){
            return;
        }
        System.out.println(root.val);
        prevOrder(root.left);
        prevOrder(root.right);
    }
    //中序遍历
    public void  inOrder(TreeNode root){
        if ( root == null){
            return;
        }
        inOrder(root.left);
        System.out.println(root.val);
        inOrder(root.right);
    }
    //后序遍历
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val);
    }

结果分别为
前序遍历：ABDCFG
中序遍历：DBAFCG
后序遍历：DBFGCA

层序遍历 （按二叉树的层次，由左到右，由上到下进行访问）

二叉树的层序遍历，借助队列来进行遍历

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

遍历结果为：ABCDFG
力扣链接: 层序遍历

六、二叉树相关习题

1.判断二叉树是否为完全二叉树

思路：对二叉树进行层序遍历，依次入队，到下一行时，上一行的结点全部出队，当出队结点有空结点时，判断此时队列中元素是否全为空。

   //判断二叉树是否为完全二叉树
    public boolean isCompeleteTree(TreeNode root){
        if ( root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if (cur == null){
                return isAllNUll(queue);
            }else {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }
        }
        return false;
    }
    public boolean isAllNUll(Queue<TreeNode> queue){
           int szie = queue.size();
           while (szie > 0){
               TreeNode cur = queue.poll();
               if (cur != null){
                   return false;
               }
           }
           return true;
    }

2.寻找最近公共祖先

力扣链接: 二叉树的最近公共祖先

思路：使用递归思想对整棵树进行遍历
p和q的存在位置如下图所示，分为三种情况
其中 第三种p和q有一个是根节点，这种情况最为特殊，他们的最近公共祖先就是root

第一种情况，对左树进行递归，在左树中找到p，在右树中找到了q，那么他们的最近公共祖先就是root
第二种情况，对左树进行递归，找到p，在右树中没有找到q，那么就肯定p和q都在左树中，且q一定在p的下方。

   public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if (p == root || q == root){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        if (left != null && right != null){
            return root;
        }
        if (left != null){
            return left;
        }
        if (right != null){
            return right;
        }
        return null;
    }

3.从中序与后序遍历序列构造二叉树

力扣链接: 从中序与后序遍历序列构造二叉树

思路：采用递归，根据中序和后序遍历的特点递归构造二叉树。
首选明确 中序和后序的特点
中序：先遍历左树，再是根节点，最后是右树
后序：先遍历左树，再是右树，最后是根节点

构造二叉树的原理是先创建根节点，再给根节点添加上左右子树。
所以我们先找到根节点。
在后序遍历中，由于其递归顺序，我们可知3是根节点。此时创建根节点
我们在中序遍历的数组中，找到3的位置，可知3的左边都是左子树，3的右边都是右子树。

我们再在后序遍历的数组从向前看，找到20，此时20就作为3的右子树的根节点，如此往复递归，最后就会构造出一颗二叉树.

 public static int postIndex;
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
          postIndex = postorder.length-1;
         return buildChildrtree(inorder,postorder,0,inorder.length-1);
    }
    public static TreeNode buildChildrtree(int[] inorder,int[] postorder,int begin,int end){
           if (begin > end){
               return null;
           }
           if (postIndex < 0){
               return null;
           }
           
           TreeNode root = new TreeNode(postorder[postIndex]);
           int rootIndex = findIndex(inorder,begin,end,postorder[postIndex]);
           postIndex--;
           root.right = buildChildrtree(inorder,postorder,rootIndex+1,end);
           root.left = buildChildrtree(inorder,postorder,begin,rootIndex-1);
           return root;
    }
    public static int findIndex(int[] inorder,int begin,int end,int key){
        for (int i = begin; i <= end; i++) {
            if (inorder[i] == key){
                return i;
            }
        }
        return -1;
    }

以上就是本篇文章所有内容，对你有帮助的话，点赞收藏支持一下吧！