|
这个我们开始来写一个BST的数据结构,此问题我被面试管问过,写过.我们写一个简单的就可以的,那我们来实现AVL树 代码如下: public class AvlTree<T extends Comparable> { private static class AvlNode<T>{//avl树节点 T element; // 节点中的数据 AvlNode<T> left; // 左儿子 AvlNode<T> right; // 右儿子 int height; // 节点的高度 public AvlNode(T theElement) { this(theElement, null, null); } public AvlNode(T theElement, AvlNode<T> lt, AvlNode<T> rt) { element = theElement; left = lt; right = rt; height = 0; } } private AvlNode<T> root;//avl树根 public AvlTree( ) { root = null; } //在avl树中插入数据，重复数据复略 public void insert(T x) { root = insert(x,root); } //在avl中删除数据,没有实现 public void remove(T x) { System.out.println( "Sorry, remove unimplemented" ); } //在avl树中找最小的数据 public T findMin() throws Exception { if(isEmpty()) throw new Exception(); return findMin(root).element; } //在avl树中找最大的数据 public T findMax() throws Exception { if(isEmpty()) throw new Exception(); return findMax(root).element; } //搜索 public boolean contains(T x) { return contains(x,root); } public void makeEmpty() { root = null; } public boolean isEmpty() { return root == null; } //排序输出avl树 public void printTree() { if(isEmpty()) System.out.println( "Empty tree" ); else printTree(root); } private AvlNode<T> insert(T x, AvlNode<T> t) { if( t == null ) return new AvlNode< T>( x, null, null ); //判断和根节点数据的大小 int compareResult=x.compareTo(t.element); if(compareResult<0) { t.left = insert(x,t.left );//将x插入左子树中 if(height(t.left ) - height(t.right )== 2)//打破平衡 if(x.compareTo(t.left.element)<0 )//LL型（左左型） t = rotateWithLeftChild(t); else //LR型（左右型） t = doubleWithLeftChild(t); } else if(compareResult>0) { t.right = insert(x,t.right );//将x插入右子树中 if( height(t.right) - height(t.left ) == 2 )//打破平衡 if( x.compareTo(t.right.element )>0)//RR型（右右型） t = rotateWithRightChild(t); else //RL型 t = doubleWithRightChild(t); } else // 重复数据，什么也不做 t.height = Math.max( height( t.left ), height( t.right ) ) + 1;//更新高度 return t; } //找最小 private AvlNode< T> findMin( AvlNode< T> t ) { if( t == null ) return t; while( t.left != null ) t = t.left; return t; } //找最大 private AvlNode< T> findMax( AvlNode< T> t ) { if( t == null ) return t; while( t.right != null ) t = t.right; return t; } //搜索（查找） private boolean contains( T x, AvlNode t ) { while( t != null ) { int compareResult = x.compareTo((T) t.element ); if( compareResult < 0 ) t = t.left; else if( compareResult > 0 ) t = t.right; else return true; // Match } return false; // No match } //中序遍历avl树 private void printTree( AvlNode< T> t ) { if( t != null ) { printTree( t.left ); System.out.println( t.element ); printTree( t.right ); } } //求高度 private int height( AvlNode< T> t ) { return t == null ? -1 : t.height; } //带左子树旋转,适用于LL型 private AvlNode< T> rotateWithLeftChild(AvlNode< T> k2) { AvlNode<T> k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1; k1.height = Math.max( height( k1.left ), k2.height ) + 1; return k1; } //带右子树旋转，适用于RR型 private AvlNode< T> rotateWithRightChild( AvlNode< T> k1 ) { AvlNode< T> k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1; k2.height = Math.max( height( k2.right ), k1.height ) + 1; return k2; } //双旋转，适用于LR型 private AvlNode< T> doubleWithLeftChild( AvlNode< T> k3 ) { k3.left = rotateWithRightChild( k3.left ); return rotateWithLeftChild( k3 ); } //双旋转,适用于RL型 private AvlNode< T> doubleWithRightChild( AvlNode< T> k1 ) { k1.right = rotateWithLeftChild( k1.right ); return rotateWithRightChild( k1 ); } // Test program public static void main( String [ ] args ) throws Exception { AvlTree< Integer> t = new AvlTree< Integer>( ); final int NUMS = 4000; final int GAP = 37; System.out.println( "Checking... (no more output means success)" ); for( int i = GAP; i != 0; i = ( i + GAP ) % NUMS ) t.insert( i ); if( NUMS < 40 ) t.printTree( ); if( t.findMin( ) != 1 || t.findMax( ) != NUMS - 1 ) System.out.println( "FindMin or FindMax error!" ); for( int i = 1; i < NUMS; i++ ) if( !t.contains( i ) ) System.out.println( "Find error1!" ); } } 小结:这个BST还是有一些地方不完善,大家一起来搞搞,说不定就很完美的。 |
行业聚焦 面试交流 职位推荐 开发视频 技术交流 腾讯微博 新浪微博
友情链接：课课家教育 阿里云 鲜果 W3Cfuns前端网 中国企业家 环球企业家 投资界 传媒梦工场 MSN中文网 Android开发者社区 cnbeta 投资中国网 又拍云存储 美通说传播 IT茶馆 网商在线 商业评论网 TechOrange IT时代周刊 3W创新传媒 开源中国社区 二维工坊 Iconfans 推酷 智能电视网 FreeBuf黑客与极客 财经网 DoNews 凤凰财经 新财富 eoe移动开发者社区 i黑马 网易科技 新浪科技 搜狐IT 创业家 创业邦 腾讯财经 福布斯中文网 天下网商 TechWeb 雷锋网 新浪创业 和讯科技 品途O2O 极客公园 艾瑞网 抽屉新热榜 卖家网 人民网通信频道 拉勾网 创新派 简单云主机
手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据
( 蜀ICP备14029946号 ) 
成都守望者科技有限公司 © 2013-2016 All Rights Reserved
收藏