蜘蛛从网站哪里抓取,自助建站源码下载,做网站从何开始,广东省自然资源厅领导分工二叉树
树在实际编程中经常遇到地一种数据结构。上一篇中我们解释了二叉树及其原理#xff0c;从中可以知道#xff0c;树地操作会涉及到很多指针地操作#xff0c;我们一般遇到地树相关地问题差不多都是二叉树。二叉树最重要地莫过于遍历#xff0c;即按照某一顺序访问树…二叉树
树在实际编程中经常遇到地一种数据结构。上一篇中我们解释了二叉树及其原理从中可以知道树地操作会涉及到很多指针地操作我们一般遇到地树相关地问题差不多都是二叉树。二叉树最重要地莫过于遍历即按照某一顺序访问树中所有节点通常有如下几种遍历方式 前序遍历先根节点左节点右节点。用以上顺序来访问中序遍历先左节点中节点右节点后续遍历先左节点右节点中节点 以上三种遍历都有递归和循环两种不同地实现方式每一种遍历地递归实现都比循环实现要简单。在上一节中已经给出了三种递归遍历地实现方式。二叉树还有很多特例二叉搜索树左子树中节点总数小于或者等于根节点。右子树地节点总数大于等于根节点。二叉树特例还包括堆和红黑树。堆分为最大堆和最小堆。一下我们利用二叉树地三种遍历方式地特性来解决如下算法问题
重建二叉树
题目输入某个二叉树前序遍历中序遍历地结果请重建该二叉树。我们假设驶入地前序遍历中序遍历不包含重复数字。例如前序12473568中序遍历47215386如下图
分析
二叉树前序遍历中第一个数字总数树地根节点。中序遍历中根节点在序列中间。左子树在根节点左边右子树在根节点右边我们通过前序遍历找到根节点在中序遍历中确认跟节点的位置后得到左右子树的长度接着将左子树右子树分别执行以上流程递归如下图在二叉树的前序遍历和中序遍历的序列中确定根节点的值左子树的值和右子树的值 实现
以上对二叉树节点地定义 /*** 二叉树节点对象定义** 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;}Overridepublic 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 endif(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分别构建左右子树。得到最终地树
上一篇数据结构与算法–二叉树实现原理 下一篇数据结构与算法–二叉查找树实现原理
