文档章节

二叉树的排序(转摘)

许雷神
 许雷神
发布于 2015/05/15 00:52
字数 504
阅读 9
收藏 0
import java.util.NoSuchElementException;


public class BST {
	public Integer data;
	public BST left;
	public BST right;
	
	public BST(Integer data){
		this.data = data;
	}
	
	//add
	public void add(Integer number){
		if(number < data){
			add(number, this, this.left, 0);
		}else{
			add(number, this, this.right, 1);
		}
	}
	
	private void add(Integer number, BST father, BST child, int tag){
		if(child == null){
			child = new BST(number);
			if(tag == 0){
				father.setLeft(child);
			}else{
				father.setRight(child);
			}
		}else{
			if(number < child.data){
				// add to left
				add(number, child, child.left, 0);
			}else{
				// add to right
				add(number, child, child.right, 1);
			}
		}
	}

	//find
	public BST find(Integer number){
		return find(number, this);
	}
	
	private BST find(Integer number, BST tree){
		if(tree == null){
			throw new NoSuchElementException("no such element in the binary search tree");
		}
		if(number < tree.data){
			return find(number, tree.left);
		}else if(number > tree.data){
			return find(number, tree.right);
		}else
			return tree;
	}
	
	//find minimum
	public BST findMin(BST tree){
		if(tree == null){
			throw new NoSuchElementException("no such element in the binary search tree");
		}else if(tree.left == null){
			return tree;
		}else
			return findMin(tree.left);
	}
	
	//find maximal
	public BST findMax(BST tree){
		if(tree == null){
			throw new NoSuchElementException("no such element in the binary search tree");
		}else if(tree.right == null){
			return tree;
		}else
			return findMax(tree.right);
	} 
	
	//remove
	public BST remove(Integer number, BST tree){
		BST delete = null;
		if (tree == null){
			throw new IndexOutOfBoundsException("tree size is 0");
		} else if(number < tree.data){
			// go left
			tree.left = remove(number, tree.left);
		} else if (number > tree.data) {
			// go right
			tree.right = remove(number, tree.right);
			// found element to be remove(recursion)
		} else if(tree.left != null && tree.right != null) {
			delete = findMin(tree.right);
			tree.setData(delete.data);
			tree.setRight(remove(tree.data,tree.right));
			delete = null;
			// one or zero child
		} else {
			delete = tree;
			if(tree.left == null){
				tree = tree.right;
			}else if(tree.right == null){
				tree = tree.left;
			}
			delete = null;
		}
		return tree;
	}
	
	//get depth
	public int getDepth(BST root){
		if( root == null){
			return 0;
		}else{
			return 1 + Math.max(getDepth(root.left), getDepth(root.right));
		}
	}
	
	//print previous order 先序遍历 中->左->右
	public void printPreOrder(){
		System.out.print(data + " ");
		if(left != null)
			left.printPreOrder();
		if(right != null)
			right.printPreOrder();
	}
	//print middle order 中序遍历 左->中->右
	public void printMidOrder(){
		if(left != null)
			left.printMidOrder();
		System.out.print(data + " ");
		if(right != null)
			right.printMidOrder();
	}
	//print post order 后序遍历 左->右->中
	public void printPostOrder(){
		if(left != null)
			left.printPostOrder();
		if(right != null)
			right.printPostOrder();
		System.out.print(data + " ");
	}
	//print level
	public void printLevelOrder(int flag){
		if(flag == 0)
			System.out.print(data + " ");
		if(left != null)
			System.out.print(left.data + " ");
		if(right != null)
			System.out.print(right.data + " ");
		
		if(left != null)
			left.printLevelOrder(1);
		if(right != null)
			right.printLevelOrder(1);
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BST tree = new BST(37);
		tree.add(24);
		tree.add(42);
		tree.add(32);
		tree.add(7);
		tree.add(40);
		tree.add(2);
		tree.add(42);
		tree.add(120);
		System.out.println("Depth is: "+tree.getDepth(tree));
		System.out.print("Privious: ");
		tree.printPreOrder();
		System.out.println();
		
		System.out.print("Middle  : ");
		tree.printMidOrder();
		System.out.println();
		
		System.out.print("Post    : ");
		tree.printPostOrder();
		System.out.println();
		
		System.out.print("Level   : ");
		tree.printLevelOrder(0);
		System.out.println();
		
	}

