java创建二叉树数据结构,二叉树查找算法java

  java创建二叉树数据结构,二叉树查找算法java

  00-1010定义节点结构搜索算法插入算法删除算法完整代码

  00-1010二叉查找树(也叫二叉查找树和二叉排序树)是一棵二叉树,每个节点的关键字都不一样,其中根序列按其关键字升序排列。

  等价描述:对于二叉查找树中的任意节点P,左子树中节点的关键字都小于P,右子树中节点的关键字都大于P,节点P的左右子树也都是二分搜索法树。

  

目录

 

  :one: key:关键字的值

  :two:值:关键字的存储信息

  3360THREE 3360LEFT:左侧节点的引用

  :four: right:右侧节点的引用

  BSTNodeK类扩展了ComparableK,V { public K key公V值;public BSTNodeK,V left公共BSTNodeK,V右;}为了代码简洁,本文不考虑属性的封装,全部设置为public。

  00-1010思路:利用二叉查找树的特性,左子树值小于根节点值,右子树值大于根节点值,从根节点开始搜索。

  如果目标值等于一个节点值,则返回该节点;如果目标值小于节点值,则搜索该节点的左子树;如果目标值大于节点值,则搜索该节点的右子树的递归版本。

  public BSTNodeK,V searchbyrecusion(K key){ return searchbyrecusion(root,key);} private BSTNodeK,V searchByRecursion(BSTNodeK,V t,K key){ if(t==null t . key==key)return t;else if (key.compareTo(t.key) 0)返回searchByRecursion(t.left,key);否则返回searchByRecursion(t.right,key);}:two:迭代版

  public BSTNodeK,V search by iteration(K key){ BSTNodeK,V p=this.root而(p!=null){ if(key.compare to(p . key)0)p=p . left;else if(key.compare to(p . key)0)p=p . right;否则返回p;}返回null}

  00-1010在以T为根的二叉查找树中插入关键字key的节点来搜索T中的key,在搜索失败中插入:one:的递归版本。

  public void insertbyreversion(K key,V value){ this . root=insertbyreversion(root,key,value);} private BSTNodeK,V insertByRecursion(BSTNodeK,V t,K key,V value){ if(t==null){ return new BSTNode(key,value);} else if(key.compare to(t . key)0)t . left=insertByRecursion(t . left,key,value);else if(key.compare to(t . key)0)t . right=insertByRecursion(t . right,key,value);else { t.value=value//

  如果二叉查找树中已经存在关键字,则替换该结点的值 } return t; }:two: 迭代版本

  

