数据结构---二叉树

文章目录

• 一、二叉树的概念
• 二、二叉树的形状
• 三、二叉树的性质
• 四、二叉树的存储。
• 五、二叉树的遍历
• 六、二叉树相关习题
• • 1.判断二叉树是否为完全二叉树
  • 2.寻找最近公共祖先
  • 3.从��序与后序遍历序列构造二叉树

    一、二叉树的概念

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

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

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

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

    二、二叉树的形状

    两种特殊的二叉树

    三、二叉树的性质

    1.二叉树第K行的最大结点数为2k-1,(K>=1).

    2.二叉树前K行最多结点数为2k-1.(K>=1)

    3.对于任何一颗二叉树，no,n1,n2分别表示度为0，1，2的结点的个数，则有如下表达式：n0 = n2 + 1。

    在一颗拥有N个结点的二叉树中，有N-1条边。 而二叉树由度为0，1，2的结点构成。 N = N0+N1+N2

    而边则是由度为1和度为2的结点产生。 边数 = 0 * N0 + 1N1+2N2 = N1+2N2。

    可得 N0+N1+N2 = N1+2N2+1

    即 N0 = N2 + 1 .

    4.具有N个结点的完全二叉树是对怒为log2（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 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 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 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