根据一个二叉树的前序和中序，重构二叉树

落日映苍穹つ 2022-12-04 15:57 122阅读 0赞

要重构二叉树，首先要知道什么是二叉树，以及如何自己创建一个二叉树。了解了二叉树是如何创建出来的，才能重构二叉树。

*  什么是二叉树

**树（Tree）**是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：  
1）有且仅有一个特定的称为根（Root）的结点；  
2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

此外，树的定义还需要强调以下两点：  
1）n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。  
2）m>0时，子树的个数没有限制，但它们一定是互不相交的。  
示例树：一棵普通的树：

![format_png][]

如上图，普通的二叉树就是有着左右分之（左右子孩子）的结构。

*  自定义创建一个二叉树

直接上代码，代码中有具体的注释：

// 二叉树对象
    public class TreeNode {
    
    
    
        private Node root ;
    
        public Node getRoot() {
            return root;
        }
    
        public void setRoot(Node root) {
            this.root = root;
        }
    
        public void add(int data){
    
    //        Node node = new Node(data);
            if(this.root == null){
                this.root = new Node(data);
                System.out.println("root节点"+data+"创建成功");
            } else{
                this.root.addNode(data);
                System.out.println("插入节点"+data+"成功");
            }
    
    
    
        }
    
    
        public static void main(String[] args) {
            TreeNode treeNode = new TreeNode();
            treeNode.add(5);
            treeNode.add(2);
            treeNode.add(1);
            treeNode.add(6);
            treeNode.add(7);
            treeNode.add(3);
    
            System.out.println("before=====");
            // 前序 根 左 右
            TreeNodeSort.getBeforeSort(treeNode.getRoot());
    
            System.out.println("mid========");
            TreeNodeSort.getMidSort(treeNode.getRoot());
    
            System.out.println("after=======");
            TreeNodeSort.getAfterSort(treeNode.getRoot());
    
            System.out.println("max deep========");
            System.out.println(TreeNodeSort.getDeep(treeNode.getRoot()));
    
    
        }
    
    }

// 二叉树的节点对象
    public class Node {
    
        private int data;
    
        private Node left;
    
        private Node right;
    
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public Node getLeft() {
            return left;
        }
    
        public void setLeft(Node left) {
            this.left = left;
        }
    
        public Node getRight() {
            return right;
        }
    
        public void setRight(Node right) {
            this.right = right;
        }
    
        public Node(int data){
            this.data = data;
            this.left = null;
            this.right = null;
        }
        public Node(){
    
        }
    
        public void addNode(int data){
    //        Node node = new Node(data);
            if(this.data > data){
                System.out.print("left=======");
                if(this.left == null){
                    this.left = new Node(data);
                } else{
                    this.left.addNode(data);
                }
                return ;
            }
            if(this.data < data){
                System.out.print("right=======");
                if(this.right == null){
                    this.right = new Node(data);
                } else{
                    this.right.addNode(data);
                }
                return ;
            }
        }
    }

// 二叉树的各个排序算法
    public class TreeNodeSort {
    
        public static void getBeforeSort(Node node){
            if(node == null){
                return ;
            } else{
                System.out.println(node.getData());
                getBeforeSort(node.getLeft());
                getBeforeSort(node.getRight());
            }
        }
    
        public static void getAfterSort(Node node){
            if(node == null){
                return;
            } else{
                getAfterSort(node.getLeft());
                getAfterSort(node.getRight());
                System.out.println(node.getData());
            }
        }
    
        public static void getMidSort(Node node){
            if(node == null){
                return;
            } else{
                getMidSort(node.getLeft());
                System.out.println(node.getData());
                getMidSort(node.getRight());
    
            }
        }
    
        // 获取树的最大深度
        public static int getDeep(Node node){
            if(node == null){
                return 0;
            } else{
                int leftDeep = getDeep(node.getLeft());
                int rightDeep = getDeep(node.getRight());
                return leftDeep > rightDeep ? leftDeep+1:rightDeep+1;
            }
        }
    }

*  知道了什么是二叉树，能自定义创建一个二叉树， 并且还能对二叉树进行排序。那么我们就可以来重构二叉树

// 根据前中序 完成重构二叉树
    public class RebuildBinaryTree {
    
        public static Node rebuild(int[] pre,int[] mid){
    
            return rebuild(pre,0,pre.length-1,mid,0,mid.length-1);
        }
    
    
        // 重构二叉树，我们知道了他的排序过程，那么我们就能根据规律来根据前中序对二叉树进行重构
        // 前：根-左-右  中：左-根-右
        // 根据前序和中序，确定二叉树的根节点，然后进行递归操作，就容易重构二叉树
        private static Node rebuild(int[] pre, int perStart, int perEnd, int[] mid, int midStart, int midEnd) {
    
            if(perStart > perEnd || midStart > midEnd){
                return null;
            }
    
            Node root = new Node(pre[perStart]);
    //        int perCount = 0;
            for(int i = midStart;i <= midEnd;i ++){
                if(pre[perStart] == mid[i]){
                    int leftChild = i - midStart;
                    int rightChild = midEnd - i;
                    root.setLeft(rebuild(pre,perStart + 1,perStart + leftChild,mid,midStart,i - 1));
                    root.setRight(rebuild(pre,perStart + leftChild + 1,perEnd,mid,i + 1,midEnd));
                    break;
                }
            }
    
            return root;
        }
    
        public static void main(String[] args) {
    
            int[] per = {1,2,4,7,3,5,6,8};
            int[] mid = {4,7,2,1,5,3,8,6};
    
            Node node = RebuildBinaryTree.rebuild(per,mid);
    
            System.out.println(node.getLeft());
    
            TreeNodeSort.getBeforeSort(node);
    
    
        }
    }

这篇文章只是针对普通二叉树来说的，如果是其他的树型结构需要进行其他的学习。

[format_png]: /images/20221123/74bb94778b3b4ba0ba6ad30917dc144d.png