# 数据结构-二叉查找树添加 删除 遍历

```package com.structures.tree;

import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.Stack;

/*
* Binary Search Tree
*/
public class Searchtree {
public Integer data;
public Searchtree left;
public Searchtree right;

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

public Searchtree(Integer number) {
this.data = number;
}

public void setLeft(Searchtree left) {
this.left = left;
}

public void setRight(Searchtree right) {
this.right = right;
}

if (number <= this.data)
else
}

private void add(int number, Searchtree father, Searchtree child, int tag) {
if (child == null) {
child = new Searchtree(number);
if (tag == 0)
father.setLeft(child);
else
father.setRight(child);
} else {
// attention: here must be child
if (number <= child.data)// add to left
else

}
}

// find
public Searchtree find(int number) {
if (number < data) {
return find(number, this);
} else if (number > data) {
return find(number, this);
} else {
return find(number, this);
}
}

private Searchtree find(int number, Searchtree tree) {
if (tree == null)
throw new NoSuchElementException(
"no such element in the binary search tree");
if (number < tree.data) {
return find(number, tree.left.left);
} else if (number > tree.data) {
return find(number, tree.right);
} else
return tree;
}

// findPrevious
private ArrayList<Searchtree> trees = new ArrayList<Searchtree>();

private Searchtree findPrevious(int number, Searchtree tree) {
if (tree == null)
throw new NoSuchElementException(
"no such element in the binary search tree");
if (number < tree.data) {
return findPrevious(number, tree.left);
} else if (number > tree.data) {
return findPrevious(number, tree.right);
} else {
Searchtree pre = trees.get(trees.size() - 2);
trees = null;
return pre;
}
}

// min
public Searchtree findMin(Searchtree 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);

}

// max
public Searchtree findMax(Searchtree 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);
}

public Searchtree remove(int number) {
return remove(number, this);
}
/*remove
*  是最困难的，请大家参考一下，递归有点晕。大家阅读书理解吧。
*  参考代码：《数据结构与算法分析》-C语言描述 英文版
*  第102-103页
* ISBN: 9787115139849
* detail：http://book.douban.com/subject/1444648/
*/
public Searchtree remove(int number, Searchtree tree) {
Searchtree 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
} else if (tree.left != null && tree.right != null) {
// two children
// replace with the smallest in right tree
delete = findMin(tree.right);
tree.setData(delete.data);
tree.setRight(remove(tree.data, tree.right));
delete = null;
} else {
// one or zero child
delete = tree;
if (delete.left == null) {
tree = tree.right;
} else if (delete.right == null) {
tree = tree.left;
}
delete = null;
}

return tree;
}

// 先序遍历 preorder traversal
public void preorder() {
System.out.print(data + " ");
if (left != null)
left.preorder();
if (right != null)
right.preorder();

}

// 中序遍历 inorder traversal
public void inorder() {
if (left != null)
left.inorder();
System.out.print(data + " ");
if (right != null)
right.inorder();

}

// 后序遍历 postorder traversal
public void postorder() {
if (left != null)
left.postorder();

if (right != null)
right.postorder();
System.out.print(data + " ");
}

public int getDepth(Searchtree root) {
int depth;
if (root == null)
return 0;
else {
depth = 1 + Math.max(getDepth(root.left), getDepth(root.right));
return depth;
}
}

public static void main(String[] args) {
Searchtree tree = new Searchtree(5);
tree.remove(1);
// tree.remove(2, tree);
//tree.remove(tree.data);
tree.preorder();
System.out.println();
tree.inorder();
System.out.println();
System.out.println(tree.getDepth(tree));
System.out.println(tree.find(7).data);
System.out.println(tree.findPrevious(8, tree).data);

}

}
//该片段来自于http://outofmemory.cn
```

0人收藏

0

0