Java由先序序列和中序序列还原二叉树

简介: 还原本来的二叉树并不是一个非常简单的事,虽然思想比较简单,但过程却是比较繁琐。下面我拿先序序列和中序序列来讲一下原理吧。 从先序序列中我们一下子就可以得到二叉树的根节点是第一个元素,然后再中序序列中我们也可以找到这个元素(假设二叉树中所有的元素的值不相同)这样我们就可以把中序序列分成两部分,前部分和先序序列可求得左子树,后部分与先序序列可求得右子树。

还原本来的二叉树并不是一个非常简单的事,虽然思想比较简单,但过程却是比较繁琐。下面我拿先序序列和中序序列来讲一下原理吧。
从先序序列中我们一下子就可以得到二叉树的根节点是第一个元素,然后再中序序列中我们也可以找到这个元素(假设二叉树中所有的元素的值不相同)这样我们就可以把中序序列分成两部分,前部分和先序序列可求得左子树,后部分与先序序列可求得右子树。下面以左部分为例,在除去根节点的前序序列中的第二个元素,就是我们左子树的的第一个节点,然后继续在中序序列的前部分中找到相同的元素,再次对中序序列进行分割。····最后我们就可以得到恢复的二叉树了。
纯文字的讲述不太容易理解,下面我拿个具体的例子来分析吧。
比如

int[] preOrder = {7,10,4,3,1,2,8,11};  //前序序列
int[] inOrder = {4,10,3,1,7,11,8,2};  //中序序列

我们很容易在前序序列中得知7是根节点,接下来我们在中序序列中找到7所在的位置,那么此时4,10,3,1便是左子树对应的所有的节点。11,8,2是右子树所对应的所有的节点。
然后我们在前序序列中找到除根节点以外的第一个节点,那就是10,所以这就是左子树的第一个节点。然后我们在中序序列中找到10在第二个位置上,而10的左边有一个元素4,右边有3,1两个节点。这就说明4是节点10的左孩子节点,3,1为节点10的右子树上面的节点,然后再前序序列中我们便可以看出3是10的左孩子节点,而3的左边没有元素,说明3美誉哦左孩子节点,3的右边有一个元素1,说明3只有右孩子节点。至此,你是不是也掌握了恢复二叉树的方法了呢?
原理其实并不难理解,但是代码却不是特别好写。所以我拷贝了其他人做好的一份代码,大家一起欣赏一下吧。

package MyBinaryTree;

public class CreateBianryTreeByString {

        /** 
         * Build Binary Tree from PreOrder and InOrder 
         *  _______7______ 
           /              \ 
        __10__          ___2 
       /      \        / 
       4       3      _8 
                \    / 
                 1  11 

         */  
        public static void main(String[] args) {  
            CreateBianryTreeByString build=new CreateBianryTreeByString();  
            int[] preOrder = {7,10,4,3,1,2,8,11};  
            int[] inOrder = {4,10,3,1,7,11,8,2};  

            Node root=build.buildTreePreOrderInOrder(preOrder,0,preOrder.length-1,inOrder,0,preOrder.length-1);  
            build.preOrder(root);  
            System.out.println();  
            build.inOrder(root);  
        }  

        public Node buildTreePreOrderInOrder(int[] preOrder,int begin1,int end1,int[] inOrder,int begin2,int end2){  
            if(begin1>end1||begin2>end2){  
                return null;  
            }  
            int rootData=preOrder[begin1];  
            Node head=new Node(rootData);  
            int divider=findIndexInArray(inOrder,rootData,begin2,end2);  
            int offSet=divider-begin2-1;  
            Node left=buildTreePreOrderInOrder(preOrder,begin1+1,begin1+1+offSet,inOrder,begin2,begin2+offSet);  
            Node right=buildTreePreOrderInOrder(preOrder,begin1+offSet+2,end1,inOrder,divider+1,end2);  
            head.left=left;  
            head.right=right;  
            return head;  
        }  

        public int findIndexInArray(int[] a,int x,int begin,int end){  
            for(int i=begin;i<=end;i++){  
                if(a[i]==x)return i;  
            }  
            return -1;  
        }  
        public void preOrder(Node n){  
            if(n!=null){  
                System.out.print(n.val+",");  
                preOrder(n.left);  
                preOrder(n.right);  
            }  
        }  
        public void inOrder(Node n){  
            if(n!=null){  
                inOrder(n.left);  
                System.out.print(n.val+",");  
                inOrder(n.right);  
            }  
        }  

        class Node{  
            Node left;  
            Node right;  
            int val;  

        public Node(int val){  
            this.val=val;  
        }  
            public Node getLeft(){  
                return left;  
            }  

        public Node getRight(){  
                return right;  
            }  

        public int getVal(){  
                return val;  
            }  


        }  
    }

测试结果:

7,10,4,3,1,2,8,11,//前序序列
4,10,3,1,7,11,8,2,//中序序列
目录
相关文章
|
5月前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
45 4
|
27天前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
25 1
|
27天前
|
算法 Java C语言
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(一)
22 1
|
9天前
|
算法 Java
JAVA 二叉树面试题
JAVA 二叉树面试题
11 0
|
4月前
|
Arthas 监控 算法
JVM成神路终章:深入死磕Java虚拟机序列总纲
JVM成神路终章:深入死磕Java虚拟机序列总纲
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
76 0
|
5月前
|
算法 搜索推荐 Java
二叉树的基本概念、常见操作以及如何使用Java代码
二叉树的基本概念、常见操作以及如何使用Java代码
74 1
|
5月前
|
Java
二叉树简单遍历、查找、删除(java)
二叉树简单遍历、查找、删除(java)
|
5月前
|
存储 Java
顺序存储二叉树(java)
顺序存储二叉树(java)
|
5月前
|
Java
二叉树线索化(java)
二叉树线索化(java)