二叉排序樹的實(shí)現(xiàn)與基本操作
二叉排序樹又稱二叉查找樹。它或者是一顆空樹,或者是具有以下性質(zhì)的二叉樹:
①如果左子樹不空,那么左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;
②如果右子樹不空,那么右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值;
③左右子樹也分別為二叉排序樹。
以下代碼實(shí)現(xiàn)了:
- 二叉樹的構(gòu)建
- 二叉樹的中、前、后、層序遍歷
- 二叉樹中結(jié)點(diǎn)的最大距離
import java.util.LinkedList; import java.util.Queue; class Node{ public int data; public Node left; public Node right; public int leftMaxDistance; public int rightMaxDistance; public Node(int data){ this.data=data; this.left=null; this.right=null; } } /** * @author TY * 實(shí)現(xiàn)二叉排序樹,包括插入、中序遍歷、先序遍歷、后序遍歷、計算所有節(jié)點(diǎn)的最大距離的功能 */ public class BinaryTree { private Node root; public BinaryTree(){ root=null; } public void insert(int data){ Node newNode=new Node(data); if(root==null) root=newNode; else{ Node current=root; Node parent; while (true) {//尋找插入位置 parent=current; if(data<current.data){ current=current.left; if(current==null){ parent.left=newNode; return; } }else{ current=current.right; if (current==null) { parent.right=newNode; return; } } } } } //將數(shù)值輸入構(gòu)建二叉樹 public void buildTree(int[] data){ for (int i = 0; i < data.length; i++) { insert(data[i]); } } //中序遍歷方法遞歸實(shí)現(xiàn) public void inOrder(Node localRoot){ if(localRoot!=null){ inOrder(localRoot.left); System.out.print(localRoot.data+" "); inOrder(localRoot.right); } } public void inOrder(){ this.inOrder(this.root); } //先序遍歷方法遞歸實(shí)現(xiàn) public void preOrder(Node localRoot){ if(localRoot!=null){ System.out.print(localRoot.data+" "); preOrder(localRoot.left); preOrder(localRoot.right); } } public void preOrder(){ this.preOrder(this.root); } //后序遍歷方法遞歸實(shí)現(xiàn) public void postOrder(Node localRoot){ if(localRoot!=null){ postOrder(localRoot.left); postOrder(localRoot.right); System.out.print(localRoot.data+" "); } } public void postOrder(){ this.postOrder(this.root); } /** * 層序遍歷二叉樹:現(xiàn)將根結(jié)點(diǎn)放入隊(duì)列中,然后每次都從隊(duì)列中取一個結(jié)點(diǎn)打印該結(jié)點(diǎn)的值, * 若這個結(jié)點(diǎn)有子結(jié)點(diǎn),則將它的子結(jié)點(diǎn)放入隊(duì)列尾,直到隊(duì)列為空 */ public void layerTranverse(){ if(this.root==null) return; Queue<Node> q=new LinkedList<Node>(); q.add(this.root); while(!q.isEmpty()){ Node n=q.poll(); System.out.print(n.data+" "); if(n.left!=null) q.add(n.left); if(n.right!=null) q.add(n.right); } } private int maxLen=0; private int max(int a,int b){ return a>b?a:b; } public void findMaxDistance(Node root){ if(root==null) return; if(root.left==null) root.leftMaxDistance=0; if(root.right==null) root.rightMaxDistance=0; if(root.left!=null) findMaxDistance(root.left); if(root.right!=null) findMaxDistance(root.right); //計算左字樹中距離根結(jié)點(diǎn)的最大距離 if(root.left!=null) root.leftMaxDistance=max(root.left.leftMaxDistance, root.left.rightMaxDistance)+1; //計算右字樹中距離根結(jié)點(diǎn)的最大距離 if(root.right!=null) root.rightMaxDistance=max(root.right.leftMaxDistance, root.right.rightMaxDistance)+1; //獲取二叉樹所有結(jié)點(diǎn)的最大距離 if(root.leftMaxDistance+root.rightMaxDistance>maxLen){ maxLen=root.leftMaxDistance+root.rightMaxDistance; } } public static void main(String[] args) { BinaryTree biTree=new BinaryTree(); int[] data={2,8,7,4,9,3,1,6,7,5}; biTree.buildTree(data); System.out.print("二叉樹的中序遍歷:"); biTree.inOrder(); System.out.println(); System.out.print("二叉樹的先序遍歷:"); biTree.preOrder(); System.out.println(); System.out.print("二叉樹的后序遍歷:"); biTree.postOrder(); System.out.println(); System.out.print("二叉樹的層序遍歷:"); biTree.layerTranverse(); System.out.println(); biTree.findMaxDistance(biTree.root); System.out.println("二叉樹中結(jié)點(diǎn)的最大距離:"+biTree.maxLen); } }
以上就是本文的全部內(nèi)容,希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作能帶來一定的幫助,同時也希望多多支持腳本之家!
- 詳解Java二叉排序樹
- C語言二叉排序(搜索)樹實(shí)例
- C#代碼實(shí)現(xiàn)撲克牌排序的幾種方式
- C#實(shí)現(xiàn)的二維數(shù)組排序算法示例
- C# ListView 點(diǎn)擊表頭對數(shù)據(jù)進(jìn)行排序功能的實(shí)現(xiàn)代碼
- C# 參數(shù)按照ASCII碼從小到大排序(字典序)
- C# 字符串按 ASCII碼 排序的方法
- C#七大經(jīng)典排序算法系列(上)
- C#實(shí)現(xiàn)冒泡排序算法的代碼示例
- C#中哈希表(HashTable)用法實(shí)例詳解(添加/移除/判斷/遍歷/排序等)
- 逐步講解快速排序算法及C#版的實(shí)現(xiàn)示例
- C#使用IComparer自定義List類實(shí)現(xiàn)排序的方法
- C#實(shí)現(xiàn)二叉排序樹代碼實(shí)例
相關(guān)文章
java基礎(chǔ)之 Arrays.toString()方法詳解
這篇文章主要介紹了java基礎(chǔ)之 Arrays.toString()方法詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-02-02java中線程池最實(shí)用的創(chuàng)建與關(guān)閉指南
試中經(jīng)常會問到,創(chuàng)建一個線程池需要哪些參數(shù)啊,線程池的工作原理啊,卻很少會問到線程池如何安全關(guān)閉的,下面這篇文章主要給大家介紹了關(guān)于java中線程池最實(shí)用的創(chuàng)建與關(guān)閉的相關(guān)資料,需要的朋友可以參考下2021-09-09Spring MVC url提交參數(shù)和獲取參數(shù)
本文重要講述通過url提交參數(shù)和獲取參數(shù)的具體操作與實(shí)現(xiàn)。具有很好的參考價值。下面跟著小編一起來看下吧2017-04-04IntelliJ?IDEA?2022.2最新版本激活教程(親測可用版)永久激活工具分享
Jetbrains官方發(fā)布了?IntelliJ?IDEA2022.2?正式版,每次大的版本更新,都會有較大的調(diào)整和優(yōu)化,除本次更新全面擁抱?Java?17?外,還有對IDE?UI界面,安全性,便捷性等都做了調(diào)整和優(yōu)化完善,用戶體驗(yàn)提升不少,相信后面會有不少小伙伴跟著更新2022-08-08java讀取文件內(nèi)容,解析Json格式數(shù)據(jù)方式
這篇文章主要介紹了java讀取文件內(nèi)容,解析Json格式數(shù)據(jù)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-09-09java基礎(chǔ)-給出一個隨機(jī)字符串,判斷有多少字母?多少數(shù)字?
這篇文章主要介紹了java基礎(chǔ)-給出一個隨機(jī)字符串,判斷有多少字母?多少數(shù)字?文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-04-04Java多線程高并發(fā)中的Fork/Join框架機(jī)制詳解
本文主要介紹了 Java 多線程高并發(fā)中的 Fork/Join 框架的基本原理和其使用的工作竊取算法(work-stealing)、設(shè)計方式和部分實(shí)現(xiàn)源碼,感興趣的朋友跟隨小編一起看看吧2021-11-11java讀取枚舉類的值轉(zhuǎn)成list和map方式
這篇文章主要介紹了java讀取枚舉類的值轉(zhuǎn)成list和map方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2023-07-07