二叉搜索树实例练习

一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表结构表示,其中每一个结点都是一个对象。结点中除了数据外,还包括域left,right和p,它们分别指向结点的左儿子、右儿子,如果结点不存在,则为NULL。
它或者是一棵空树;或者是具有下列性质的二叉树:
1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉查找树;
显然满足了上面的性质,那么二叉查找树按中序遍历就是按从小到大的顺序遍历,这也就是为什么叫排序树的原因,当然上面的小于和大于都可以根据自己的需求改变的。
二叉查找树的几个常用操作:查找,删除,插入.
HDU 3791:
Problem Description
判断两序列是否为同一二叉搜索树序列
Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
Output
如果序列相同则输出YES,否则输出NO
Sample Input
2
567432
543267
576342
0
Sample Output
YES
NO
解释:按顺序插入数字之后,再用二叉树先序遍历判断两颗二叉树是否相同。
Java代码


复制代码 代码如下:

import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner in=new Scanner(System.in);
BinarySearchTree<Character> root=null;
while(in.hasNext()){
int t=in.nextInt();
if(t==0) break;
root=new BinarySearchTree<Character>();
String result=null;
String result1=null;
String s=in.next();
for(int i=0;i<s.length();i++){
root.insert(s.charAt(i));
}
result=root.printTree(root.getRoot());
for(int i=0;i<t;i++){
root=new BinarySearchTree<Character>();
s=in.next();
for(int j=0;j<s.length();j++){
root.insert(s.charAt(j));
}
result1=root.printTree(root.getRoot());
if(result.equals(result1)) System.out.println("YES");
else System.out.println("NO");
}
}
}
}
class BinaryNode< T extends Comparable<T>> {//二叉查找树节点
BinaryNode< T> left;
BinaryNode< T> right;
T element;
public BinaryNode(T theElement){
this(theElement, null, null);
}
public BinaryNode(T theElement, BinaryNode lt, BinaryNode rt){
element = theElement;
left = lt;
right = rt;
}
public T getElement(){
return this.element;
}
public BinaryNode< T> getLeft(){
return this.left;
}
public BinaryNode< T> getRight(){
return this.right;
}
public String toString(){
return element + "";
}
}
class BinarySearchTree< T extends Comparable<T>>{//二叉搜索树
private BinaryNode< T> root;//根节点
public BinarySearchTree(){//构造函数
root = null;
}
public BinarySearchTree(BinaryNode< T> t){//构造函数
root = t;
}
public void makeEmpty(){
root = null;
}
public boolean isEmpty(){
return root == null;
}
public BinaryNode<T> getRoot(){
return root;
}
public T find(T x){
return find(x, root).element;
}
public void insert(T x){
root = insert(x, root);
}
public void printTree(){
printTree(root);
}
private BinaryNode< T> find(T x, BinaryNode< T> t){//查找操作
if(t == null){
return null;
}
if(x.compareTo(t.element) < 0){
return find(x, t.left);
}
else if(x.compareTo(t.element) == 0){
return t;
}
else{
return find(x, t.right);
}
}
private BinaryNode< T> insert(T x, BinaryNode< T> t){//插入操作
if(t == null){
t = new BinaryNode< T>(x, null, null);
}
else if(x.compareTo(t.element) < 0){
t.left = insert(x, t.left);
}
else if(x.compareTo(t.element) > 0){
t.right = insert(x, t.right);
}
else;
return t;
}
private StringBuffer sb=new StringBuffer();
public String printTree(BinaryNode< T> t){//前序遍历二叉查找树
if(t != null){
sb.append(t.element);
printTree(t.left);
printTree(t.right);
}
return sb.toString();
}
}

时间: 2012-11-24

C#创建二叉搜索树的方法

本文实例讲述了C#创建二叉搜索树的方法.分享给大家供大家参考.具体如下: public static BinaryTreeNode BuildBinarySearchTree(int[] sortedArray) { if (sortedArray.Length == 0) return null; int _mid = sortedArray.Length / 2; BinaryTreeNode _root = new BinaryTreeNode(sortedArray[_mid]); in

C#二叉搜索树插入算法实例分析

本文实例讲述了C#二叉搜索树插入算法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data; } } public void

二叉搜索树源码分享

