前言
再数据结构中树、图才是数据结构标志性产物,(线性表大多都现成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;} elsereturn (findmin(t.left));}public node findmax(node t)// 查找最大{if (t == null) {return null;} else if (t.right == null) {return t;} elsereturn (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;}} 结语 |
|
来自: Fengsq501u81r4 > 《计算机》