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

java-50-输入两棵二叉树A和B,判断树B是不是A的子结构

发表于: 2012-02-10   作者:bylijinnan   来源:转载   浏览:
摘要: 思路来自: http://zhedahht.blog.163.com/blog/static/25411174201011445550396/ import ljn.help.*; public class HasSubtree { /**Q50. * 输入两棵二叉树A和B,判断树B是不是A的子结构。 例如,下图中的两棵树A和B,由于A中有一部分子树的结构和B是一
思路来自: http://zhedahht.blog.163.com/blog/static/25411174201011445550396/
import ljn.help.*;
public class HasSubtree {

	/**Q50.
	 * 输入两棵二叉树A和B,判断树B是不是A的子结构。

例如,下图中的两棵树A和B,由于A中有一部分子树的结构和B是一样的,因此B就是A的子结构。


                 1                                                     8
               /   \                                                 /    \
              8     7                                                9    2
            /    \
           9     2
                /  \
               4    7
	 */
	public static void main(String[] args) {
		int[] data01={1,8,7,9,2,0,0,0,0,4,7};
		Node tree01=Helper.createTree(data01);
		int[] data02={8,9,2};
		Node tree02=Helper.createTree(data02);
		
		boolean result=hasSubtree(tree01,tree02);
		System.out.println(result);//true
		
		/*
		 * hasSubtreeByOrder() does not work.
		 * preOrder and inOrder can define a unique BTree,but 
		 * inOrderOfTree1=9,8,4,2,7,1,7
		 * inOrderOfTree2=9,8,2
		 */
		result=hasSubtreeByOrder(tree01,tree02);
		System.out.println(result);//false
		
	}

	//hasSubtree():just some "boundary condition".see hasSubtreeCore().
	public static boolean hasSubtree(Node tree1,Node tree2){
		if((tree1==null&&tree2!=null)||
				tree1!=null&&tree2==null){
			return false;
		}
		if(tree1==null&&tree2==null){
			return true;
		}
		return hasSubtreeCore(tree1,tree2);
	}
	
	public static boolean hasSubtreeCore(Node tree1,Node tree2){
		boolean result=false;
		if(tree1.getData()==tree2.getData()){//if roots are equal,test if both leftTree and rightTree are equal
			result=tree1HaveAllNodesOfTree2(tree1,tree2);
		}
		//roots are not equal
		if(!result&&tree1.getLeft()!=null){//find tree2 in tree1's left child,if exists
			result=hasSubtreeCore(tree1.getLeft(),tree2);
		}
		if(!result&&tree1.getRight()!=null){//find tree2 in tree1's right child,if exists
			result=hasSubtreeCore(tree1.getRight(),tree2);
		}
		return result;
	}
	
	public static boolean tree1HaveAllNodesOfTree2(Node tree1,Node tree2){
		if(tree2==null){
			return true;
		}
		if(tree1==null){
			return false;
		}
		if(tree1.getData()!=tree2.getData()){
			return false;
		}
		//now the roots are equal.Test left tree and right tree
		return tree1HaveAllNodesOfTree2(tree1.getLeft(),tree2.getLeft())&&
			tree1HaveAllNodesOfTree2(tree1.getRight(),tree2.getRight());
	}
	
	public static boolean hasSubtreeByOrder(Node tree1,Node tree2){
		StringBuilder sb=new StringBuilder();
		preOrder(tree1,sb);
		String preOrderOfTree1=sb.toString();
		
		sb.setLength(0);
		
		preOrder(tree2,sb);
		String preOrderOfTree2=sb.toString();
		if(preOrderOfTree1.indexOf(preOrderOfTree2)==-1){
			return false;
		}
		
		sb.setLength(0);
		inOrder(tree1,sb);
		String inOrderOfTree1=sb.toString();
		
		sb.setLength(0);
		inOrder(tree2,sb);
		String inOrderOfTree2=sb.toString();
		
		return inOrderOfTree1.indexOf(inOrderOfTree2)!=-1;
	}
	public static void preOrder(Node node,StringBuilder sb){
		if(node==null){
			return;
		}
		sb.append(node.getData()+",");
		preOrder(node.getLeft(),sb);
		preOrder(node.getRight(),sb);
	}
	public static void inOrder(Node node,StringBuilder sb){
		if(node==null){
			return;
		}
		inOrder(node.getLeft(),sb);
		sb.append(node.getData()+",");
		inOrder(node.getRight(),sb);
	}
}

java-50-输入两棵二叉树A和B,判断树B是不是A的子结构

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
4.3 B树 虽然一级或两级索引通常有助于加快查询,但在商用系统中常使用一种更通用的结构。这 一通用
2 B树
在20世纪80年代初,典型数据库的规模为10~100 MB,而三十年后的今天,典型数据库的规模已需要以TB为
3 B树
首先本文参考了其他一些博客,在此列出,表示感谢:   http://blog.csdn.net/v_july_v/article/de
4 B树
http://blog.csdn.net/fyplinux/archive/2008/12/03/3434347.aspx B树、B-树、B+树、B*树详解 B树
5 B树
一棵B树T是具有如下性质的有根树(设根为root): 1.每个节点x有一下域: (a)num,当前存储在节点x
6 B树
即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3
7 B 树
度:一个结点的子树个数称为该结点的 度 ( Degree ),一棵树的度是指该树中结点最大的 度数 深度:
8 B树
二叉排序树或者二叉搜索树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.
9 B 树
0)引论 大多数的查找树都是二叉树,这个可以理解,因为二叉树相对来说比较简单,易行,用递归方式
10 B树
用阶定义的B树 B树又叫平衡多路查找树。一棵m阶的B树的特性如下: 树中每个结点最多含有m个孩子(m
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号