java 二叉查找树(增删改查操作)
发布时间:2020-12-14 23:53:25 所属栏目:Java 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 /** * java 二叉查找树(增删改查操作) */public class Main{public static void main ( String[] args ){BinarySearchTree btr = new BinarySearchT
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 /** * java 二叉查找树(增删改查操作) */ public class Main { public static void main ( String[] args ) { BinarySearchTree btr = new BinarySearchTree(); btr.insert ( 6 ); btr.insert ( 2 ); btr.insert ( 1 ); btr.insert ( 3 ); btr.insert ( 4 ); btr.insert ( 8 ); System.out.println ( btr.find ( 10 ) ); System.out.println ( btr.findMin() ); System.out.println ( btr.findMax() ); } } // 定义树节点 class BinaryNode { Comparable element; // 保存节点内容 BinaryNode left; // 保存节点的左孩子 BinaryNode right; // 保存节点的右孩子 // 定义构造函数,初始化成员 BinaryNode ( Comparable theElement ) { this ( theElement,null,null ); } BinaryNode ( Comparable theElement,BinaryNode lt,BinaryNode rt ) { element = theElement; left = lt; right = rt; } } // 定义二叉查找树,将树节点封装成树并进行各种操作 class BinarySearchTree { private BinaryNode root; public BinarySearchTree() { root = null; } // 判断树是否为空 public boolean isEmpty() { return root == null; } // 查找树中是否存在某节点 public Comparable find ( Comparable x ) { return find2 ( x,root ).element; } // 查找树中最小的节点 public Comparable findMin() { return findMin2 ( root ).element; } // 查找树中最大的节点 public Comparable findMax() { return findMax2 ( root ).element; } // 向树中插入某节点 public void insert ( Comparable x ) { root = insert2 ( x,root ); } // 删除树中某节点 public void remove ( Comparable x ) { root = remove2 ( x,root ); } // 查找的具体操作,该操作对外是透明的,后面的操作同理 private BinaryNode find2 ( Comparable x,BinaryNode t ) { // 如果不存在,就新添加一个辅助树节点,并将其内容设为不存在 if ( t == null ) { BinaryNode s = new BinaryNode ( "不存在该元素!" ); return s; } if ( x.compareTo ( t.element ) < 0 ) // 如果查找的元素比当前根节点小,则继续再该节点的左子树中查找,直至根节点为空 { return find2 ( x,t.left ); } else if ( x.compareTo ( t.element ) > 0 ) // 如果查找的元素比当前根节点大,则继续再该节点的右子树中查找,直至根节点为空 { return find2 ( x,t.right ); } else return t; // 如果查找的节点内容和当前根节点的内容相等,则返回当前根节点 } // 找最小节点的具体过程 private BinaryNode findMin2 ( BinaryNode t ) { if ( t == null ) { return null; } else if ( t.left == null ) { return t; } return findMin2 ( t.left ); } // 找最大节点的具体过程 private BinaryNode findMax2 ( BinaryNode t ) { if ( t != null ) { while ( t.right != null ) { t = t.right; } } return t; } // 构造二叉查找树的具体过程 private BinaryNode insert2 ( Comparable x,BinaryNode t ) { if ( t == null ) // 若树是空的,则构造一棵新的树,t为树的根 { t = new BinaryNode ( x,null ); } else if ( x.compareTo ( t.element ) < 0 ) // 如果要插入的元素小于当前节点,则插入在该节点的左边 { t.left = insert2 ( x,t.left ); } else if ( x.compareTo ( t.element ) > 0 ) // 如果要插入的元素大于当前节点,则插入在该节点的又边 { t.right = insert2 ( x,t.right ); } else ; // 否则什么也不做 return t; } // 删除节点的具体操作过程 private BinaryNode remove2 ( Comparable x,BinaryNode t ) { if ( t == null ) { return t; } if ( x.compareTo ( t.element ) < 0 ) { t.left = remove2 ( x,t.left ); } else if ( x.compareTo ( t.element ) > 0 ) { t.right = remove2 ( x,t.right ); } else if ( t.left != null && t.right != null ) { t.element = findMin2 ( t.right ).element; t.right = remove2 ( x,t.right ); } else { t = ( t.left != null ) ? t.left : t.right; } return t; } } 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |