admin管理员组

文章数量:1794759

二叉树

二叉树-1

一、二叉树的概念与基本性质

​ 二叉树是n(n>=0)个结点的有限集合，该集合或者为空集，或者由一个根节点和两棵互不相交的、分别称为左子树和右子树的二叉树组成（递归的好苗子）。介绍一下常用的三种特殊二叉树：

斜树： 所有结点只有左子树或所有结点只有右子树，如图所示

满二叉树： 所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，如图所示

完全二叉树： 对一棵具有n各结点的二叉树按层序遍历编号，如果编号为i(i>=1&&i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树（其实很好理解，就是结点按顺序排列）。我们可以得到如下性质1）叶子结点只会出现在最后两层。2）度为1的结点只能有一个，并且该结点只有左孩子。继续看图

二叉树的几个性质（不证明，有兴趣可以自行查找）：

1）二叉树的第i层上最多有2^i-1 个结点（i>=1）。

2）在一棵深度为k的二叉树中，最多有2^k-1个结点（满二叉树情况下），最少有k个结点（斜树）。

3）在一棵二叉树中，如果叶子结点的个数为n₀ ,度为2的结点个数为n₂ ,则n₀ =n₂ +1（这个性质比较重要）。

这个性质证明一下：假设n为二叉树的结点总数，n₁ 为二叉树中度为1的结点个数，我们可以得到
n=n₀ +n₁ +n₂
考虑二叉树中的分支数，因为只有顶点没有入度（也就是除了顶点外，每个结点都有一条连向它的边，注意是连向它的，不是它连出去的边，一个结点连出去的边有0条，1条，2条三种可能情况），所以总的分支数为n-1，同时n₁ 的结点连着一个结点，n₂ 的结点连着两个结点所以总分支数也可以写成n-1=n₁ +2*n₂ ，将上面的式子的代入，移项可得n₀ =n₂ +1。

4）具有n个结点的完全二叉树 的深度为floor(log₂ n)+1;

5)对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i(i>=1&&i<=n)的结点，有：1.如果i>1,则结点i的双亲的编号为floor(i/2)。2.如果某编号为i的结点有左孩子的话，则它左孩子的编号为2*i;，同理，如果有右孩子的话，右孩子的编号为2i+1（作用在于当你用数组来实现完全二叉树的时候可以根据这个性质来确定子结点和父结点）。

---

二、二叉树的遍历

​ 上面啰嗦地介绍了一些性质和概念，其实如果嫌烦可以不求甚解，有个印象就好。本节主要来介绍下对于一棵二叉树我们怎么去遍历（从根结点出发，按照某种次序访问二叉树的所有结点，使得每个结点被访问一次且仅被访问一次 ）它。

前序遍历

顺序是先访问根节点–>左子树–>右子树，废话少说直接上代码

递归遍历

 public static void re_preorder(Node root){if(root==null){return;}System.out.println(root.val);re_preorder(root.left);re_preorder(root.right);}

辅助栈遍历

    public static void  preorder2(Node root){Stack<Node> s=new Stack<Node>();if(root!=null) {s.push(root);}while(!s.empty()){Node temp=s.pop();System.out.println(temp.val);if(temp.right!=null){s.push(temp.right);}if(temp.left!=null){s.push(temp.left);}}}

Morris遍历

    public static void m_preorder(Node root){if(root==null){return;}Node pnode=root;while(pnode!=null){if(pnode.left==null){System.out.println(pnode.val);pnode=pnode.right;}else{Node pre=pnode.left;while(pre.right!=null&&pre.right!=pnode){pre=pre.right;}if(pre.right==null){pre.right=pnode;System.out.println(pnode.val);pnode=pnode.left;}else{pre.right=null;pnode=pnode.right;}}}}

递归写法和辅助栈写法其实是一样的也比较好理解，递归也是调用了栈，所以时间复杂度和空间复杂度都是O(n),而Morris遍历的时间复杂度是O(n),空间复杂度却为O(1),但是可能看得会迷惑点，这边建议看着代码找个例子画一下图。在此叙述一下Morris的遍历的实现过程，

我们记当前结点为pnode,

如果pnode没有左孩子就将当前结点右移；

如果pnode有左孩子，就找到左子树上最右的结点记为pre;

​ 如果pre的右孩子为空，就将右孩子指向pnode，然后将pnode左移；

​ 如果pre的右孩子已经指向了pnode ,就将pre右孩子指空，然后pnode右移；

