前面介绍学习的大多是线性表相关的内容,把指针搞懂后其实也没有什么难度。规则相对是简单的。
再数据结构中树、图才是数据结构标志性产物,(线性表大多都现成api可以使用),因为树的难度相比线性表大一些并且树的拓展性很强,你所知道的树、二叉树、二叉排序树,AVL树,线索二叉树、红黑树、B数、线段树等等高级数据结构。然而二叉排序树是所有的基础,所以彻底搞懂二叉排序树也是非常重要的。
参考王道数据结构
二叉树也是树的一种,而二叉排序树又是二叉树的一种。
相关性质:
二叉树是一树的一种,但应用比较多,所以需要深入学习。二叉树的每个节点最多只有两个节点。
二叉树与度为2的树的区别:
几种特殊二叉树:
二叉树性质:
相比树,二叉树的性质就是树的性质更加具体化。
概念
前面铺垫那么多,咱们言归正传,详细实现一个二叉排序树。首先要了解二叉排序树的规则:
构造
首先二叉排序树是由若干节点构成。
node类构造为:
class node {//结点 public int value; public node left; public node right; public node() { } public node(int value) { 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; } }
既然节点构造好了,那么就需要节点等其他信息构造成树。有了链表构造经验,很容易得知一棵树最主要的还是root根节点。
所以树的构造为:
public class BinarySortTree { node root;//根 public BinarySortTree() {root=null;} public void makeEmpty()//变空 {root=null;} public boolean isEmpty()//查看是否为空 {return root==null;} //各种方法 }
主要方法
findmax(),findmin()
findmin()找到最小节点:
findmax()找到最大节点:
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)); }
isContains(int x)
这里的意思是查找二叉查找树中是否存在x。
public boolean isContains(int x)//是否存在 { node current=root; if(root==null) {return false;} while(current.value!=x&¤t!=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; }
insert(int x)
插入的思想和前面isContains类似。找到自己的位置(空位置)插入。但是又不太一样。你可能会疑问为什么不直接找到最后一个空,然后将current赋值过去current=new node(x)。这样的化current就相当于指向一个new node(x)节点。和树就脱离关系,所以要提前判定是否为空,若为空将它的left或者right赋值即可。
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;//其中用不到 }
delete(int x)
删除操作算是一个相对较难理解的操作了。
删除节点规则:
删除的节点没有子孙:
左节点为空、右节点为空:
左右节点均不空
所以整个删除算法流程为:
代码为
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; }
完整代码
二叉排序树完整代码为:
package 二叉树; import JAVA.util.ArrayDeque; import java.util.Queue; import java.util.Stack; public class BinarySortTree { class node {// 结点 public int value; public node left; public node right; public node() { } public node(int value) { 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; } }