資料結構 — 二叉樹（建立、周遊）java實作

1、連結清單的節點

package package1;

public class Node {
  //資料域
  public Object data;
  //引用域（指針域）
  public Node next;
  //無參構造器
  public Node() {
    this(null,null);
  }
  //一個參數的構造器
  public Node(Object data) {
    this(data,null);
  }
  //兩個參數
  public Node(Object data,Node next) {
    this.data = data;
    this.next = next;
  }
}
</span>

2、隊列接口

package package1;

public interface IQueue {
  public void clear();
  public boolean isEmpty();
  public int length();
  public Object peek();
  public void offer(Object x) throws Exception;
  public Object poll();
}
</span>

3、棧接口

package package1;

public interface IStack {
  public void clear();
  public boolean isEmpty();
  public int length();
  public Object peek();
  public void push(Object x) throws Exception;
  public Object pop();
}
</span>

4、鍊隊列

package package1;

public class LinkQueue implements IQueue{

  private Node front;
  private Node rear;
  
  public LinkQueue() {
    front = rear = null;
  }
  public void clear() {
    front = rear = null;
  }

  public boolean isEmpty() {
    return front == null;
  }

  public int length() {
    Node n = front;
    int length = 0;
    while(n != null) {
      n = n.next;
      length++;
    }
    return length;
  }

  public Object peek() {
    if(front != null) {
      return front.data;
    }else {
      return null;
    }
  }

  public void offer(Object x) {
    Node n = new Node(x);
    if(front != null) {
      rear.next = n;
      rear = n;
    }else {
      front = rear = n;
    }
  }

  public Object poll() {
    if(front != null) {
      Node n = front;
      front = front.next;
      if(n == rear) {
        rear = null;
      }
      return n.data;
    }else {
      return null;
    }
  }

}
</span>

4、鍊棧

package package1;

public class LinkStack implements IStack{
  //棧頂元素
  private Node top;
  //将棧置空
  public void clear() {
    top = null;
  }
  //判斷棧是否為空
  public boolean isEmpty() {
    return top == null;
  }
  //求鍊棧的長度
  public int length() {
    Node n = top;
    int length = 0;
    while(n != null) {
      n = n.next;
      length++;
    }
    return length;
  }
  //取棧頂元素，并傳回其值
  public Object peek() {
    if(!isEmpty())
      return top.data;
    else 
      return null;
  }
  //入棧
  public void push(Object x) {
    Node n = new Node(x);
    n.next = top;
    top = n;
  }
  
  //出棧
  public Object pop() {
    //this為隐式參數
    if(this.isEmpty()) {
      return null;
    }else {
      Node n = top;
      top = top.next;
      return n.data;
    }
  }
  //整個棧的周遊
  public void display() {
    Node n = top;
    while(n != null) {
      System.out.print(n.data.toString() + " ");
      n = n.next;
    }
  }
}
</span>

5、二叉樹節點

package package1;

public class BiTreeNode {

  //域
  public Object data;
  public BiTreeNode lchild,rchild;
  
  //構造空節點
  public BiTreeNode() {
    this(null);
  }
  
  //構造左右孩子域為空的二叉樹
  public BiTreeNode(Object data) {
    this(data, null, null);
  }
  
  //構造左右孩子和資料域都不為空的二叉樹
  public BiTreeNode(Object data, BiTreeNode lchild, BiTreeNode rchild) {
    this.data = data;
    this.lchild = lchild;
    this.rchild = rchild;
  }
}
</span>

6、二叉樹（包含二叉樹的基本操作）

package package1;

public class BiTree {
  //域
  private BiTreeNode root;
  
  //構造空樹
  public BiTree() {
    this.root = null;
  }
  //構造二叉樹
  public BiTree(BiTreeNode root) {
    this.root = root;
  }
  
  /*根據先根周遊和中根周遊建立一顆二叉樹
   * preOrder 先根周遊序列
   * inOrder 中根周遊序列
   * preIndex 先根周遊序列在preOrder中的開始位置
   * inIndex 中根周遊序列在inOrder中的開始位置
   * count 節點的總數
   */
  public BiTree(String preOrder, String inOrder, int preIndex, int inIndex, int count) {
    /*
     * 算法描述：
     * 1.先根和中根非空
     * 2.取先根周遊序列中第一個節點作為根節點
     * 3.找到根節點在中序中的位置
     * 4.建立根節點、左子樹、右子樹
     */
    if(count > 0){
      char r = preOrder.charAt(preIndex);
      int i = 0;
      for(; i < count; i++){
        if(r == inOrder.charAt(inIndex + i))
          break;
      }
      root = new BiTreeNode(r);
        /*
         * 先序：root：lchild：rchild
         * 中序：lchild：root：rchild
         */
      root.lchild = new BiTree(preOrder, inOrder, preIndex+1, inIndex, i).root;
      root.rchild = new BiTree(preOrder, inOrder, preIndex+i+1, inIndex+i+1, count-i-1).root;
      
    }
  }
  
  //标明空子樹的 先根周遊序列建立一棵二叉樹
  private static int index = 0;
  public BiTree(String preStr){
    char c = preStr.charAt(index++);
    if(c != '#') {
      root = new BiTreeNode(c);
      root.lchild = new BiTree(preStr).root;
      root.rchild = new BiTree(preStr).root;
    } else {
      root = null;
    }
    
  }
  
