数据结构 — 二叉树（创建、遍历）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