数据构架与算法—二叉排序树(java)(2)

this.value = value;

this.left = null;

this.right = null;

}

public node(int value, node l, node r) {

this.value = value;

this.left = l;

this.right = r;

}

}

node root;// 根

public BinarySortTree() {

root = null;

}

public void makeEmpty()// 变空

{

root = null;

}

public boolean isEmpty()// 查看是否为空

{

return root == null;

}

public node findmin(node t)// 查找最小返回值是node，调用查看结果时应该.value

{

if (t == null) {

return null;

} else if (t.left == null) {

return t;

} else

return (findmin(t.left));

}

public node findmax(node t)// 查找最大

{

if (t == null) {

return null;

} else if (t.right == null) {

return t;

} else

return (findmax(t.right));

}

public boolean isContains(int x)// 是否存在

{

node current = root;

if (root == null) {

return false;

}

while (current.value != x && current != null) {

if (x < current.value) {

current = current.left;

}

if (x > current.value) {

current = current.right;

}

if (current == null) {

return false;

} // 在里面判断即使超直接返回

}

// 如果在这个位置判定是否为空会导致current.value不存在报错

if (current.value == x) {

return true;

}

return false;

}

public node insert(int x)// 插入 t是root的引用

{

node current = root;

if (root == null) {

root = new node(x);

return root;

}

while (current != null) {

if (x < current.value) {

if (current.left == null) {

return current.left = new node(x);}

else current = current.left;}

else if (x > current.value) {

if (current.right == null) {

return current.right = new node(x);}

else current = current.right;

}

}

return current;//其中用不到

}

public node remove(int x, node t)// 删除节点

{

if (t == null) {

return null;

}

if (x < t.value) {

t.left = remove(x, t.left);

} else if (x > t.value) {

t.right = remove(x, t.right);

} else if (t.left != null && t.right != null)// 左右节点均不空

{

t.value = findmin(t.right).value;// 找到右侧最小值替代

t.right = remove(t.value, t.right);

} else // 左右单空甚至左右都空

{

if (t.left == null && t.right == null) {

t = null;

} else if (t.right != null) {

t = t.right;

} else if (t.left != null) {

t = t.left;

}

return t;

}

return t;

郑州不孕不育医院:郑州不孕不育医院哪家好:郑州不孕不育医院排行:

结语

这里我们优先学习了树，二叉树，以及二叉搜素树的基本构造。对于二叉搜素树插入查找非常容易理解之后实现的过后要切记函数对参数的引用之类。需要认真考量。

而偏有难度的是二叉树的删除，利用一个递归的观念，要找到特殊状况和普通情况，递归一定程度也有弊端的转换(转成自己同样问题，作用域减小)需要思考。

下面还会介绍二叉搜素树的三序遍历(递归和非递归).和层序遍历。需要的朋友请持续关注。另外，笔者数据结构专栏欢迎查房。!

如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流：bigsai。回复爬虫，数据结构等有精美资料一份。

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-121391-2.html