复制代码 代码如下: #include <iostream>using namespace std; //枚举类,前中后三种遍历方式enum ORDER_MODE{ ORDER_MODE_PREV = 0, ORDER_MODE_MID, ORDER_MODE_POST}; //树节点的结构体template <class T>struct BinaryNode{ T    element; BinaryNode  *left; BinaryNode  *right; Binary

Python实现二叉搜索树

二叉搜索树 我们已经知道了在一个集合中获取键值对的两种不同的方法.回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的.我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表.在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效率. 搜索树操作 在我们研究这种实现方式之前,让我们回顾一下ADT MAP提供的接口.我们会注意到,这种接口和Python的字典非常相似. Map() 创建了一个新的

Python二叉搜索树与双向链表转换实现方法

本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

Java 实现二叉搜索树的查找、插入、删除、遍历

由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出- 学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找.插入.删除.遍历等内容. 二叉搜索树需满足以下四个条件: 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 任意节点的左.右子

javascript数据结构之二叉搜索树实现方法

本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg

二叉搜索树的插入与删除(详细解析)

题目:创建一个类,类中的数据成员时一棵二叉搜索树,对外提供的接口有添加结点和删除结点这两种方法.用户不关注二叉树的情况.要求我们给出这个类的结构以及实现类中的方法. 思路添加结点:添加结点其实很容易,我们只需要找到结点所行对应的位置就可以了,而且没有要求是平衡的二叉搜索树,因此每次添加结点都是在叶子结点上操作,不需要修改二叉搜索树整体的结构.要找出添加节点在二叉搜索树中的位置,可以用一个循环解决.判断插入结点与当前头结点的大小,如果大于头结点则继续搜索右子树,如果小于头结点则继续搜索左子树.直到

java实现 二叉搜索树功能

一.概念 二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现Comparator接口,在本文中为了方便,采用了int类型数据进行操作. 要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作. 二.二叉搜索树构建 谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点.左节点.右节点这四个属性,代码如下 sta

Java创建二叉搜索树,实现搜索,插入,删除的操作实例

Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除) 首先我们要有一个编码的思路,大致如下: 1.查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走! 2.插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致. 3.删除: 1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树:当被删节点

Java删除二叉搜索树的任意元素的方法详解

本文实例讲述了Java删除二叉搜索树的任意元素的方法.分享给大家供大家参考,具体如下: 一.删除思路分析 在删除二叉搜索树的任意元素时,会有三种情况: 1.1 删除只有左孩子的节点 节点删除之后,将左孩子所在的二叉树取代其位置:连在原来节点父亲元素右节点的位置,比如在图中需要删除58这个节点. 删除58这个节点后,如下图所示: 1.2 删除只有右孩子的节点: 节点删除之后,将右孩子所在的二叉树取代其位置:连在原来节点的位置,比如在下图中需要删除58这个节点. 删除58这个节点后,如下图所示: 这

Java删除二叉搜索树最大元素和最小元素的方法详解

本文实例讲述了Java删除二叉搜索树最大元素和最小元素的方法.分享给大家供大家参考,具体如下: 在前面一篇<Java二叉搜索树遍历操作>中完成了树的遍历,这一节中将对如何从二叉搜索树中删除最大元素和最小元素做介绍: 我们要想删除二分搜索树的最小值和最大值,就需要先找到二分搜索树的最小值和最大值,其实也还是很容易的,因为根据二叉搜索树的特点,它的左子树一定比当前节点要小,所以二叉搜索树的最小值一定是左子树一直往下走,一直走到底.同样在二叉搜索树中,右子树节点值,一定比当前节点要大,所以右子树一直

javascript算法之二叉搜索树的示例代码

什么是二叉树 二叉树就是树的每个节点最多只能有两个子节点 什么是二叉搜索树 二叉搜索树在二叉树的基础上,多了一个条件,就是二叉树在插入值时,若插入值比当前节点小,就插入到左节点,否则插入到右节点:若插入过程中,左节点或右节点已经存在,那么继续按如上规则比较,直到遇到一个新的节点. 二叉搜索树的特性 二叉搜索树由于其独特的数据结构,使得其无论在增删,还是查找,时间复杂度都是O(h),h为二叉树的高度.因此二叉树应该尽量的矮,即左右节点尽量平衡. 二叉搜索树的构造 要构造二叉搜索树,首先要构造二叉树