文档章节

二叉树的排序(转摘)

许雷神
 许雷神
发布于 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
06/03
0
0
平衡二叉树(AVL)树

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

笨拙的小Q
2016/07/02
36
0
数组、链表等常用数据结构和集合浅解(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/qq_34173549/article/details/79897957 数组、链表等常用数据结构和集合浅解(java) 脑子转了一圈,巴拉巴拉...

追风筝的猪
04/11
0
0
编程题——1~10

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

thanatos_y
2016/07/19
3
0
JavaScript实现排序二叉树的基本操作

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

a独家记忆
06/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

MySQL 数据库中间件 MyCAT 基础解析

前言 网络应用持续扩张的过程中,为了处理海量数据往往首先遇到的挑战就是数据存储的扩展 数据存储的扩展一般以切分来实现,切分的技术实现又可分为垂直切分和水平切分: 以表(或Schema)为切...

PeakFang-BOK
33分钟前
1
0
Linux Mysql 安装

https://www.cnblogs.com/xinjing-jingxin/p/8025805.html

流氓兔-
59分钟前
1
0
GlusterFS强制删除节点

GlusterFS中,修改了节点名称,导致找不到了,想删除掉重新加入。 没想到,gluster peer detach server02方法失败,竟然用了各种方法都删除不掉,提示节点无效(废话!有效的我还要删除么?!...

openthings
今天
3
0
光纤技术取得突破,互联网速度或可提高100倍

据外媒报道,近日发表在《自然通讯》上的一篇文章称,通过检测扭曲成螺旋状的光线,互联网速度可以提高 100 倍。这项研究可用于轻松升级现有的网络,大幅提高传输效率。 光纤线缆使用光脉冲来...

linux-tao
今天
2
0
day150-2018-11-17-英语流利阅读-待学习

歪果仁也疯狂:海外版抖音的征途 毛西 2018-11-17 1.今日导读 海外版抖音 TikTok 于 2017 年 5 月上线海外,至今覆盖全球 150 多个国家和地区,月活跃用户数已突破 5 亿。然而,“出海”的抖...

飞鱼说编程
今天
11
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部