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

JAVA 實(shí)現(xiàn)二叉樹(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))

 更新時(shí)間:2016年07月12日 16:20:45   投稿:lqh  
本篇文章主要介紹用JAVA 實(shí)現(xiàn)二叉樹,并提供實(shí)例.對(duì)二叉樹數(shù)據(jù)結(jié)構(gòu)很好的學(xué)習(xí)實(shí)踐,有需要的朋友可以參考下

二叉樹的分類(按存儲(chǔ)結(jié)構(gòu))

樹的分類(按存儲(chǔ)結(jié)構(gòu))

              順序存儲(chǔ)(用數(shù)組表示(靜態(tài)二叉樹))
      鏈?zhǔn)酱鎯?chǔ)

一些特別的二叉根:

                                   完全二叉樹,平衡二叉樹(AVL),線索二叉樹,三叉的(帶父親的指針)
            二叉搜索樹或者叫二叉 查找樹(BST)

 所用二叉樹如下圖所示:

 

二叉樹的Java實(shí)現(xiàn)(鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))

class TreeNode {
  private int key = 0;
  private String data = null;
  private boolean isVisted = false;
  private TreeNode leftChild = null;
  private TreeNode rightChild = null;
  
  public TreeNode(){
    
  }
  public TreeNode(int key, String data){
    this.key = key;
    this.data = data;
    this.leftChild = null;
    this.rightChild = null;
  }
  public int getKey() {
    return key;
  }
  public void setKey(int key) {
    this.key = key;
  }
  public String getData() {
    return data;
  }
  public void setData(String data) {
    this.data = data;
  }
  public TreeNode getLeftChild() {
    return leftChild;
  }
  public void setLeftChild(TreeNode leftChild) {
    this.leftChild = leftChild;
  }
  public TreeNode getRightChild() {
    return rightChild;
  }
  public void setRightChild(TreeNode rightChild) {
    this.rightChild = rightChild;
  }
  public boolean isVisted() {
    return isVisted;
  }
  public void setVisted(boolean isVisted) {
    this.isVisted = isVisted;
  }
}

public class BinaryTree {

  private TreeNode root = null;

  public BinaryTree() {
    root = new TreeNode(1, "rootNode(A)");
  }
  public void createBinTree(TreeNode root){
    //手動(dòng)的創(chuàng)建(結(jié)構(gòu)如圖所示)
    TreeNode newNodeB = new TreeNode(2,"B");
    TreeNode newNodeC = new TreeNode(3,"C");
    TreeNode newNodeD = new TreeNode(4,"D");
    TreeNode newNodeE = new TreeNode(5,"E");
    TreeNode newNodeF = new TreeNode(6,"F");
    root.setLeftChild(newNodeB);
    root.setRightChild(newNodeC);
    root.getLeftChild().setLeftChild(newNodeD);
    root.getLeftChild().setRightChild(newNodeE);
    root.getRightChild().setRightChild(newNodeF);
  }
  public boolean IsEmpty() {
    // 判二叉樹空否
    return root == null;
  }

  public int Height() {
    // 求樹高度
    return Height(root);
  }

  public int Height(TreeNode subTree) {
    if (subTree == null)
      return 0; //遞歸結(jié)束:空樹高度為0
    else {
      int i = Height(subTree.getLeftChild());
      int j = Height(subTree.getRightChild());
      return (i < j) ? j + 1 : i + 1;
    }

  }

  public int Size() {
    // 求結(jié)點(diǎn)數(shù)
    return Size(root);
  }

  public int Size(TreeNode subTree) {
    if (subTree == null)
      return 0;
    else {
      return 1 + Size(subTree.getLeftChild())
          + Size(subTree.getRightChild());
    }
  }

  public TreeNode Parent(TreeNode element) {
    //返回雙親結(jié)點(diǎn)
    return (root == null || root == element) ? null : Parent(root, element);
  }

  public TreeNode Parent(TreeNode subTree, TreeNode element) {

    if (subTree == null)
      return null;
    if (subTree.getLeftChild() == element
        || subTree.getRightChild() == element)
      //找到, 返回父結(jié)點(diǎn)地址
      return subTree;
    TreeNode p;
    //先在左子樹中找,如果左子樹中沒有找到,才到右子樹去找
    if ((p = Parent(subTree.getLeftChild(), element)) != null)
      //遞歸在左子樹中搜索
      return p;
    else
      //遞歸在左子樹中搜索
      return Parent(subTree.getRightChild(), element);

  }

  public TreeNode LeftChild(TreeNode element) {
    //返回左子樹
    return (element != null) ? element.getLeftChild() : null;
  }

  public TreeNode RightChild(TreeNode element) {
    //返回右子樹
    return (element != null) ? element.getRightChild() : null;
  }

  public TreeNode getRoot() {
    //取得根結(jié)點(diǎn)
    return root;
  }

  public void destroy(TreeNode subTree) {
    //私有函數(shù): 刪除根為subTree的子樹
    if (subTree != null) {
      destroy(subTree.getLeftChild()); //刪除左子樹
      destroy(subTree.getRightChild()); //刪除右子樹
      //delete subTree;       //刪除根結(jié)點(diǎn)
      subTree = null;
    }
  }

  public void Traverse(TreeNode subTree) {

    System.out.println("key:" + subTree.getKey() + "--name:"
        + subTree.getData());
    Traverse(subTree.getLeftChild());
    Traverse(subTree.getRightChild());
  }

  public void PreOrder(TreeNode subTree) {
    //先根
    if (subTree != null) {
      visted(subTree);
      PreOrder(subTree.getLeftChild());
      PreOrder(subTree.getRightChild());
    }
  }

