首页 > 代码库 > 数据结构—二叉查找树
数据结构—二叉查找树
查找树是一种数据结构，二叉查找树是按二叉树结构来组织的。可以用链表结构表示，其中每一个结点就是一个对象。结点中包括：key、数据、left、right、p。其中left、right和p分别指向左儿子，右儿子和父结点。
二叉查找树中的关键字总是满足二叉查找树的性质：y是x左子树上的结点，则key[y]≤key[x]，如果y是x右子树上的结点，则key[y]≥key[x]。
遍历：
根据二叉查找树的性质，可以用一个递归算法按排列顺序输出树中的所有关键字。这种是中序遍历算法：因为一子树根的关键字在输出时介于左子树和右子树的关键字之间。那么，根据根所在的不同位置，还有前序遍历和后序遍历。
1 //中序递归遍历二叉树 2 public void Inorder_Tree_Walk(TreeNode root) 3 { 4 if(root!=null) 5 { 6 Inorder_Tree_Walk(root.leftChild); 7 nodeList.add(root); 8 Inorder_Tree_Walk(root.rightChild); 9 }10 11 12 }
查询：
在树中查找给定的关键字。下面代码从树的根节点开始进行查找，并沿着树下降。碰到节点x就比较节点x的key与给定k值比较。如果相同，则查找结束。如果k小于key[x]，则继续查找x的左子树，根据二叉查找树的性质可知，k不可能在x的右子树中。对称地，如果k大于key[x]，则继续查找x 的右子树。运行时间是O（lgn）。
1 //查找给定关键字k 2 public TreeNode Tree_Seach(int key) 3 { 4 TreeNode pNode = root; 5 while(pNode!=null && pNode.key != key) 6 { 7 if (key<pNode.key) 8 pNode = pNode.leftChild; 9 else10 pNode = pNode.rightChild;11 }12 return pNode; 13 }
最大最小关键字：
要查找二叉树中的最小关键字元素，只要从根节点开始，沿着各结点的left指针查找下去，直到遇到null为止，而要找到最大关键字元素，就沿着各节点right指针查找。
public TreeNode Tree_Minimum(TreeNode node) throws Exception { if(node == null) { throw new Exception("树为空"); } TreeNode pNode = node; while(pNode.leftChild != null) { pNode = pNode.leftChild; } return pNode; } public TreeNode Tree_Maximum(TreeNode node)throws Exception { if(node == null) { throw new Exception("树为空"); } TreeNode pNode = node; while(pNode.rightChild != null) { pNode = pNode.rightChild; } return pNode; }
前趋和后继
给定一个二叉查找树中的结点，要求找出中序遍历下它的后继。就是：某结点x的后继，具有大于key[x]中的关键字中最小者的结点。根据二叉查找树的结构，不用进行比较就可以找到结点的后继。
后继：一、如果x的右子树不空，后继就是右子树中最小值。二、如果x的右子树为空，则x的后继是x的最低祖先结点，且后继的左儿子是x的祖先。如下代码：
public TreeNode Tree_Successor(TreeNode node) throws Exception { if(node == null) { return null; } TreeNode pNode = node; //若右子树不空，则为右子树中最小的关键字 if(pNode.rightChild != null) { return Tree_Minimum(pNode.rightChild); } TreeNode parentNode = node.parent; //若右子树为空，且x有一个后继y.则y是x的最低祖先结点，且y的左儿子也是x的祖先 while(parentNode != null && pNode == parentNode.rightChild) { pNode = parentNode; parentNode = pNode.parent; } return parentNode; }
前驱：前驱和后继是对称的。一、如果x的左子树不空，前驱就是左子树中最大值。二、如果x的左子树为空，则x的前驱是x的最低祖先结点，且前驱的左儿子是x的祖先。
public TreeNode precessor(TreeNode node) throws Exception { TreeNode pNode = node; TreeNode parentNode = pNode.parent; if(pNode == null) { return null; } if(pNode.leftChild != null) { return Tree_Maximum(pNode.leftChild); } while(parentNode != null && pNode == parentNode.leftChild) { pNode = parentNode; parentNode = parentNode.parent; } return parentNode; }
插入：将新的元素v插入树中，可以调用Tree_Insert过程。该过程的输入参数是一个结点z，且key[z] = v，z.leftChild = null，z.rightChild = null。该过程修改树T和z的域，并把z插入到树中适当的位置。运行时间为O（lgn）
public void insert(int key) { TreeNode parentNode = null; TreeNode newNode = new TreeNode(key, "v", null, null, null); TreeNode pNode = root; if(root == null) { root = newNode; return ; } while(pNode != null) { parentNode = pNode; if(key < pNode.key) { pNode = pNode.leftChild; } else if(key > pNode.key) { pNode = pNode.rightChild; } else { return;//书中已存在与新结点的关键字相同的结点 } } newNode.parent = parentNode; if(newNode.key < parentNode.key) { parentNode.leftChild = newNode; } else { parentNode.rightChild = newNode; } }
删除：将给定结点z从二叉查找树中删除的过程：一、如果z没有子女，则修改其父节点z.parent，使其子女为空；二、如果z只有一个子女，则可以通过在其子结点和父节点之间建立一条链来删除z。三、如果z有两个子女，先删除z的后继y(y没有子女)，再用y的内容代替z的内容。运行时间为O(lgn)。
public void Delete(int key) throws Exception { TreeNode pNode = Tree_Seach(key); if(pNode == null) { throw new Exception("树中不存在要删除的关键字！"); } Tree_Delete(pNode); } private void Tree_Delete(TreeNode pNode) throws Exception { if(pNode == null) { return ; } TreeNode parentNode = pNode.parent; if(pNode.leftChild == null && pNode.rightChild == null) { if(parentNode.leftChild == pNode) { parentNode.leftChild = null; } else { parentNode.rightChild = null; } return; } if(pNode.leftChild == null && pNode.rightChild != null) { if(pNode == parentNode.leftChild) { parentNode.leftChild = pNode.rightChild; pNode.rightChild.parent = parentNode; } else { parentNode.rightChild = pNode.rightChild; pNode.rightChild.parent = parentNode; } return; } if(pNode.leftChild != null && pNode.rightChild == null) { if(pNode == parentNode.leftChild) { parentNode.leftChild = pNode.leftChild; pNode.leftChild.parent = parentNode; } else { parentNode.rightChild = pNode.leftChild; pNode.leftChild.parent = parentNode; } return; } //左右儿子都不为空，就删除后继，让后继的内容，代替当前内容 TreeNode successorNode = Tree_Successor(pNode); pNode.key = successorNode.key; pNode.data = successorNode.data; Tree_Delete(successorNode); }
程序实现：
1 package agrith; 2 3 import java.util.List; 4 import java.util.ArrayList; 5 6 public class BiSeachTree { 7 class TreeNode{ 8 private int key; 9 private String data; 10 private TreeNode leftChild; 11 private TreeNode rightChild; 12 private TreeNode parent; 13 14 public TreeNode(int key,String data,TreeNode leftChild,TreeNode rightChild,TreeNode parent) 15 { 16 17 this.key = key; 18 this.data =http://www.mamicode.com/data; 19 this.leftChild = leftChild; 20 this.rightChild = rightChild; 21 this.parent = parent; 22 } 23 public int getKey() 24 { 25 return key; 26 } 27 public String toString() 28 { 29 String leftKey = (leftChild == null?" ":String.valueOf(leftChild.key)); 30 String rightKey = (rightChild == null?" ":String.valueOf(rightChild.key)); 31 return "("+leftKey+","+key+","+rightKey+")"; 32 } 33 } 34 35 private TreeNode root = null; 36 private List<TreeNode> nodeList = new ArrayList<TreeNode>(); 37 38 //获取中序二叉树列表 39 public List<TreeNode> Inorder_Tree_WalkList() 40 { 41 42 if(nodeList != null ) 43 { 44 nodeList.clear(); 45 } 46 Inorder_Tree_Walk(root); 47 return nodeList; 48 49 } 50 //中序递归遍历二叉树 51 public void Inorder_Tree_Walk(TreeNode root) 52 { 53 if(root!=null) 54 { 55 Inorder_Tree_Walk(root.leftChild); 56 nodeList.add(root); 57 Inorder_Tree_Walk(root.rightChild); 58 } 59 } 60 //查找给定关键字k 非递归版本运行的快 61 public TreeNode Tree_Seach(int key) 62 { 63 TreeNode pNode = root; 64 while(pNode!=null && pNode.key != key) 65 { 66 if (key<pNode.key) 67 pNode = pNode.leftChild; 68 else 69 pNode = pNode.rightChild; 70 } 71 return pNode; 72 } 73 public TreeNode Tree_Minimum(TreeNode node) throws Exception 74 { 75 if(node == null) 76 { 77 throw new Exception("树为空"); 78 } 79 TreeNode pNode = node; 80 while(pNode.leftChild != null) 81 { 82 pNode = pNode.leftChild; 83 } 84 return pNode; 85 } 86 public TreeNode Tree_Maximum(TreeNode node)throws Exception 87 { 88 if(node == null) 89 { 90 throw new Exception("树为空"); 91 } 92 TreeNode pNode = node; 93 while(pNode.rightChild != null) 94 { 95 pNode = pNode.rightChild; 96 } 97 return pNode; 98 } 99 public TreeNode Tree_Successor(TreeNode node) throws Exception100 {101 if(node == null)102 {103 return null;104 }105 TreeNode pNode = node;106 //若右子树不空，则为右子树中最小的关键字107 if(pNode.rightChild != null)108 {109 return Tree_Minimum(pNode.rightChild);110 }111 TreeNode parentNode = node.parent;112 //若右子树为空，且x有一个后继y.则y是x的最低祖先结点，且y的左儿子也是x的祖先113 while(parentNode != null && pNode == parentNode.rightChild)114 {115 pNode = parentNode;116 parentNode = pNode.parent;117 }118 return parentNode; 119 }120 public TreeNode Tree_precessor(TreeNode node) throws Exception121 {122 TreeNode pNode = node;123 TreeNode parentNode = pNode.parent;124 if(pNode == null)125 {126 return null;127 }128 if(pNode.leftChild != null)129 {130 return Tree_Maximum(pNode.leftChild);131 }132 while(parentNode != null && pNode == parentNode.leftChild)133 {134 pNode = parentNode;135 parentNode = parentNode.parent;136 }137 return parentNode;138 }139 public void Tree_Insert(int key)140 {141 TreeNode parentNode = null;142 TreeNode newNode = new TreeNode(key, "v", null, null, null);143 TreeNode pNode = root;144 if(root == null)145 {146 root = newNode;147 return ;148 }149 while(pNode != null)150 {151 parentNode = pNode;152 if(key < pNode.key)153 {154 pNode = pNode.leftChild;155 }156 else if(key > pNode.key)157 {158 pNode = pNode.rightChild; 159 }160 else161 {162 return;//书中已存在与新结点的关键字相同的结点163 }164 }165 newNode.parent = parentNode;166 if(newNode.key < parentNode.key)167 {168 parentNode.leftChild = newNode; 169 }170 else171 {172 parentNode.rightChild = newNode;173 } 174 }175 public boolean IsEmpty()176 {177 if(root == null)178 {179 return true;180 }181 else182 {183 return false;184 }185 }186 public void TreeEmpty() throws Exception187 {188 if(IsEmpty())189 {190 throw new Exception("树空异常！");191 }192 }193 //返回二叉查找树的关键字的有序链表194 public String toStringofOrderList(){195 StringBuilder sbBuilder = new StringBuilder("[");196 for(TreeNode p :Inorder_Tree_WalkList())197 {198 sbBuilder.append(p.key);199 sbBuilder.append(" ");200 }201 sbBuilder.append("]");202 return sbBuilder.toString();203 }204 //返回二叉查找树的字符串表示205 public String toString()206 {207 StringBuilder sbBuilder = new StringBuilder("[");208 for(TreeNode p:Inorder_Tree_WalkList())209 {210 sbBuilder.append(p);211 sbBuilder.append(" ");212 }213 sbBuilder.append("]");214 return sbBuilder.toString();215 }216 public TreeNode getRoot()217 {218 return root;219 }220 }221 222 223 /*224 * To change this template, choose Tools | Templates225 * and open the template in the editor.226 */227 package agrith;228 229 import javax.swing.tree.TreeNode;230 231 /**232 *233 * @author ning234 */235 public class TreeMain {236 public static void main(String [] args) throws Exception237 {238 try{239 BiSeachTree biTree = new BiSeachTree();240 System.out.println("二叉树是否为空？" + (biTree.IsEmpty()?"是":"否"));241 int [] keys = new int[]{ 15, 6, 18, 3, 7, 13, 20, 2, 9, 4 };242 for(int key:keys)243 {244 biTree.Tree_Insert(key);245 }246 System.out.println("二叉树是否为空？" + (biTree.IsEmpty()?"是":"否"));247 BiSeachTree.TreeNode minTreeNode = biTree.Tree_Minimum(biTree.getRoot());248 System.out.println("最小关键字："+minTreeNode.getKey());249 BiSeachTree.TreeNode maxTreeNode = biTree.Tree_Maximum(biTree.getRoot()); 250 System.out.println("最大关键字："+maxTreeNode.getKey());251 test(biTree, maxTreeNode);252 System.out.println("根结点的关键字："+biTree.getRoot().getKey());253 TestTraverse(biTree);254 }catch(Exception e)255 {256 System.out.println(e.getMessage());257 e.printStackTrace();258 }259 }260 public static void TestTraverse(BiSeachTree biTree)261 {262 System.out.println("遍历二叉树：" + biTree );263 System.out.println("二叉树转化为有序链表："+ biTree.toStringofOrderList());264 }265 public static void test(BiSeachTree BiTree,BiSeachTree.TreeNode pNode) throws Exception266 {267 System.out.println("本结点: " + pNode); 268 System.out.println("前趋结点: " + BiTree.Tree_precessor(pNode)); 269 System.out.println("后继结点: " + BiTree.Tree_Successor(pNode)); 270 }271 272 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。