Skip to content

caven #9

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
wfcaven wants to merge 1 commit into
base: master
Choose a base branch
from
Open

caven #9

Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
164 changes: 164 additions & 0 deletions 1-二叉树/1-二叉查找树BST/caven
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,164 @@
package algorithm;

import java.util.NoSuchElementException;

//二叉树的操作类
public class BiSearchTree {
public static BiSearchTNode root=new BiSearchTNode();
//create 创建二叉查找树
public static BiSearchTNode create(int[] number){
root.setData(number[0]);
for (int i = 1; i < number.length; i++) {
insert(number[i]);
}
return root;
}

//insert 插入一个新的值到已存在的二叉查找树中
public static void insert(int number) {
if (root.getData()>number){
add(number, root, root.getlChild(), 0);
}
else{
add(number, root, root.getrChild(), 1);
}
}
private static void add(int number, BiSearchTNode father, BiSearchTNode child, int tag) {
if (child == null) {
child = new BiSearchTNode(number);
if (tag == 0){
father.setlChild(child);
}
else{
father.setrChild(child);
}
} else {
if (number <= child.getData()){
add(number, child, child.getlChild(), 0);
}
else{
add(number, child, child.getrChild(), 1);
}

}
}

//search 通过值查找一个节点
public static BiSearchTNode search(int number) {
if (root.getData()>number) {
return find(number, root.getlChild());
} else {
return find(number, root.getrChild());
}
}
private static BiSearchTNode find(int number, BiSearchTNode tree) {
if (tree == null)
throw new NoSuchElementException("二叉树中不存在该值");
if (tree.getData()>number) {
return find(number, tree.getlChild());
} else if (tree.getData()<number) {
return find(number, tree.getrChild());
} else{
return tree;
}
}

//delete 通过值删除一个节点
//有点错误，到现在还没解决，先提交作业，就差这一个了。
public static BiSearchTNode delete(int number) {
return remove(number, root);
}
private static BiSearchTNode remove(int number, BiSearchTNode tree) {
if (tree == null)
throw new NoSuchElementException("二叉树中不存在该值");
if (tree.getData()>number) {
remove(number, tree.getlChild());
} else if (tree.getData()<number) {
remove(number, tree.getrChild());
} else{
deleteAll(tree);
}
return tree;
}
private static void deleteAll(BiSearchTNode tree) {
if(tree!=null){
deleteAll(tree.getlChild());
deleteAll(tree.getrChild());
tree=null;
}
}

//中序遍历
public static void InOrderTraverse(BiSearchTNode node){
if(node!=null){
InOrderTraverse(node.getlChild());
System.out.print(node.getData()+" - ");
InOrderTraverse(node.getrChild());
}
}

public static void main(String [] args) throws Exception{
System.out.println("===创建树===");
int[] ints={5, 9, 2, 1, 4, 7, 6, 8};
create(ints);
InOrderTraverse(root);
System.out.println("");
System.out.println("===插入一个新的值 3===");
insert(3);
InOrderTraverse(root);
System.out.println("");
System.out.println("===查找一个值 4===");
BiSearchTNode tree=search(4);
System.out.println(tree.getData());
System.out.println("===删除一个值 3===");
InOrderTraverse(delete(3));
}
}

//二叉树对象
class BiSearchTNode{
private int data;
private BiSearchTNode lChild=null;
private BiSearchTNode rChild=null;

public BiSearchTNode() {
}

public BiSearchTNode(int data){
this.data = data;
}

public BiSearchTNode(int data,BiSearchTNode lChild,BiSearchTNode rChild){
this.data = data;
this.lChild = lChild;
this.lChild = lChild;
}


public int getData() {
return data;
}

public BiSearchTNode getlChild() {
return lChild;
}

public void setlChild(BiSearchTNode lChild) {
this.lChild = lChild;
}

public BiSearchTNode getrChild() {
return rChild;
}

public void setrChild(BiSearchTNode rChild) {
this.rChild = rChild;
}

public void setData(int data) {
this.data = data;
}



}