java先序中序建立二叉树的递归算法

2021年6月24日 4点热度 0条评论 来源: 网络2017

在网上找了很多知道先序中序建立二叉树的例子,但是看不懂,所以自己耐心写了一个,并附有详细的注释。

首先描述一下大致的算法例如: 

先序 e,a,c,b,d,g,f 

中序 a,b,c,d,e,f,g

先序的第一个节点e,就是头节点,所以中序中e的左半部分单独当做一个二叉树处理,右半部分一样,即: 

(a,b,c,d),e,(f,g)

右半部分(a,b,c,d)在先序是a,c,b,d

左半部分(f,g)的先序是g,f

我们可以得出左半部分的头结点a,就是e的左节点;找出右半部分的头结点g就是右节点。

再找a的左节点和右节点就是一个递归了。以下直接贴代码

/**
 *二叉树建模 
 **/
public class MyBinaryTree<U>{

	static class Node<T>{
		Node left;
		Node right;
		T val;
		public Node(T val){
			this.val = val;
		}
	}
	
	private U[] preOrder = null;
	private U[] inOrder = null;
	private U[] sufOrder = null;
	
	
	
	public U[] getPreOrder() {
		return preOrder;
	}



	public void setPreOrder(U[] preOrder) {
		this.preOrder = preOrder;
	}



	public U[] getInOrder() {
		return inOrder;
	}



	public void setInOrder(U[] inOrder) {
		this.inOrder = inOrder;
	}



	public U[] getSufOrder() {
		return sufOrder;
	}



	public void setSufOrder(U[] sufOrder) {
		this.sufOrder = sufOrder;
	}

	/**
	 *根据二叉树先序和中序建立二叉树模型,返回头结点
	 *@param preOrder 先序数组
	 *@param big1 先序中需要建立二叉树的部分的起始位置 
	 *@param end1 先序中需要建立二叉树的部分的最终位置
	 *@param inOrder 中序数组
	 *@param big2 中序中需要建立二叉树的部分的起始位置 
	 *@param end2 中序中需要建立二叉树的部分的最终位置
	 *如:先序{1,3,4,6,8,9,0,2} big1为2,end1为5 
	 *中序{1,5,7,6,8,4,9}big2为3,end2为6
	 *保证需要建立二叉树的先序部分里和中序部分,它们的组成节点是一样的。
	 **/
	public Node getTreePreOrderInOrder(U[] preOrder,int big1,int end1,U[] inOrder,int big2,int end2){
		if(big1>end1||big2>end2) return null;
		Node<U> head = new Node<U>(preOrder[big1]);
		int index = 0;//头节点(头结点指的是big1到end1范围内的节点的头节点)在中序big2到end2之间所处的位置
		for(int i=big2; i<end2 ; i++){
			U in = inOrder[i];
			if(in.equals(preOrder[big1])){
				  break;
			}else{
				index ++;
			}
		}
		//计算建立左节点的节点范围
		int leftBig1 = big1+1;//先序的起始位置
		int leftEnd1 = big1+index;//先序的最终位置
		int leftBig2 = big2;//中序的起始位置
		int leftEnd2 = big2+index-1;//中序的最终位置
		//计算建立右节点的节点范围
		int rightBig1 = big1+index+1;//先序的起始位置
		int rightEnd1 = end1;//先序的最终位置
		int rightBig2 = big2+index+1;//中序的起始位置
		int rightEnd2 = end2;//中序的最终位置
		//左节点
		Node<U> leftNode = getTreePreOrderInOrder(preOrder, leftBig1,leftEnd1,inOrder,leftBig2,leftEnd2);
		//右节点
		Node<U> rightNode = getTreePreOrderInOrder(preOrder, rightBig1,rightEnd1,inOrder, rightBig2,rightEnd2);
		head.left = leftNode;
		head.right = rightNode;
		return head;
	}

	public void preNode(Node head){
		if(head!=null){
			System.out.print(head.val.toString()+",");
			preNode(head.left);
			preNode(head.right);
		}
	}
	
	public void inOrder(Node head){
		if(head!=null){
			
			inOrder(head.left);
			System.out.print(head.val.toString()+",");
			inOrder(head.right);
		}
	}
	
	public void printTree(Node<U> head){
		
	}
	
	public static void main(String srgd[]){
		String preOrder[] = {"e","a","c","b","d","g","f"};
		String inOrder[] = {"a","b","c","d","e","f","g"};
		MyBinaryTree<String> tree = new MyBinaryTree<String>();
		Node head = tree.getTreePreOrderInOrder(preOrder, 0, preOrder.length-1, inOrder, 0, inOrder.length-1);
		tree.preNode(head);
		System.out.println();
		tree.inOrder(head);
	}
}

    原文作者:网络2017
    原文地址: https://blog.csdn.net/wangdongmei2012/article/details/10002523
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。