[javaSE] 数据结构(二叉树-遍历与查找)
2023-02-18 15:47:13 时间
前序遍历:中,左,右
中序遍历:左,中,右
后序遍历:左,右,中
二叉树查找
从根节点进行比较,目标比根节点小,指针移动到左边
从根节点进行比较,目标比根节点大,指针移动到右边
/** * 前序遍历 * @param tree */ public void preOrder(BSTree tree){ preOrder(tree.mRoot); } public void preOrder(BSTNode node){ if(node!=null){ System.out.print(node.key+""); preOrder(node.left); preOrder(node.right); } } /** * 中序遍历 * @param tree */ public void midOrder(BSTree tree){ midOrder(tree.mRoot); } public void midOrder(BSTNode node){ if(node!=null){ midOrder(node.left); System.out.print(node.key+""); midOrder(node.right); } } /** * 后序遍历 * @param tree */ public void postOrder(BSTree tree){ postOrder(tree.mRoot); } public void postOrder(BSTNode node){ if(node!=null){ postOrder(node.left); postOrder(node.right); System.out.print(node.key+""); } } /** * 二叉树的查找 * @param tree * @param key * @return */ public BSTNode<T> search(BSTree<T> tree,T key){ BSTNode<T> mRoot=tree.mRoot; while(mRoot!=null){ int flag=key.compareTo(mRoot.key); if(flag<0){ mRoot=mRoot.left; }else if(flag>0){ mRoot=mRoot.right; }else{ return mRoot; } } return mRoot; }
tree.preOrder(tree);//输出 312546 tree.midOrder(tree);//输出 123456 tree.postOrder(tree);//输出 214653 BSTree.BSTNode node=tree.search(tree, 5); System.out.println(node.left.key);//输出 4
相关文章
- SPI:Java的高可扩展利器
- Java反射机制清空字符串导致业务异常分析
- 7000+字图文并茂解带你深入理解java锁升级的每个细节
- 全文手敲代码,教你用Java实现扫雷小游戏
- 4种方法教你如何查看java对象所占内存大小
- 手绘图解java类加载原理
- Java中的线程到底有哪些安全策略
- Java中观察者模式与委托,还在傻傻分不清
- 一图详解java-class类文件原理
- Java遇上SPL:架构优势和开发效率,一个不放过
- 长篇图解java反射机制及其应用场景
- [java并发编程]基于信号量semaphore实现限流器
- java并发编程-StampedLock高性能读写锁
- 【java并发编程】ReentrantLock 可重入读写锁
- 【java并发编程】Lock & Condition 协调同步生产消费
- Java synchronized对象级别与类级别的同步锁
- java并发编程JUC第十二篇:AtomicInteger原子整型
- java并发编程JUC第十一篇:如何在线程之间进行对等数据交换
- java并发编程JUC第十篇:CyclicBarrier线程同步
- java并发编程JUC第九篇:CountDownLatch线程同步