所谓二叉树,就是一个节点最多只能有两个子节点,而二叉搜索树就是一个经典并简单的二叉树.规则是一个节点的左子节点一定比自己小,右子节点一定大于等于自己(当然也可以反过来).在树基本平衡的时候插入,搜索和删除速度都很快,时间复杂度为O(logN).但是,如果插入的是有序的数据,那效率就会变成O(N),在这个时候,树其实变成了一个链表.
tree代码:
public class Tree {
private Node root;
/**
* 插入节点
* @param data
*/
public void insert(int data){
Node node = new Node(data);
if(this.root == null){
this.setRoot(node);
return;
}
Node current = this.root;
while(true){
if(current.getData() > data){
if(current.hasLeft()){
current = current.getLeft();
}else{
current.setLeft(node);
return;
}
}else if(current.getData() < data){
if(current.hasRight()){
current = current.getRight();
}else{
current.setRight(node);
return;
}
}else{
return;
}
}
}
/**
* 删除节点
* @param key
*/
public void remove(int key){
Node node = this.findNode(key);
if(node == null){
return;
}
Node parent = node.getParent();
//要删除的节点没有子节点
if(!node.hasLeft() && !node.hasRight()){
if(parent == null){
this.setRoot(null);
}else if(node.isLeft()){
parent.setLeft(null);
}else{
parent.setRight(null);
}
//要删除的节点只有一个子节点
}else if(!node.hasRight() || !node.hasLeft()){
Node child = node.hasLeft() ? node.getLeft() : node.getRight();
if(parent == null){
this.setRoot(child);
}else if(node.isLeft()){
parent.setLeft(child);
}else{
parent.setRight(child);
}
//要删除的节点有两个子节点
}else{
Node successor = this.getSuccessor(node);
if (parent == null) {
this.setRoot(successor);
} else if (node.isLeft()) {
parent.setLeft(successor);
} else {
parent.setRight(successor);
}
}
}
/**
* 查找
* @param key
*/
public void find(int key){
Node node = this.findNode(key);
if(node != null){
System.out.println("node data is : " + node.getData());
}
}
/**
* 查找节点
* @param key
* @return
*/
private Node findNode(int key){
Node current = this.root;
while(current.getData() != key){
if(current.getData() > key){
if(current.hasLeft()){
current = current.getLeft();
}else{
return null;
}
}else if(current.getData() < key){
if(current.hasRight()){
current = current.getRight();
}else{
return null;
}
}
}
return current;
}
/**
* 找到继任节点,找出删除节点中右树最小的节点,如果删除节点的右节点
* 没有子节点,则返回null
* @param node
* @return
*/
private Node getSuccessor(Node node){
Node current = node.getRight();
while(current.hasLeft()){
current = current.getLeft();
}
if(node.getRight() != current){
Node parent = current.getParent();
if(current.hasRight()){
parent.setLeft(current.getRight());
}else{
parent.setLeft(null);
}
current.setRight(node.getRight());
}
current.setLeft(node.getLeft());
return current;
}
private void setRoot(Node node){
this.root = node;
if(node != null){
node.setParent(null);
}
}
}
node代码:
public class Node {
private int data;
private Node left;
private Node right;
private Node parent;
public Node(int data){
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
if(this.left != null){
this.left.parent = this;
}
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
if(this.right != null){
this.right.parent = this;
}
}
public boolean hasRight(){
return this.right != null;
}
public boolean hasLeft(){
return this.left != null;
}
public boolean isRoot(){
return this.parent == null;
}
public boolean isRight(){
return this.parent.right == this;
}
public boolean isLeft(){
return this.parent.left == this;
}
}
分享到:
相关推荐
算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、二叉树、二叉搜索树 算法面试通关40讲完整课件 18-20 树、...
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:1.若它的左子树非空,则左子树上所有结点的值均小于根结点的值;2.若它的右...
二叉搜索树(BST)是一种常见的二叉树结构,它具有有序性质,使得在插入、删除和搜索操作上非常高效。本教程将向您展示如何使用Java编写代码来执行二叉搜索树的插入操作。我们将提供一个简单而清晰的示例,以帮助您...
用c语言编写的数据结构相关的二叉树的二叉搜索
剑指Offer(Python多种思路实现):二叉搜索树的第K大节点 面试54题: 题目:二叉搜索树的第K大节点 题:给定一颗二叉搜索树,请找出其中的第k小的结点。例如, 5 / \ 3 7 /\ /\ 2 4 6 8 中,按结点数值大小顺序第三个...
大连理工大学数据结构上机 二叉树三种遍历,先序和中序建立二叉树,后序和中序建立二叉树,二叉搜索树查找,删除,插入
二叉树、二叉搜索树的构建,前序、中序、后序的 递归和非递归遍历;前序中序序列构建二叉树……
二叉平衡树:若不是空树,则(1)左右子树都是平衡二叉树;(2)左右子树的深度之差的绝对值不超过1。 本次实验是利用二叉排序树和平衡二叉树达到以下目的:(1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉...
该程序是在VC2005下基于二叉搜索树实现的,主要功能包括查找、删除、添加、修改等基本操作,另外还有关于MFC位图显示,文件读写的操作
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度
主要介绍了C语言判定一棵二叉树是否为二叉搜索树的方法,结合实例形式综合对比分析了C语言针对二叉搜索树判定的原理、算法、效率及相关实现技巧,需要的朋友可以参考下
最优二叉搜索树详细的分析了最优二叉树的伪代码以及给出了算法设计,还包含一个例子用来更好的理解最优二叉搜索树的流程
二叉搜索树判断的ppt有动画,有递归讲解,二叉搜索树判断的ppt有动画,有递归讲解,十分详细,适合要做演示的老师和同学 二叉搜索树判断的ppt有动画,有递归讲解,二叉搜索树判断的ppt有动画,有递归讲解,十分详细,...
数据结构二叉树二叉搜索树堆相关C++代码.docx
「剑指 Offer 54. 二叉搜索树的第k大节点」思路:二叉搜索树,是具有下列性质的二叉树:1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
二叉搜索树是一种特殊的二叉树,它的每个节点的左子树中的所有元素都小于该节点,而右子树中的所有元素都大于该节点。 二叉搜索树的特性 二叉搜索树具有一些重要特性,如有序性、唯一性和高度平衡性,这些特性使得它...
二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树...