二叉搜索树的Java达成
发布时间：2021-11-19 14:50:15 所属栏目：教程 来源：互联网
导读：为了更加深入了解二叉搜索树，本人用Java写了个二叉搜索树，有兴趣的同学可以一起探讨探讨。 首先，二叉搜索树是啥？它有什么用呢？ 二叉搜索树， 也称二叉排序树，它的每个节点的数据结构为1个父节点指针，1个左孩子指针，1个有孩子指针，还有就是自己的数
|
为了更加深入了解二叉搜索树，本人用Java写了个二叉搜索树，有兴趣的同学可以一起探讨探讨。 首先，二叉搜索树是啥？它有什么用呢？ 二叉搜索树， 也称二叉排序树，它的每个节点的数据结构为1个父节点指针，1个左孩子指针，1个有孩子指针，还有就是自己的数据部分了，因为只有左右两孩子，所以才叫二叉树，在此基础上，该二叉树还满足另外一个条件：每个结点的左孩子都不大于该结点&&每个结点的右孩子都大于该结点。这样，我们队这棵树进行中序遍历，就能把key从小到大排序了…… 那么问题来了，我都有线性表有链表了，我还要它干啥？两个字！效率！ 相比线性表，你要搜索一个key，就要执行一次线性时间，算法复杂度为O(n)；而用二叉搜索树，算法效率是O(lgn)！这是很诱人的数字。下面我用Java实现以下二叉搜索树，你自然就明白为什么算法复杂度是O(lgn)了。 其次，写一个数据结构，自然而然也要实现对这个数据结构的增、删、查、改了。 下面是我的思路： 创建树：我是通过一个一个结点的插入来建立一棵二叉搜索树。 搜索结点：从根节点开始，进行key的比较，小了就往左走，大了就往右走，最后到了叶子结点都还没有的话，那么该树就不存在要搜索的结点了。 修改结点：修改其实就是查询，在查询之后把结点的数据部分给改了而已，这里我就不重复去实现了。 删除结点：这个应该就是最难的了，所以我有必要详细讲，先上图（不好意思，懒得用软件画图了，将就将就下哈）： 当我们要删除一个结点时，分如下几种情况： 此结点是叶子结点，这个最简单啦，直接把结点给释放掉就行了。（如图删除9） 此结点只有左孩子，这个也简单啦，直接把左子树替换过来就行了。（如图删除3） 此结点只有右孩子，同上。（如图删除8） 此结点有左右孩子，当出现这种情况时（如图删除7），我们就要找出该结点的后继结点（因为右子树肯定存在，所以找肯定在右子树中），然后把这个后继结点替换到要删除的结点中，然后继续执行对这个后继结点的删除操作（递归删除操作就行了）。 发现没？现在我的解题思路是自顶向下去分析……自顶向下，逐级求精是一个很伟大的思想！ 现在问题来了！后继结点怎么求？我们来分析一下，当求一个结点的后继结点时，分为以下两种情况： 当该结点有右孩子时，后继结点就在右子树中，就是该右子树的最小结点 当该结点没有右孩子时，那后继结点就满足这个条件：该后继结点是该结点的祖先&&该结点位于该结点的左子树中（如图中的9的后继结点是12） 哎呀呀！问题又来了！最小结点咋办！很简单！ 当求一棵树的最小结点时，那么就要从这颗树的根节点开始，一直往左子树走，就能找到它的最小结点了！ 好了，现在问题逐步解决了！删除结点的功能也就完成了！ 最后，没代码说个锤子，咱上代码！ 首先，写个测试类： public class Test { public static void main(String[] args) { int[] datas={12,4,5,7,4,8,3,2,6,9}; BinTree tree=new BinTree(datas); tree.preOrderTraverse();//先序遍历 tree.midOrderTraverse();//中序遍历 tree.postOrderTraverse();//后序遍历 tree.insert(15); //插入结点 tree.search(7); //查询结点 tree.search(100); //查询一个不存在的结点 tree.getMax(); //获取最大值 tree.getMin(); //获取最小值 tree.getPre(7); //前驱结点 tree.getPre(2); //最前的前驱结点 tree.getPost(7); //后继结点 tree.getPost(15); //最后的后继结点 tree.delete(5); //删除结点 tree.delete(0); //删除一个不存在的结点 } } 然后，二叉搜索树： public class BinTree { Node root=null; private class Node{ Node parent=null; Node leftChild=null; Node rightChild=null; int key; public Node(int data) { this.key=data; } } public BinTree(int[] datas) { buildTree(datas); } private void buildTree(int[] datas) { for (int i = 0; i < datas.length; i++) { Node node=new Node(datas[i]); insertNode(node); } } private void insertNode(Node node) { //插入结点 Node next=this.root; Node cur=null; //用来保存当前结点 while(next!=null){ //当到达叶子结点时，确认位置！ cur=next; if(node.key>=cur.key){ next=next.rightChild; }else{ next=next.leftChild; } } node.parent=cur; //插入该结点！ if(cur==null){ this.root=node; //该树为空树，所以这个是根节点 }else if(node.key>=cur.key){ cur.rightChild=node; }else{ cur.leftChild=node; } } /* * 插入一个数 */ public void insert(int data){ Node node=new Node(data); System.out.println("插入结点："+data); insertNode(node); this.midOrderTraverse(); } /* * 先序遍历 */ public void preOrderTraverse(){ System.out.println("先序遍历："); preOrderTraverse(root); System.out.println(); } private void preOrderTraverse(Node node){ //先序遍历 if(node!=null){ System.out.print("-"+node.key+"-"); preOrderTraverse(node.leftChild); preOrderTraverse(node.rightChild); } } /* * 中序遍历 */ public void midOrderTraverse(){ System.out.println("中序遍历："); midOrderTraverse(root); System.out.println(); } private void midOrderTraverse(Node node){ //中序遍历 if(node!=null){ midOrderTraverse(node.leftChild); System.out.print("-"+node.key+"-"); midOrderTraverse(node.rightChild); } } /* * 后序遍历 */ public void postOrderTraverse(){ System.out.println("后序遍历："); postOrderTraverse(root); System.out.println(); } private void postOrderTraverse(Node node){ //后序遍历 if(node!=null){ System.out.print("-"+node.key+"-"); postOrderTraverse(node.leftChild); postOrderTraverse(node.rightChild); } } /* * 搜索结点 */ public void search(int data){ System.out.println("您要查找的是："+data); Node node; if((node=searchNode(new Node(data)))==null){ System.out.println("树中没有该结点！"); }else{ System.out.println("查找"+node.key+"成功！"); } } private Node searchNode(Node node){ //private供内部调用，搜索结点 if(node==null){ System.out.println("输入为空，查找失败！"); }else{ if(root==null){ System.out.println("该树为空树！"); }else{ //开始查找 boolean isFound=false; Node x=root; Node y=null; while(!isFound&&x!=null){ //当查到或者到了叶子节点还没查到时，终结！ y=x; if(node.key==x.key){ isFound=true; }else{ //通过比较大小往下面查找 if(node.key>x.key){ x=x.rightChild; }else{ x=x.leftChild; } } } if(isFound){ //没找到的话，在最后返回null return y; } } } return null; } /* * 获取最大值 */ public void getMax(){ Node node; if((node=getMaxNode(root))==null){ System.out.println("该树为空！"); }else{ System.out.println("最大的结点是："+node.key); } } private Node getMaxNode(Node node){ //获取最大值 if(node!=null){ Node x=node; Node y=null; while(x!=null){ //一直往右遍历直到底就是最大值了！ y=x; x=x.rightChild; } return y; } return null; } /* * 获取最小值 */ public void getMin(){ Node node; if((node=getMinNode(root))==null){ System.out.println("该树为空！"); }else{ System.out.println("最小的结点是："+node.key); } } private Node getMinNode(Node node){ //获取最小值 if(node!=null){ Node x=node; Node y=null; while(x!=null){ //一直往左遍历直到底就是最小值了！ y=x; x=x.leftChild; } return y; } return null; } /* * 获取前驱结点 */ public void getPre(int data){ Node node=null; System.out.println(data+"的前驱结点："); if((node=getPreNode(searchNode(new Node(data))))==null){ System.out.println("该结点不存在或无前驱结点！"); }else{ System.out.println(data+"的前驱结点为："+node.key); } } private Node getPreNode(Node node){ //获取前驱结点 if(node==null){ return null; } if(node.leftChild!=null){ //当有左孩子时，前驱结点就是左子树的最大值 return getMaxNode(node.leftChild); }else{//当不存在左孩子时，前驱结点就是——它的祖先，而且，它在这个祖先的右子树中。这句话自己画图就能理解了 Node x=node; Node y=node.parent; while(y!=null&&x==y.leftChild){ x=y; y=y.parent; } return y; } } /* * 获取后继结点 */ public void getPost(int data){ Node node=null; System.out.println(data+"的后继结点："); if((node=getPostNode(searchNode(new Node(data))))==null){ System.out.println("该结点不存在或无后继结点！"); }else{ System.out.println(data+"的后继结点为："+node.key); } } private Node getPostNode(Node node){ //获取后继结点 if(node==null){ return null; } if(node.rightChild!=null){ //当有右孩子时，前驱结点就是右子树的最小值 return getMinNode(node.rightChild); }else{//当不存在右孩子时，后继结点就是——它的祖先，而且，它在这个祖先的左子树中。这句话自己画图就能理解了 Node x=node; Node y=node.parent; while(y!=null&&x==y.rightChild){ x=y; y=y.parent; } return y; } } /* * 删除结点 */ public void delete(int data){ Node node; if((node=searchNode(new Node(data)))==null){//注意！这里不能new结点！你必须从树中找该结点！new就是初始化了 System.out.println("二叉树中不存在此结点！"); return; } deleteNode(node); System.out.println("删除结点"+data+"后："); this.midOrderTraverse(); } private void deleteNode(Node node){ if(node==null){ System.out.println("删除结点不能为空！"); return; } replacedNode(node); } private void replacedNode(Node node) { //替换结点 if(node.leftChild!=null &&node.rightChild!=null){ //当有左右孩子时，用后继结点替换 replacedNodeOfPost(node); } else { if(node.leftChild!=null){ //当只有左孩子时，直接用左子树替换 node=node.leftChild; }else if(node.rightChild!=null){ //只有右孩子时，直接有子树替换 node=node.rightChild; }else{ //当没有左右孩子时，就直接释放了这个结点 freeNode(node); } } } private void freeNode(Node node) { //释放该结点，断掉其与父结点的链接 if(node==node.parent.leftChild){ node.parent.leftChild=null; }else{ node.parent.rightChild=null; } } private void replacedNodeOfPost(Node node) { Node y=this.getPostNode(node); //找后继结点 node.key=y.key; replacedNode(y); //替换了key之后，再一次递归把现在这个结点给替换了！ } } 最后是测试结果： ------------------分割线------------------------- 先序遍历： -12--4--3--2--5--4--7--6--8--9- 中序遍历： -2--3--4--4--5--6--7--8--9--12- 后序遍历： -12--4--3--2--5--4--7--6--8--9- 插入结点：15 中序遍历： -2--3--4--4--5--6--7--8--9--12--15- 您要查找的是：7 查找7成功！ 您要查找的是：100 树中没有该结点！ 最大的结点是：15 最小的结点是：2 7的前驱结点： 7的前驱结点为：6 2的前驱结点： 该结点不存在或无前驱结点！ 7的后继结点： 7的后继结点为：8 15的后继结点： 该结点不存在或无后继结点！ 删除结点5后： 中序遍历： -2--3--4--4--6--7--8--9--12--15- 二叉树中不存在此结点！  （编辑：江门站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
