二叉排序树（BinarySortTree）
发布时间：2020-12-14 04:41:55 所属栏目：大数据 来源：网络整理
导读：相关知识： 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。 二叉树中的左右子树不可随意交换。 根节点：一棵树最上面的节点称为根节点。 父节点、子节点：如果一个节点下面连接多个节点
|
相关知识： 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。 二叉树中的左右子树不可随意交换。 根节点：一棵树最上面的节点称为根节点。 父节点、子节点：如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子 节点。 叶子节点：没有任何子节点的节点称为叶子节点。 兄弟节点：具有相同父节点的节点互称为兄弟节点 二叉排序树： 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树，他的特点如下：
二叉排序树的结构如下图所示：
插入元素： 二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。 注：新插入的结点总是叶子结点。 查找元素： 若根结点的关键字值等于查找的关键字，成功；否则，若小于根结点的关键字值，递归查左子树；若大于根结点的关键字值，递归查右子树；若子树为空，查找不成功。 使用Java语言实现排序二叉树： 1.定义一个二叉树的封装节点类Node： 在Node类中，定义三个属性，int类型的value表示节点的值，Node类型的left表示节点的左子树，Node类型的right表示节点的右子树，并提供构造器和set、get方法。 1 package BST; 2 /** 3 * 二叉树节点类 4 * 属性：左子树，右子树，值 5 * 构造器，修改器和访问器 6 * @author ASUS 7 * 8 */ 9 public class Node { 10 private int value; //值 11 private Node left; //左子树 12 private Node right; //右子树 13 14 //无参构造器 15 public Node(){ 16 17 } 18 19 //有参构造器 20 public Node(Node left,Node right,int value){ 21 this.left=left; 22 this.right=right; 23 this.value=value; 24 } 25 26 //重载，一个参数构造器 27 public Node(int value) { 28 this.left=null; 29 this.right=null; 30 this.value=value; 31 } 32 33 //访问器和修改器 34 public int getValue() { 35 return value; 36 } 37 38 public void setValue(int value) { 39 this.value = value; 40 } 41 42 public Node getLeft() { 43 return left; 44 } 45 46 public void setLeft(Node left) { 47 this.left = left; 48 } 49 50 public Node getRight() { 51 return right; 52 } 53 54 public void setRight(Node right) { 55 this.right = right; 56 } 57 58 59 } 2.定义一个排序二叉树的工具类BSTTools 该类用于实现创建一个BST，在BST中遍历元素和在BST中删除指定元素等方法。 实现删除BST中指定元素的方法时，需要提供两个参数。分为三种情况，一种是要删除的元素key比根节点小，一种等于根节点，一种是比根节点大。 而当删除元素的key等于根节点时又分为三种情况：（假如删除的结点为p）
实现遍历时有两种方法：非递归遍历和递归遍历 采用递归的方法实现三种遍历，不仅代码简洁且容易理解，但其开销也比较大，而若采用非递归方法实现三种遍历，则要用栈来模拟实现（递归也是用栈实现的） 遍历二叉排序树时，有三种方法：
1 package BST; 2 3 import java.util.Stack; 4 5 public class BSTTools { 6 private static Node root=null; //创建一个唯一的根节点 7 8 /*该方法用于在BST中插入节点，参数为key 9 * 步骤是： 10 * 1.先定义插入节点的父节点，将root赋值给节点p 11 * 2.节点p从根节点root开始查找，找到插入节点的相应位置 12 * 3.在相应位置插入节点 13 */ 14 public boolean insertNode(int key) { 15 Node pNode=root; 16 Node prev=null;//插入节点的父节点，设置其为null 17 18 //找到插入节点的相应位置 19 while(pNode!=null){ 20 prev=pNode; 21 if (key<pNode.getValue()) { 22 pNode=pNode.getLeft(); 23 }else if (key>pNode.getValue()) { 24 pNode=pNode.getRight(); 25 }else{ 26 return true; 27 } 28 } 29 30 //将节点插入到相应的位置 31 if (root==null) { 32 root=new Node(key); 33 }else if (key>prev.getValue()) { 34 prev.setRight(new Node(key)); 35 } else { 36 prev.setLeft(new Node(key)); 37 } 38 return true; 39 } 40 41 /*中序遍历排序二叉树，有两中方法，递归遍历和非递归遍历, 42 *中序遍历对二叉树来说就是将各个节点从小到大进行排序 43 */ 44 45 /*非递归中序遍历二叉树 46 *步骤是： 47 *1，创建一个栈，从根节点开始遍历 48 *2，利用循环来遍历，先左子树，后根节点，再右子树 49 */ 50 public void sort() { 51 //new一个stack的对象用来存储节点值，stack是堆存储，特点是：先进后出(FILO),跟栈类似 52 Stack<Node> stack=new Stack<Node>(); 53 Node node=root; 54 //从根节点开始遍历 55 while(node!=null||!stack.isEmpty()){ 56 //如果根节点不为null，就循环先将左子树节点不断压入堆中 57 while (node!=null) { 58 stack.push(node); 59 node=node.getLeft(); 60 } 61 //stack.pop（）方法表示移除并返回栈顶元素 62 node=stack.pop(); 63 //打印栈顶元素的值，即该节点的值 64 System.out.println(node.getValue()); 65 //获得右子树 66 node=node.getRight(); 67 } 68 } 69 70 /*递归中序遍历二叉树 71 * 步骤是： 72 * 利用递归方法来遍历，先左子树，后根节点，再右子树 73 */ 74 public static void sort(Node node) { 75 if (node==null) { 76 return; 77 } else { 78 sort(node.getLeft()); 79 System.out.println(node.getValue()); 80 sort(node.getRight()); 81 } 82 } 83 84 //删除BST中的元素 85 86 //从根节点开始查找相应的节点并删除 87 public void delete(int key) { 88 delete(root,key); 89 } 90 91 /* 92 * 在BST中删除有三种情况： 93 * 1.要删除的元素key比根节点小 94 * 2.等于根节点 95 * 3.比根节点大 96 */ 97 98 //从指定的节点开始查找相应的节点并删除 99 public boolean delete(Node node,int key) { 100 if(node==null){ 101 return false; 102 }else{ 103 if (key==node.getValue()) { 104 return deleteBST(node); 105 } else if (key<node.getValue()) { 106 return delete(node.getLeft(),key); 107 } else { 108 return delete(node.getRight(),key); 109 } 110 } 111 } 112 113 /* 114 * 当删除的key和node.getValue相等时又分为三种情况：假如删除的结点为p 115 * 1.要删除的p结点是叶子结点，只需要修改它的双亲结点的指针为空 116 * 2.若p只有左子树或者只有右子树，直接让左子树/右子树代替p 117 * 3.若p既有左子树，又有右子树,用p左子树中最大的那个值代替p，重接其左子树 118 */ 119 private boolean deleteBST(Node node) { 120 // TODO Auto-generated method stub 121 Node temp=null; 122 /*右子树空，只需要重接它的左子树 123 *如果是叶子结点，在这里也把叶子结点删除了 124 */ 125 if (node.getRight()==null) { 126 temp=node; 127 node=node.getLeft(); 128 //左子树空， 重接它的右子树 129 } else if (node.getLeft()==null) { 130 temp=node; 131 node=node.getRight(); 132 //左右子树均不为空 133 } else { 134 temp=node; 135 Node sNode=node; 136 //转向左子树，然后向右走到“尽头” 137 sNode=sNode.getLeft(); 138 while (sNode.getRight()!=null) { 139 temp=sNode; 140 sNode=sNode.getRight(); 141 } 142 //将左子树最大的值代替被删除节点 143 node.setValue(sNode.getValue()); 144 //将原来左子树最大值节点的左子树改为该节点父节点的右子树。 145 temp.setRight(sNode.getLeft()); 146 } 147 return true; 148 } 149 } 3.定义一个测试类BinarySortTree： 该类主要用于测试BST。 1 package BST; 2 3 public class BinarySortTree { 4 public static void main(String[] args) { 5 BSTTools bstTools=new BSTTools(); 6 //构建的二叉树没有相同元素 7 int[] num = {4,7,2,1,10,6,9,3,8,11,-2}; 8 for (int i = 0; i < num.length; i++) { 9 bstTools.insertNode(num[i]); 10 } 11 bstTools.sort(); 12 bstTools.delete(4); 13 System.out.println("------------------"); 14 bstTools.sort(); 15 } 16 } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