	public Integer getData() {
		return data;
	}
	public void setData(Integer data) {
		this.data = data;
	}
	public BST getLeft() {
		return left;
	}
	public void setLeft(BST left) {
		this.left = left;
	}
	public BST getRight() {
		return right;
	}
	public void setRight(BST right) {
		this.right = right;
	}
}


本文转载自:#

共有 人打赏支持
许雷神
粉丝 7
博文 13
码字总数 0
作品 0
广州
私信 提问
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
2018/06/03
0
0
平衡二叉树(AVL)树

1、平衡二叉树定义 是一种二叉排序树(二叉查找树、二叉搜索树),其中每个节点的左子树和右子树的高度差不大于1。(左右子树也是平衡二叉树) 平衡因子BF = 二叉树节点的左子树深度减去右子...

笨拙的小Q
2016/07/02
36
0
JavaScript实现排序二叉树的基本操作

记得一开始学习数据结构用的是c语言实现,学了这么久前端就想用JavaScript来实现一下,顺便复习下数据结构。 先来了解下什么是排序二叉树,排序二叉树是具有以下特点的二叉树 若左子树不空,...

a独家记忆
2018/06/29
0
0
编程题——1~10

一、CMyString类的实现(主要是构造函数、拷贝构造函数、赋值运算符、异常安全性) 二、Singleton的实现 1、ns3里的实现 实现程序如下: 2、《C++设计新思维》第6章 多线程实现程序如下: 三...

thanatos_y
2016/07/19
3
0
堆排序 最大堆 最小堆 Java实现

堆排序啊,其实是一种数据结构,二叉树,二叉树分为是满二叉树和完全二叉树。一棵深度为 k,且有 2k - 1 个节点称之为满二叉树,完全二叉树:深度为 k,有 n 个节点的二叉树,当且仅当其每一...

豆芽菜橙
2018/07/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

centos7安装RabbitMQ详细过程

由于RabbitMQ是基于Erlang语言开发,所以在安装RabbitMQ之前,需要先安装Erlang 1、环境: centos 7.1 内核版本3.10.0-229.el7.x86_64 Erlang 19.0.4版本 RabbitMQ 3.6.14版本 2、在线安装E...

秋至丶枫以落
4分钟前
0
0
6个使用KeePassX保护密码的技巧

虽然安全是个深奥的主题,但是你可以遵循几个简单的日常习惯来减小攻击面。本文将解释确保密码信息安全的重要性,并给出如何充分利用KeePassX的建议。 日益互联的数字世界使安全成为一个重要...

Linux就该这么学
6分钟前
0
0
2018最佳GAN论文回顾(下)

继上一篇《2018最佳GAN论文回顾(上)》,我又继续介绍了一个对于GAN的基于样式的生成器体系结构的新论文,提出了一个新的模型来应对这种挑战。 一种用于生成式对抗网络的基于生成器体系结构...

阿里云官方博客
8分钟前
0
0
UnsatisfiedLinkError sawindbg.dll

方法:搜索sawindbg.dll,然后将文件报错的目录下

洛水
45分钟前
4
0
说说不知道的Golang中参数传递

本文由云+社区发表 导言 几乎每一个C++开发人员,都被面试过有关于函数参数是值传递还是引用传递的问题,其实不止于C++,任何一个语言中,我们都需要关心函数在参数传递时的行为。在golang中...

腾讯云加社区
45分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部