也许看了这个过程你会感觉一头雾水，在这里我提供下我的一点小理解，首先这个遍历在空间性能上较之前两种优化了，它是怎么做到的呢——利用闲置的右指针去指向将来想要返回的上一层结点，那么问题来了，我们怎么知道当前结点是初次遍历到的还是返回的，只需要看当前结点左子树的右孩子是不是连着自己，如果连着自己那就是第二次回到了这个点。至于是什么序遍历无非就是你在什么时候System.out.println() 。借用看到的一句话

morris遍历的实质就是建立一种机制，对于没有左子树的结点只到达一次，对于有左子树的结点会到达两次

中序遍历

左子树–>根节点–>右子树的顺序。上代码

递归遍历

    public static void re_inorder(Node root){if(root==null){return;}re_inorder(root.left);System.out.println(root.val);re_inorder(root.right);}

辅助栈遍历

    public static void inorder2(Node root){if(root==null){return;}Stack<Node> s=new Stack<Node>();s.push(root);Node pnode=root.left;while(pnode!=null||!s.empty()){if(pnode!=null){s.push(pnode);pnode=pnode.left;}else{pnode=s.pop();System.out.println(pnode.val);pnode=pnode.right;}}}

Morris遍历

    public static void m_inorder(Node root){if(root==null){return;}Node pnode=root;while(pnode!=null){if(pnode.left==null) {System.out.println(pnode.val);pnode = pnode.right;}else{Node pre=pnode.left;while(pre.right!=null&&pre.right!=pnode){pre=pre.right;}if(pre.right==null){pre.right=pnode;pnode=pnode.left;}else{System.out.println(pnode.val);pre.right=null;pnode=pnode.right;}}}}

后序遍历

左子树–>右子树–>根结点，继续上代码：

递归遍历

    public static void re_postorder(Node root){if(root==null){return;}re_postorder(root.left);re_postorder(root.right);System.out.println(root.val);}

辅助栈双栈遍历

    public static void postorder2d(Node root){if(root==null){return;}Stack<Node> s1=new Stack<Node>();Stack<Node> s2=new Stack<Node>();s1.push(root);while(!s1.empty()){Node pnode=s1.pop();s2.push(pnode);if(pnode.left!=null){s1.push(pnode.left);}if(pnode.right!=null){s1.push(pnode.right);}}while(!s2.empty()){Node pnode=s2.pop();System.out.println(pnode.val);}}

双栈实现后序遍历其实很容易理解，就是从栈1中取出当前结点压入栈2，然后把当前结点的左结点压入栈1，右结点压入栈1，这样下次弹出来再压入栈2会使栈2中的结点排序从上到下为左结点，右节点，根结点，依次出栈就是后序遍历。

辅助栈单栈遍历

    public static void postorder2(Node root){if(root==null){return;}Stack<Node> s=new Stack<Node>();s.push(root);Node pre=null;while(!s.empty()){Node temp=s.peek();if(temp.left==pre||temp.right==pre){System.out.println(temp.val);s.pop();}else if(temp.left==null&&temp.right==null){System.out.println(temp.val);s.pop();}else{if(temp.right!=null){s.push(temp.right);}if(temp.left!=null){s.push(temp.left);}}pre=temp;}}

单栈遍历的核心在于，你要判断栈中当前顶点是刚进入的结点，还是左右孩子弹出来后再次碰到的结点。

Morris遍历

   public static Node reversel(Node root){Node pre=null;Node next=null;while(root!=null){next=root.right;root.right=pre;pre=root;root=next;}return pre;}public static void printedg(Node root){Node tail=reversel(root);while(tail!=null){System.out.println(tail.val);tail=tail.right;}reversel(root);}public static void m_postorder(Node root){if(root==null){return;}Node pnode=root;while(pnode!=null){Node pre=pnode.left;if(pre!=null){while(pre.right!=null&&pre.right!=pnode){pre=pre.right;}if(pre.right==null){pre.right=pnode;pnode=pnode.left;continue;}else{pre.right=null;printedg(pnode.left);}}pnode=pnode.right;}printedg(root);}

后序遍历的morris遍历比较麻烦，比较好的解决方法如图所示

如果我们能根据箭头方向依次打印，先按1箭头打印，再按2箭头打印，依次推之，其实就是完成了后序遍历，所以在后序遍历中，我们应该依次逆序打印当前结点左子树的右边界。怎么实现逆序打印，其实将右指针连接的结点看成单链表的话，就是将单链表反转打印，再反转恢复原样。

总结：

