数据结构与算法--重建二叉树

墨蓝 2022-10-23 09:52 89阅读 0赞

#### 二叉树 ####

*  树在实际编程中经常遇到地一种数据结构。上一篇中我们解释了二叉树及其原理，从中可以知道，树地操作会涉及到很多指针地操作，我们一般遇到地树相关地问题差不多都是二叉树。二叉树最重要地莫过于遍历，即按照某一顺序访问树中所有节点，通常有如下几种遍历方式：
    
     *  前序遍历：先根节点，左节点，右节点。用以上顺序来访问
     *  中序遍历：先左节点，中节点，右节点
     *  后续遍历：先左节点，右节点，中节点
 *  以上三种遍历都有递归和循环两种不同地实现方式，每一种遍历地递归实现都比循环实现要简单。在[上一节][Link 1]中已经给出了三种递归遍历地实现方式。
 *  二叉树还有很多特例，二叉搜索树左子树中节点总数小于或者等于根节点。右子树地节点总数大于等于根节点。
 *  二叉树特例还包括堆和红黑树。堆分为最大堆和最小堆。
 *  一下我们利用二叉树地三种遍历方式地特性来解决如下算法问题：

#### 重建二叉树 ####

*  题目：输入某个二叉树前序遍历，中序遍历地结果，请重建该二叉树。我们假设驶入地前序遍历，中序遍历不包含重复数字。例如：前序（1，2，4，7，3，5，6，8），中序遍历（4，7，2，1，5，3，8，6），如下图  
    ![在这里插入图片描述][20210309104808643.png]

##### 分析 #####

*  二叉树前序遍历中，第一个数字总数树地根节点。
 *  中序遍历中，根节点在序列中间。左子树在根节点左边，右子树在根节点右边
 *  我们通过前序遍历找到根节点
 *  在中序遍历中确认跟节点的位置后得到左右子树的长度
 *  接着将左子树，右子树分别执行以上流程（递归）
 *  如下图，在二叉树的前序遍历和中序遍历的序列中确定根节点的值，左子树的值和右子树的值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]

##### 实现 #####

*  以上对二叉树节点地定义：

/** * 二叉树节点对象定义 * * @author liaojiamin * @Date:Created in 15:24 2020/12/11 */
    public class BinaryNode implements Comparable { 
        private Object element;
        private BinaryNode left;
        private BinaryNode right;
        /** * 树高度 */
        private int height;
        private int count;
    
        public BinaryNode(Object element, BinaryNode left, BinaryNode right) { 
            this.element = element;
            this.left = left;
            this.right = right;
            this.count = 1;
            this.height = 0;
        }
    
        public int getHeight() { 
            return height;
        }
    
        public void setHeight(int height) { 
            this.height = height;
        }
    
        public Object getElement() { 
            return element;
        }
    
        public void setElement(Object element) { 
            this.element = element;
        }
    
        public BinaryNode getLeft() { 
            return left;
        }
    
        public void setLeft(BinaryNode left) { 
            this.left = left;
        }
    
        public BinaryNode getRight() { 
            return right;
        }
    
        public void setRight(BinaryNode right) { 
            this.right = right;
        }
    
        public int getCount() { 
            return count;
        }
    
        public void setCount(int count) { 
            this.count = count;
        }
    
        @Override
        public int compareTo(Object o) { 
            if (o == null) { 
                return 1;
            }
            int flag;
            if (o instanceof Integer) { 
                int myElement = (int) this.element - (int) o;
                flag = myElement > 0 ? 1 : myElement == 0 ? 0 : -1;
            } else { 
                flag = this.element.toString().compareTo(o.toString());
            }
    
            if (flag == 0) { 
                return 0;
            } else if (flag > 0) { 
                return 1;
            } else { 
                return -1;
            }
        }
    }

*  重构二叉树实现

package com.ljm.resource.math.binary;
    
    /** * 已知前序遍历：1,2,4,7,3,5,6,8 中序遍历：4,7,2,1,5,3,8,6 重建二叉树 * @author liaojiamin * @Date:Created in 17:22 2021/3/8 */
    public class RebuildBinary { 
        public static BinaryNode construct(int[] preOrder, int[] inOrder){ 
            if(preOrder == null || inOrder == null || preOrder.length != inOrder.length || preOrder.length <= 0){ 
                System.out.println("Invalid input");
                return null;
            }
            return constructCore(preOrder, inOrder, 0, preOrder.length -1, 0, inOrder.length -1);
        }
    
        public static BinaryNode constructCore(int[] preOrder, int[] inOrder,
                                        int preStart, int preEnd,
                                        int inStart, int inEnd){ 
            int rootValue = preOrder[preStart];
            BinaryNode rootNode = new BinaryNode(rootValue, null, null);
            //整棵树只有一个root节点的清空
            if(preStart == preEnd){ 
                if(inStart == inEnd && preOrder[preStart] == inOrder[inStart]){ 
                    return rootNode;
                }else { 
                    System.out.println("Invalid input");
                    return null;
                }
            }
            //找到root节点在 中序遍历中位置
            int rootInOrderIndex = inStart;
            while (rootInOrderIndex <= inEnd && inOrder[rootInOrderIndex] != rootValue){ 
                rootInOrderIndex ++;
            }
            //中序遍历中没有找到root节点
            if(rootInOrderIndex == inEnd && inOrder[rootInOrderIndex] != rootValue){ 
                System.out.println("Invalid input");
                return null;
            }
            int leftLength = rootInOrderIndex - inStart;
    
            //没有左子树情况start = end
            if(leftLength > 0){ 
                int leftInOrderStart = inStart;
                int leftInOrderEnd =  inStart + leftLength - 1;
    
                int leftPreOrderStart = preStart + 1;
                int leftPreOrderEnd = preStart + leftLength;
                rootNode.setLeft(constructCore(preOrder, inOrder, leftPreOrderStart, leftPreOrderEnd, leftInOrderStart, leftInOrderEnd));
            }
            //存在右节点
            if(leftLength < preEnd - preStart){ 
                int rightInOrderStart = rootInOrderIndex + 1;
                int rightInOrderEnd = inEnd;
    
                int rightPreOrderStart = preStart + 1 + leftLength;
                int rightPreOrderEnd = preEnd;
                rootNode.setRight(constructCore(preOrder, inOrder, rightPreOrderStart, rightPreOrderEnd, rightInOrderStart, rightInOrderEnd));
            }
            return rootNode;
        }
    
        public static void main(String[] args) { 
            int preOrder[] = { 1,2,4,7,3,5,6,8};
            int inOrder[] = { 4,7,2,1,5,3,8,6};
            BinaryNode binaryNode = construct(preOrder, inOrder);
            PostfixExTOTreeEx.printMiddleFirstTree(binaryNode);
        }
    }

*  以上我们在函数constructCore中，我们先根据前序遍历序列地第一个数字，创建根节点。
 *  接下来在中序遍历中找到根节点位置
 *  这样就能确定左右子树地数量
 *  在前序遍历和中序遍历地序列中划分左右子树节点后，
 *  将左右子树递归调用函数constructCore，分别构建左右子树。得到最终地树

[上一篇：数据结构与算法–二叉树实现原理][Link 1]  
[下一篇：数据结构与算法–二叉查找树实现原理][Link 2]

[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/111043418
[20210309104808643.png]: /images/20221023/feab6e8b64f149d08874c9be9b758113.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]: /images/20221023/b9e8656036ad4165be86a2abdf8d48d7.png
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/111231303