  public void InOrder(TreeNode subTree) {
    //中根
    if (subTree != null) {
      InOrder(subTree.getLeftChild());
      visted(subTree);
      InOrder(subTree.getRightChild());
    }
  }

  public void PostOrder(TreeNode subTree) {
    //后根
    if (subTree != null) {
      PostOrder(subTree.getLeftChild());
      PostOrder(subTree.getRightChild());
      visted(subTree);
    }
  }
  public void LevelOrder(TreeNode subTree) {
     //水平遍邊
  }
  public boolean Insert(TreeNode element){
    //插入
    return true;
  }
  public boolean Find(TreeNode element){
    //查找
    return true;
  }
  public void visted(TreeNode subTree) {
    subTree.setVisted(true);
    System.out.println("key:" + subTree.getKey() + "--name:"
        + subTree.getData());
  }

  public static void main(String[] args) {
    BinaryTree bt = new BinaryTree();
    bt.createBinTree(bt.root);
    System.out.println("the size of the tree is " + bt.Size());
    System.out.println("the height of the tree is " + bt.Height());
    System.out.println("*******先根(前序)[ABDECF]遍歷*****************");
    bt.PreOrder(bt.root);
    System.out.println("*******中根(中序)[DBEACF]遍歷*****************");
    bt.InOrder(bt.root);
    System.out.println("*******后根(后序)[DEBFCA]遍歷*****************");
    bt.PostOrder(bt.root);
  }

}

 結(jié)果輸出:
the size of the tree is 6
the height of the tree is 3
*******先根(前序)[ABDECF]遍歷*****************
key:1--name:rootNode(A)
key:2--name:B
key:4--name:D
key:5--name:E
key:3--name:C
key:6--name:F
*******中根(中序)[DBEACF]遍歷*****************
key:4--name:D
key:2--name:B
key:5--name:E
key:1--name:rootNode(A)
key:3--name:C
key:6--name:F
*******后根(后序)[DEBFCA]遍歷*****************
key:4--name:D
key:5--name:E
key:2--name:B
key:6--name:F
key:3--name:C
key:1--name:rootNode(A)

 希望本文對(duì)學(xué)習(xí)JAVA程序設(shè)計(jì)的同學(xué)有所幫助。

相關(guān)文章

  • AsyncHttpClient的ConnectionSemaphore方法源碼流程解讀

    AsyncHttpClient的ConnectionSemaphore方法源碼流程解讀

    這篇文章主要為大家介紹了AsyncHttpClient的ConnectionSemaphore方法源碼流程解讀,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2023-12-12
  • Jersey Restful接口如何獲取參數(shù)的問題

    Jersey Restful接口如何獲取參數(shù)的問題

    這篇文章主要介紹了Jersey Restful接口如何獲取參數(shù)的操作,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • java web SpringMVC后端傳json數(shù)據(jù)到前端頁(yè)面實(shí)例代碼

    java web SpringMVC后端傳json數(shù)據(jù)到前端頁(yè)面實(shí)例代碼

    本篇文章主要介紹了java web SpringMVC后端傳json數(shù)據(jù)到前端頁(yè)面實(shí)例代碼,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下。
    2017-03-03
  • Java實(shí)現(xiàn)代碼塊耗時(shí)測(cè)算工具類

    Java實(shí)現(xiàn)代碼塊耗時(shí)測(cè)算工具類

    這篇文章主要為大家介紹了如何利用Java語(yǔ)言編寫一個(gè)工具類,用來(lái)測(cè)算代碼塊的耗時(shí),同時(shí)還能顯示進(jìn)度,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2023-05-05
  • Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例講解

    Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例講解

    這篇文章主要介紹了Java模擬棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)的基本示例,棧的后進(jìn)先出和隊(duì)列的先進(jìn)先出是數(shù)據(jù)結(jié)構(gòu)中最基礎(chǔ)的知識(shí),本文則又對(duì)Java實(shí)現(xiàn)棧和隊(duì)列結(jié)構(gòu)的方法進(jìn)行了細(xì)分,需要的朋友可以參考下
    2016-04-04
  • Spring多數(shù)據(jù)源導(dǎo)致配置失效的解決

    Spring多數(shù)據(jù)源導(dǎo)致配置失效的解決

    這篇文章主要介紹了Spring多數(shù)據(jù)源導(dǎo)致配置失效的解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2024-01-01
  • jar命令修改jar包中的application.yml配置文件

    jar命令修改jar包中的application.yml配置文件

    本文主要介紹了jar命令修改jar包中的application.yml配置文件,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2023-08-08
  • java語(yǔ)法糖之jdk迭代的新特性匯總

    java語(yǔ)法糖之jdk迭代的新特性匯總

    什么是語(yǔ)法糖?泛型、自動(dòng)裝箱拆箱、變長(zhǎng)參數(shù)、增強(qiáng)for循環(huán)、switch字符類型、lambda表達(dá)式等,這些其實(shí)都是語(yǔ)法糖。這篇文章主要給大家介紹了關(guān)于java語(yǔ)法糖之jdk迭代的新特性的相關(guān)資料,需要的朋友可以參考下
    2021-05-05
  • java語(yǔ)言圖形用戶登錄界面代碼

    java語(yǔ)言圖形用戶登錄界面代碼

    這篇文章主要為大家詳細(xì)介紹了java語(yǔ)言圖形用戶登錄界面代碼,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2016-06-06
  • 使用Feign設(shè)置Token鑒權(quán)調(diào)用接口

    使用Feign設(shè)置Token鑒權(quán)調(diào)用接口

    這篇文章主要介紹了使用Feign設(shè)置Token鑒權(quán)調(diào)用接口,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-03-03

最新評(píng)論