二叉树的遍历其实并不只有这几种，遍历的作用也是巨大的，我也会在后续更新进阶的遍历。

---

三、已知前序，中序，后序遍历构造二叉树

其实这块我就是想来讲一下如何从二叉树的遍历中恢复出这棵二叉树——就是告诉了遍历后的结果和遍历方式，能否恢复出二叉树，以及怎么样恢复出二叉树。首先来复习下三种遍历方式——前序遍历的遍历顺序:根节点–>左子树–>右子树；中序遍历：左子树–>根节点–>右子树； 后序遍历: 左子树–>右子树–>根节点。

已知前序遍历和中序遍历：

假如已经知道前序遍历和中序遍历的结果，构造一棵二叉树思路应该是这样的：找到根节点是哪个，哪些数是属于左子树的，哪些是属于右子树的，然后在找到的左右子树中再重复上述步骤，递归构造出二叉树。接下来举个栗子详细讲解

如图（图有点丑）所示的二叉树，我们很容易得到它的前序遍历[3,9.20,15,7]和中序遍历[9,3,15,20,7] 。首先解决第一个问题，根节点是哪一个，其实看到前序遍历的遍历规则就可以知道根节点就是数组第一个数3，在前序遍历的数组中是看不出哪些是左子树，哪些是右子树的，但是当我们知道根节点和中序遍历后就不一样的，比如这边我们知道根节点是3，在中序数组中找到3的位置，然后3的左边都属于左子树，3的右边都属于右子树，并且你也能知道左右子树的长度，再返回到前序遍历数组中，根节点后面左子树长度内的数都属于前序遍历左子树部分，剩下的都是右子树部分。而左右子树可以继续用上面的方式来确定对应的根节点，左子树的左右子树等等。直到叶子结点。

上代码

    public static Node recover1(int[] preorder,int[] inorder,int pl,int pr,int il,int ir){if(pl>pr){return null;}int root_val=preorder[pl]; //前序遍历数组第一个就是根节点int root_i=map.get(root_val);int size=root_i-il;//得到左子树的长度Node root=new Node(root_val);root.left=recover1(preorder,inorder,pl+1,pl+size,il,root_i-1);root.right=recover1(preorder,inorder,pl+size+1,pr,root_i+1,ir);return root;}public static void main(String[] args){int[] preorder={3,9,20,15,7};int[] inorder={9,3,15,20,7};//int[] postorder={9,15,7,20,3};for(int i=0;i<5;i++){map.put(inorder[i],i);}Node root=recover1(preorder,inorder,0,4,0,4);//Node root2=recover2(postorder,inorder,0,4,0,4);//show(root2);}

实现起来还是简单的，对代码做一些解释。6个参数前两个不用解释，就是遍历数组，pl,pr则是在前序遍历数组中下一棵子树的索引范围，就像第一次时，pl=0,pr=preorder.length-1;il,ir同理，是中序数组中子树的索引范围。然后是map，这是为了避免每次递归都要循环在中序遍历数组中找根节点的索引值，不如在一开始用map存储(inorder[i],i)的键值对，这样就可以根据值获得其在中序遍历数组中的索引。

已知中序遍历和后序遍历

这无非是照猫画虎，就不多赘述了直接上代码

    public static Node recover2(int[] postorder,int[] inorder,int pol,int por,int il,int ir){if(pol>por){return null;}int root_val=postorder[por];int root_i=map.get(root_val);int size=root_i-il;Node root=new Node(root_val);root.left=recover2(postorder,inorder,pol,pol+size-1,il,root_i-1);root.right=recover2(postorder,inorder,pol+size,por-1,root_i+1,ir);return root;}public static void main(String[] args){//int[] preorder={3,9,20,15,7};int[] inorder={9,3,15,20,7};int[] postorder={9,15,7,20,3};for(int i=0;i<5;i++){map.put(inorder[i],i);}//Node root=recover1(preorder,inorder,0,4,0,4);Node root2=recover2(postorder,inorder,0,4,0,4);//show(root2);}

还剩一个就是已知前序遍历和后序遍历构造二叉树，其实根据上面的思想我们就可以知道，这是无法完成的，因为没有中序遍历，你无法确定左，右子树的长度。

---

这是本人第一次发文，本着共同学习共同进步的想法，深知网友都是人才，希望能够得到有缘人的指导与探讨，同样也希望能把发文这件事坚持下来。（一直在想自己的文章应该有点特色，特色就是每文一享吧）
给我一首歌的时间–周杰伦（要绿钻）

本文标签： 二叉树