  //遞歸先根周遊
  public void preRootTraverse(BiTreeNode T) {
    if(T != null){
      System.out.print(T.data);
      preRootTraverse(T.lchild);
      preRootTraverse(T.rchild);
    }
  }
  
  /*
   * 非遞歸先根周遊
   * 1.第一層循環：棧是否為空
   * 2.不斷的通路左子樹，右子樹入棧，一會傳回（出棧）
   * 3.重點：直接通路
   */
  public void preRootTraverse() {
    BiTreeNode T = root;
    if(T != null) {
      //将root入棧之後就是不斷的入棧出棧
      LinkStack S = new LinkStack();
      S.push(T);
      //入棧出棧的過程
      while(!S.isEmpty()) {
        T = (BiTreeNode)S.pop();
        System.out.print(T.data);
        while(T != null) {
          if(T.lchild != null) {
            System.out.print(T.lchild.data);
          }
          if(T.rchild != null) {
            S.push(T.rchild);
          }
          T = T.lchild;//一直向下
        }
      }
    }
  }
  
  //遞歸中根周遊
  public void inRootTraverse(BiTreeNode T) {
    if(T != null){
      inRootTraverse(T.lchild);
      System.out.print(T.data);
      inRootTraverse(T.rchild);
    }
  }
  
  /*
   * 非遞歸中根周遊
   * 1.第一層循環同先根
   * 2.左孩子不斷入棧，然後到底之後出棧時通路輸出，之後右孩子入棧
   * 3.重點：沒有左子樹，出棧，通路
   */
  public void inRootTraverse() {
    BiTreeNode T = root;
    if(T != null) {
      LinkStack S = new LinkStack();
      S.push(T);
      while(!S.isEmpty()) {
        while(S.peek() != null) {
          S.push(((BiTreeNode)S.peek()).lchild);
        }
        //空節點出棧
        S.pop();
        if(!S.isEmpty()) {
          T = (BiTreeNode)S.pop();
          System.out.print(T.data);
          S.push(T.rchild);
      }
      
      }
    }
  }
  
  //遞歸後根周遊
  public void postRootTraverse(BiTreeNode T) {
    if(T != null){
      postRootTraverse(T.lchild);
      postRootTraverse(T.rchild);
      System.out.print(T.data);
    }
  }
  
  /*
   * 非遞歸後根周遊
   * 1.第一層同上兩個
   * 2.不斷将左子樹入棧，到底，出棧，如果出棧節點為葉子節點，通路
   * 3.重點：沒有左子樹 和 右子樹 （已經被通路了）
   */
  public void postRootTraverse() {
    BiTreeNode T = root;
    if(T != null) {
      LinkStack S = new LinkStack();
      S.push(T);
      Boolean flag;
      BiTreeNode p = null;
      while(!S.isEmpty()) {
        while(S.peek() != null) {
          S.push(((BiTreeNode)S.peek()).lchild);
        }
        S.pop();
        while(!S.isEmpty()) {
          T = (BiTreeNode)S.peek();//取棧頂元素
          if(T.rchild == null || T.rchild == p) {
            System.out.print(T.data);
            S.pop();
            p = T;
            flag = true;
          } else {
            S.push(T.rchild);
            flag = false;
          }
          if(!flag) {
            break;
          }
        }
      }
    }
  }
  
  //層次周遊（自左向右）
  
  public void levelTraverse() {
    
    BiTreeNode T = root;
    if(T != null) {
      LinkQueue L = new LinkQueue();
      L.offer(T);
      
      while(!L.isEmpty()) {
        T = (BiTreeNode)L.poll();
        
        System.out.print(T.data);
        if(T.lchild != null) {
          L.offer(T.lchild);
        }
        if(T.rchild != null) {
          L.offer(T.rchild);
        }
      }
    }
  }
  
  public BiTreeNode getRoot() {
    return root;
  }
  
  public void setRoot(BiTreeNode root) {
    this.root = root;
  }
}

7、測試程式

package package1;

public class t1 {

  public static void main(String[] args) {
    String preOrder = "ABDEGCFH";
    String inOrder = "DBGEAFHC";
    
    BiTree T = new BiTree(preOrder,inOrder,0,0,preOrder.length());
    System.out.println("先根周遊(遞歸）");
    T.preRootTraverse(T.getRoot());
    System.out.println();
    System.out.println("先根周遊(非遞歸）");
    T.preRootTraverse();
    System.out.println();
    System.out.println("中根周遊（遞歸）");
    T.inRootTraverse(T.getRoot());
    System.out.println();
    System.out.println("中根周遊（非遞歸）");
    T.inRootTraverse();
    System.out.println();
    System.out.println("後根周遊（遞歸）");
    T.postRootTraverse(T.getRoot());
    System.out.println();
    System.out.println("後根周遊（非遞歸）");
    T.postRootTraverse();
    
    System.out.println();
    System.out.println("層次周遊");
    T.levelTraverse();
  }

}
</span>

8、測試結果

資料結構 — 二叉樹（建立、周遊）java實作

繼續閱讀

nginx location中斜線的位置的重要性

資料結構與算法（27）——排序（二）

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的簡單使用

neo4j之cypher使用文檔

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

mybatis_入門程式Mybatis入門

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

Effective Java 8:通用程式設計

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

Linux裝置模型（中）之上層容器

scala (3) Function 和 Method