欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

二叉排序樹的實(shí)現(xiàn)與基本操作

 更新時間:2016年12月23日 11:10:23   作者:一個弱者想變強(qiáng)  
二叉排序樹又稱二叉查找樹。本文主要對二叉排序樹的實(shí)現(xiàn)與基本操作進(jìn)行詳細(xì)介紹,以下代碼實(shí)現(xiàn)了:1、二叉樹的構(gòu)建;2、二叉樹的中、前、后、層序遍歷;3、二叉樹中結(jié)點(diǎ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í)或者工作能帶來一定的幫助,同時也希望多多支持腳本之家!

相關(guān)文章

  • java基礎(chǔ)之 Arrays.toString()方法詳解

    java基礎(chǔ)之 Arrays.toString()方法詳解

    這篇文章主要介紹了java基礎(chǔ)之 Arrays.toString()方法詳解,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-02-02
  • java中線程池最實(shí)用的創(chuàng)建與關(guān)閉指南

    java中線程池最實(shí)用的創(chuàng)建與關(guān)閉指南

    試中經(jīng)常會問到,創(chuàng)建一個線程池需要哪些參數(shù)啊,線程池的工作原理啊,卻很少會問到線程池如何安全關(guān)閉的,下面這篇文章主要給大家介紹了關(guān)于java中線程池最實(shí)用的創(chuàng)建與關(guān)閉的相關(guān)資料,需要的朋友可以參考下
    2021-09-09
  • Mac安裝Maven的幾種方法小結(jié)

    Mac安裝Maven的幾種方法小結(jié)

    本文主要介紹了Mac安裝Maven的幾種方法小結(jié),主要包括通過Homebrew安裝Maven,通過SDKMAN安裝Maven和通過官方網(wǎng)站下載安裝包安裝Maven,感興趣的可以了解一下
    2024-01-01
  • Spring MVC url提交參數(shù)和獲取參數(shù)

    Spring MVC url提交參數(shù)和獲取參數(shù)

    本文重要講述通過url提交參數(shù)和獲取參數(shù)的具體操作與實(shí)現(xiàn)。具有很好的參考價值。下面跟著小編一起來看下吧
    2017-04-04
  • IntelliJ?IDEA?2022.2最新版本激活教程(親測可用版)永久激活工具分享

    IntelliJ?IDEA?2022.2最新版本激活教程(親測可用版)永久激活工具分享

    Jetbrains官方發(fā)布了?IntelliJ?IDEA2022.2?正式版,每次大的版本更新,都會有較大的調(diào)整和優(yōu)化,除本次更新全面擁抱?Java?17?外,還有對IDE?UI界面,安全性,便捷性等都做了調(diào)整和優(yōu)化完善,用戶體驗(yàn)提升不少,相信后面會有不少小伙伴跟著更新
    2022-08-08
  • java讀取文件內(nèi)容,解析Json格式數(shù)據(jù)方式

    java讀取文件內(nèi)容,解析Json格式數(shù)據(jù)方式

    這篇文章主要介紹了java讀取文件內(nèi)容,解析Json格式數(shù)據(jù)方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-09-09
  • java基礎(chǔ)-給出一個隨機(jī)字符串,判斷有多少字母?多少數(shù)字?

    java基礎(chǔ)-給出一個隨機(jī)字符串,判斷有多少字母?多少數(shù)字?

    這篇文章主要介紹了java基礎(chǔ)-給出一個隨機(jī)字符串,判斷有多少字母?多少數(shù)字?文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-04-04
  • Java多線程高并發(fā)中的Fork/Join框架機(jī)制詳解

    Java多線程高并發(fā)中的Fork/Join框架機(jī)制詳解

    本文主要介紹了 Java 多線程高并發(fā)中的 Fork/Join 框架的基本原理和其使用的工作竊取算法(work-stealing)、設(shè)計方式和部分實(shí)現(xiàn)源碼,感興趣的朋友跟隨小編一起看看吧
    2021-11-11
  • java 可重啟線程及線程池類的設(shè)計(詳解)

    java 可重啟線程及線程池類的設(shè)計(詳解)

    下面小編就為大家?guī)硪黄猨ava 可重啟線程及線程池類的設(shè)計(詳解)。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • java讀取枚舉類的值轉(zhuǎn)成list和map方式

    java讀取枚舉類的值轉(zhuǎn)成list和map方式

    這篇文章主要介紹了java讀取枚舉類的值轉(zhuǎn)成list和map方式,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-07-07

最新評論