当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-从先序遍历和中序遍历重建二叉树

发表于: 2012-01-17   作者:bylijinnan   来源:转载   浏览:
摘要: public class BuildTreePreOrderInOrder { /** * Build Binary Tree from PreOrder and InOrder * _______7______ / \ __10__ ___2 / \ / 4

public class BuildTreePreOrderInOrder {

	/**
	 * Build Binary Tree from PreOrder and InOrder
	 *  _______7______
       /              \
    __10__          ___2
   /      \        /
   4       3      _8
            \    /
             1  11
             
	 */
	public static void main(String[] args) {
		BuildTreePreOrderInOrder build=new BuildTreePreOrderInOrder();
		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;
		}


	}
}


java-从先序遍历和中序遍历重建二叉树

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
对于一棵 二叉树T,我们可以递归定义它的先序遍历,中序遍历,后序遍历:  1、先序遍历 ( PreO
1:问题 给定二叉树的2个遍历序列(如先序+中序,先序+后序,中序+后序等),是否能够根据这2个遍历
在自考中一直在头疼二叉树的遍历问题,先序中序后序,先根后根傻傻分不清楚。在这里就来谈谈着三种
这是根据本人另一个C语言版本采用python实现的,添加了根据中序和后序重建二叉树功能,更多详细解释
[二叉树]已知后序/中序遍历,求先序遍历 二叉树后序遍历序列是dabec,中序遍历序列debac,它的前序
[二叉树]已知后序/中序遍历,求先序遍历 二叉树后序遍历序列是dabec,中序遍历序列debac,它的前序
二叉树的遍历分为前序遍历、中序遍历、后序遍历。先来看一下三种遍历的不同 1前序遍历 (1)访问根
题目(剑指offer page55): 输入某二叉树的前序遍历和中序遍历结果,请重建二叉树 ,假设前序遍历和
1. 问题描述 使用队列作为辅助存储,按树的结点的深度,从根开始依次访问所有结点。 2.问题分析与
题记:写这篇博客要主是加深自己对遍历二叉树的认识和总结实现算法时的一些验经和训教,如果有错误
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号