public void insertByIteration(K key, V value) { BSTNode<K, V> p = root; if (p == null) { root = new BSTNode<>(key, value); return; } BSTNode<K, V> pre = null; while (p != null) { pre = p; if (key.compareTo(p.key) < 0) p = p.left; else if (key.compareTo(p.key) > 0) p = p.right; else { p.value = value; // 如果二叉查找树中已经存在关键字,则替换该结点的值 return; } } if(key.compareTo(pre.key) < 0) { pre.left = new BSTNode<>(key, value); } else { pre.right = new BSTNode<>(key, value); } }

 

  

删除算法

在以t为根的二叉查找树中删除关键词值为key的结点

 

  在t中找到关键词为key的结点,分三种情况删除key

  1.若key是叶子节点,则直接删除

  

 

  2.若key只有一棵子树,则子承父业

  

 

  3.若key既有左子树也有右子树,则找到key的后继结点,替换key和后继节点的值,然后删除后继节点(后继节点只有一棵子树,转化为第二种情况)。

  后继结点是当前结点的右子树的最左结点,如果右子树没有左子树,则后继节点就是右子树的根节点。

  

 

  

 

  

public void removeByRecursion(K key) { this.root = removeByRecursion(root, key); } private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) { if(t == null) return root; else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大,递归处理右子树 else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key); // key小,递归处理左子树 else { if(t.right == null) return t.left; // 情况一、二一起处理 if(t.left == null) return t.right; // 情况一、二一起处理 BSTNode<K, V> node = t.right; // 情况三:右子树没有左子树 if (node.left == null) { node.left = t.left; } else { // 情况三:右子树有左子树 BSTNode<K, V> pre = null; while (node.left != null) { pre = node; node = node.left; } t.key = node.key; t.value = node.value; pre.left = node.right; } } return t; }

 

  

完整代码

class BSTNode<K extends Comparable<K>, V> { public K key; public V value; public BSTNode<K, V> left; public BSTNode<K, V> right; public BSTNode(K key, V value) { this.key = key; this.value = value; }}class BSTree<K extends Comparable<K>, V> { public BSTNode<K, V> root; private void inorder(BSTNode<K, V> root) { if (root != null) { inorder(root.left); System.out.print("(key: " + root.key + " , value: " + root.value + ") "); inorder(root.right); } } private void preorder(BSTNode<K, V> root) { if (root != null) { System.out.print("(key: " + root.key + " , value: " + root.value + ") "); preorder(root.left); preorder(root.right); } } private void postorder(BSTNode<K, V> root) { if (root != null) { postorder(root.left); postorder(root.right); System.out.print("(key: " + root.key + " , value: " + root.value + ") "); } } public void postorderTraverse() { System.out.print("后序遍历:"); postorder(root); System.out.println(); } public void preorderTraverse() { System.out.print("先序遍历:"); preorder(root); System.out.println(); } public void inorderTraverse() { System.out.print("中序遍历:"); inorder(root); System.out.println(); } public BSTNode<K, V> searchByRecursion(K key) { return searchByRecursion(root, key); } private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) { if (t == null t.key == key) return t; else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key); else return searchByRecursion(t.right, key); } public BSTNode<K, V> searchByIteration(K key) { BSTNode<K, V> p = this.root; while (p != null) { if (key.compareTo(p.key) < 0) p = p.left; else if (key.compareTo(p.key) > 0) p = p.right; else return p; } return null; } public void insertByRecursion(K key, V value) { this.root = insertByRecursion(root, key, value); } private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) { if (t == null) { return new BSTNode<>(key, value); } else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value); else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value); else { t.value = value; } return t; } public void insertByIteration(K key, V value) { BSTNode<K, V> p = root; if (p == null) { root = new BSTNode<>(key, value); return; } BSTNode<K, V> pre = null; while (p != null) { pre = p; if (key.compareTo(p.key) < 0) p = p.left; else if (key.compareTo(p.key) > 0) p = p.right; else { p.value = value; // 如果二叉查找树中已经存在关键字,则替换该结点的值 return; } } if (key.compareTo(pre.key) < 0) { pre.left = new BSTNode<>(key, value); } else { pre.right = new BSTNode<>(key, value); } } public void removeByRecursion(K key) { this.root = removeByRecursion(root, key); } private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) { if(t == null) return root; else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大,递归处理右子树 else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key); // key小,递归处理左子树 else { if(t.right == null) return t.left; // 情况一、二一起处理 if(t.left == null) return t.right; // 情况一、二一起处理 BSTNode<K, V> node = t.right; // 情况三:右子树没有左子树 if (node.left == null) { node.left = t.left; } else { // 情况三:右子树有左子树 BSTNode<K, V> pre = null; while (node.left != null) { pre = node; node = node.left; } t.key = node.key; t.value = node.value; pre.left = node.right; } } return t; }}

:bug: 方法测试:

 

  

public class Main { public static void main(String[] args) { BSTree<Integer, Integer> tree = new BSTree<>();// tree.insertByRecursion(1, 1);// tree.insertByRecursion(5, 1);// tree.insertByRecursion(2, 1);// tree.insertByRecursion(4, 1);// tree.insertByRecursion(3, 1);// tree.insertByRecursion(1, 2); tree.insertByIteration(1, 1); tree.insertByIteration(5, 1); tree.insertByIteration(2, 1); tree.insertByIteration(4, 1); tree.insertByIteration(3, 1); tree.insertByIteration(1, 5); tree.removeByRecursion(4); tree.inorderTraverse(); tree.postorderTraverse(); tree.preorderTraverse(); BSTNode<Integer, Integer> node = tree.searchByIteration(1); System.out.println(node.key + " " + node.value); }}

 

  

中序遍历:(key: 1 , value: 5) (key: 2 , value: 1) (key: 3 , value: 1) (key: 5 , value: 1)后序遍历:(key: 3 , value: 1) (key: 2 , value: 1) (key: 5 , value: 1) (key: 1 , value: 5)先序遍历:(key: 1 , value: 5) (key: 5 , value: 1) (key: 2 , value: 1) (key: 3 , value: 1)1 5

 

  

以上就是Java数据结构之二叉查找树的实现的详细内容,更多关于Java二叉查找树的资料请关注盛行IT其它相关文章!

 

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

相关文章阅读

  • mysql复合索引和组合索引,mysql组合索引数据结构
  • mysql复合索引和组合索引,mysql组合索引数据结构,Mysql之组合索引方法详解
  • mysql复合索引和组合索引,mysql复合索引数据结构
  • mysql复合索引和组合索引,mysql复合索引数据结构,MySQL的复合索引总结
  • b+树 多路搜索树,数据结构中树的分类
  • b+树 多路搜索树,数据结构中树的分类,数据结构-树(三):多路搜索树B树、B+树
  • avl树的构造,avl树特性,数据结构之AVL树详解
  • 数据结构c语言哈夫曼树,c语言哈夫曼树的构造,使用C语言详解霍夫曼树数据结构
  • c语言数据结构算法编程库,数据结构 c语言中文网
  • c语言数据结构算法编程库,数据结构 c语言中文网,C语言编程数据结构基础详解小白篇
  • c++纸牌游戏,数据结构纸牌游戏c语言
  • c++纸牌游戏,数据结构纸牌游戏c语言,C语言实战之纸牌游戏
  • ,,c#解析jobject的数据结构
  • ,,javascript数据结构之多叉树经典操作示例【创建、添加、遍历、移除等】
  • ,,Java 数据结构与算法系列精讲之背包问题
  • 留言与评论(共有 条评论)
       
    验证码: