投稿
  1. 极客之音首页
  2. 技术随笔

二叉树（Java版）

小半 • • 技术随笔 • 阅读 234

导读：本篇文章讲解 二叉树（Java版），希望对大家有帮助，欢迎收藏，转发！站点地址：www.bmabk.com

文章目录

1. 二叉树的概念

  1. 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
  2. 二叉树的子节点分为左节点和右节点。
  3. 二叉树的示意图

在这里插入图片描述
4.如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2n-1 , n为层数，则我们称为满二叉树。
在这里插入图片描述
5.如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。

在这里插入图片描述
二叉树的性质：

1. 若二叉树的层次从0开始，则在二叉树的第i层最多有2i个节点（i>=0)。
2. 高度为k的二叉树最多有2k-1个节点（k >= -1）。
3. 对任何一颗二叉树，如果其叶节点的个数为n0，度为2的非叶节点个数为n2，则右n0 = n2 + 1。

2. 二叉树的遍历

2.1 前序、中序、后序遍历的说明

2.1.1 前序遍历

前序遍历：先输出父节点，再遍历左子树和右子树，简单记，即根左右。如下图中的二叉树的前序遍历结果为：A B C D E F G H。
在这里插入图片描述

2.1.2 中序遍历

中序遍历：先遍历左子树，再输出父节点，再遍历右子树，简单记，即左根右。如下图中的二叉树的中序遍历结果为：C B E D F A G H。

在这里插入图片描述

2.1.3 后序遍历

后序遍历：先遍历左子树，再遍历右子树，最后输出父节点，简单记，即左右根。如下图中的二叉树的后序遍历结果为：C E F D B G H A。
在这里插入图片描述

2.1.4 小结

看输出父节点的顺序，就可以确定是前序遍历还是中序遍历，还是后序遍历。

2.2 创建二叉树

在进行前序，中序和后序遍历代码编写之前，我们需要先构建出一颗二叉树，不妨我们就以上面的二叉树为例，把其构建出来，在下图中以给出，并写出了三种遍历结果。如果我们利用其中序遍历去构建的话，构建完C B节点后就去构建E节点就找不到关系了，所以行不通，如果我们利用后序遍历去构建的话，构建完C节点，再去构建E结点就找不到关系了 ，所以也行不通，最后我们把希望寄托在了前序遍历上。
在这里插入图片描述
利用前序遍历去构建这颗二叉树，构建完A节点，A的左孩子不为null，再构建B节点，B的左孩子不为null，再构建C节点，C的左孩子为null，然后去构建其右孩子，右孩子也为null，此时以C节点为根节点的子树 构建完毕，再去构建B的右孩子D结点…
所以我们可以根据前序遍历的结果给出这样一个数组ABC##DE##F##G#H##（null用#表示，当遇到#时返回null）。

首先给出一个节点类BtNode。

public class BtNode {
    private char date; //数据域
    private BtNode leftChild; //指向左孩子
    private BtNode rightChild; //指向右孩子

    public BtNode(char date) {
        this.date = date;
    }

    public char getDate() {
        return date;
    }

    public void setDate(char date) {
        this.date = date;
    }

    public BtNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BtNode leftChild) {
        this.leftChild = leftChild;
    }

    public BtNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BtNode rightChild) {
        this.rightChild = rightChild;
    }
}

BinaryTree类
因为在构建树过程中，需要返回节点，再去构建右孩子，此时遍历数组的下一个元素，所以我们用一个x[]代替一个普通的整型，防止构建时用的是同一个数组中的元素。

public class BinaryTree {
    private BtNode root;

    /**
     * 创建二叉树
     */
    private BtNode createTree(char[] str, int[] x) {
        BtNode t = null;
        if (str[x[0]] != '#') {
            t = new BtNode(str[x[0]]);
            x[0] += 1;
            t.setLeftChild(createTree(str, x));
            x[0] += 1;
            t.setRightChild(createTree(str, x));
        }
        return t;
    }

    public void createTree(char[] str) {
        if (str == null) {
            return;
        }
        int[] x = {0};
        root = createTree(str, x);
    }
    
}
-------------------------------------
String str = "ABC##DE##F##G#H##";
char[] arr = str.toCharArray();
BinaryTree mytree = new BinaryTree();
mytree.createTree(arr);

2.3 三种遍历的递归形式

2.3.1 前序遍历

 /**
   * 前序遍历
   */
  private void preOrder(BtNode root) {
      if (root == null) {
          return;
      }

      System.out.print(root.getDate() + " ");
      preOrder(root.getLeftChild());
      preOrder(root.getRightChild());
  }

  public void preOrder() {
      preOrder(root);
      System.out.println();
  }

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----前序遍历-----");
        mytree.preOrder();
}

测试结果
在这里插入图片描述

2.3.2 中序遍历

/**
  * 中序遍历
  */
 private void inOrder(BtNode root) {
     if (root == null) {
         return;
     }
     inOrder(root.getLeftChild());
     System.out.print(root.getDate() + " ");
     inOrder(root.getRightChild());
 }

 public void inOrder() {
     inOrder(root);
     System.out.println();
 }

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----中序遍历-----");
        mytree.inOrder();
    }
}

测试结果
在这里插入图片描述

2.3.3 中序遍历

/**
*后序遍历
*/
private void postOrder(BtNode root) {
     if (root == null) {
         return;
     }
     postOrder(root.getLeftChild());
     postOrder(root.getRightChild());
     System.out.print(root.getDate() + " ");
}

public void postOrder() {
     postOrder(root);
     System.out.println();
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----后序遍历-----");
        mytree.postOrder();
    }
}

测试结果
在这里插入图片描述

2.4 三种遍历的非递归形式

2.4.1 前序遍历

算法思想：将遍历树的指针ptr指向根节点，并将根节点入栈，判断栈是否为空，如果不为空，将栈顶元素出栈，并判断该节点的右子树是否为空，如果不为空，入栈，再判断其左子树是否为空，若不为空，入栈，循环以上步骤，直至栈为空。

代码实现如下

/**
* 非递归前序遍历
*/
public void nicePreOrder() {
   BtNode ptr = root;
   Stack<BtNode> stack = new Stack<>();
   stack.push(ptr);

   while (!stack.isEmpty()) {
       ptr = stack.pop();
       System.out.print(ptr.getDate() + " ");
       if (ptr.getRightChild() != null) {
           stack.push(ptr.getRightChild());
       }
       if (ptr.getLeftChild() != null) {
           stack.push(ptr.getLeftChild());
       }
   }
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----非递归前序遍历-----");
        mytree.nicePreOrder();
    }
}

测试结果
在这里插入图片描述

2.4.2 中序遍历

算法思想：将二叉树的根节点赋值给要进行遍历的指针ptr，用该指针进行遍历，若当前节点非空，则将该节点进行入栈操作并访问其左子树，循环执行，直到当前节点为空时，让栈顶的元素出栈，然后访问其右子树，再重复如上操作，直到ptr指向空并且栈为null时退出循环。

代码实现如下

/**
* 非递归中序遍历
*/
public void niceInOrder() {
   BtNode t = root;
   Stack<BtNode> stack = new Stack<>();

   while (t != null || !stack.isEmpty()) {
       while (t != null) {
           stack.push(t);
           t = t.getLeftChild();
       }
       t = stack.pop();
       System.out.print(t.getDate() + " ");
       t = t.getRightChild();
   }
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----非递归中序遍历-----");
        mytree.niceInOrder();
    }
}

测试结果

在这里插入图片描述

2.4.3 后序遍历

算法思想：将二叉树的根节点赋值给要进行遍历的指针ptr，用该指针进行遍历，若当前节点非空，则将该节点进行入栈操作并访问其左子树，循环执行，直到当前节点为空时，让栈顶的元素出栈，判断其右子树是否为空且是否遍历，如果非空且未遍历该右子树，再将其压入栈中并遍历其右子树；如果为空或已遍历则访问该节点并弹出栈，同时设置标记指针pre记录该节点（用于判断节点的右子树是否已经遍历），再将遍历的指针ptr置为空，下次遍历直接取出栈顶元素，直至遍历的指针为空且栈为空时退出循环。

代码实现如下

/**
* 非递归后序遍历
*/
public void nicePostOrder() {
   Stack<BtNode> stack = new Stack<>();
   BtNode ptr = root;
   BtNode pre = null;

   while (ptr != null || !stack.isEmpty()) {
       while (ptr != null) {
           stack.push(ptr);
           ptr = ptr.getLeftChild();
       }
       ptr = stack.pop();
       if (ptr.getRightChild() == null || ptr.getRightChild() == pre) {
           System.out.print(ptr.getDate() + " ");
           pre = ptr;
           ptr = null;
       } else {
           stack.push(ptr);
           ptr = ptr.getRightChild();
       }
   }
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----非递归后序遍历-----");
        mytree.nicePostOrder();
    }
}

测试结果
在这里插入图片描述

2.5二叉树的层次遍历

所谓层次遍历即按照下图所示遍历二叉树，遍历结果为：A B G C D H E F
在这里插入图片描述
算法思想：准备一个队列：将根节点入队，访问其队头元素，判断该节点的左右孩子是否为空，不为空则入队，循环直至队列为空结束。

代码实现如下

/**
* 二叉树的层次遍历
*/
public void levelOrder() {
    BtNode ptr = root;
    Queue<BtNode> queue = new LinkedList<>();
    queue.offer(ptr);
    while (!queue.isEmpty()) {
        ptr = queue.poll();
        System.out.print(ptr.getDate() + " ");
        if (ptr.getLeftChild() != null) {
            queue.offer(ptr.getLeftChild());
        }
        if (ptr.getRightChild() != null) {
            queue.offer(ptr.getRightChild());
        }
    }
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-------层次遍历-------");
        mytree.levelOrder();
    }
}

测试结果
在这里插入图片描述

2.6二叉树的s形层次遍历

所谓s形层次遍历即按照下图所示遍历二叉树，遍历结果为：A G B C D H F E
在这里插入图片描述
算法思想 :观察s形遍历的结果我们发现，奇数层从左往右打印，偶数层从右向左打印，所以我们准备两个栈进行操作，首先将根节点入栈1，然后判断栈1是否为空，显然不为空，那么将栈顶元素出栈，判断其左孩子是否未空，不为空如栈2，其右孩子是否为空，不为空如栈2，当栈1为空时，退出此循环操作；再判断栈2是否为空，不为空，将栈顶元素出栈，判断其右孩子是否为空，不为空如栈1，判断左孩子是否为空，不为空如栈1，当栈2为空时，退出此循环操作；当栈1和栈2同时为空时，退出程序。

代码实现如下

public void sOrder() {
     if (root == null) {
         return;
     }
     BtNode ptr = root;
     Stack<BtNode> stack1 = new Stack<>();
     Stack<BtNode> stack2 = new Stack<>();

     stack1.push(ptr);
     while (!stack1.isEmpty() || !stack1.isEmpty()) {
         while (!stack1.isEmpty()) {
             ptr = stack1.pop();
             System.out.print(ptr.getDate() + " ");
             if (ptr.getLeftChild() != null) {
                 stack2.push(ptr.getLeftChild());
             }
             if (ptr.getRightChild() != null) {
                 stack2.push(ptr.getRightChild());
             }
         }
         while (!stack2.isEmpty()) {
             ptr = stack2.pop();
             System.out.print(ptr.getDate() + " ");
             if (ptr.getRightChild() != null) {
                 stack1.push(ptr.getRightChild());
             }
             if (ptr.getLeftChild() != null) {
                 stack1.push(ptr.getLeftChild());
             }
         }
     }
 }

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----二叉树的s形遍历-----");
        mytree.sOrder();
    }
}

测试结果
在这里插入图片描述

3. 计算二叉树的节点个数

算法思想：一颗二叉树的节点个数等于其左孩子的节点个数+其右孩子的节点个数+1，所以我们可以用递归的思想很容易计算出二叉树的节点个数。
在这里插入图片描述

代码实现如下

private int getSize(BtNode ptr) {
    if (ptr == null) {
        return 0;
    }
    return getSize(ptr.getLeftChild()) + getSize(ptr.getRightChild()) + 1;
}

public int getSize() {
    return getSize(root);
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----二叉树的节点个数-----");
        System.out.println(mytree.getSize());
    }
}

测试结果
在这里插入图片描述

4. 计算二叉树的高度（深度）

算法思想：一颗二叉树的深度等于其左孩子的深度和其右孩子的深度的最大值再加1，同理，所以我们可以用递归的思想很容易计算出二叉树的深度。
在这里插入图片描述

代码实现如下

private int getDepth(BtNode ptr) {
    if (ptr == null) {
        return 0;
    }
    return Math.max(getDepth(ptr.getLeftChild()), getDepth(ptr.getRightChild())) + 1;
}

/**
 * 计算二叉树的深度
 */
public int getDepth() {
    return getDepth(root);
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String str = "ABC##DE##F##G#H##";
        char[] arr = str.toCharArray();

        BinaryTree mytree = new BinaryTree();
        mytree.createTree(arr);

        System.out.println("-----二叉树的高度-----");
        System.out.println(mytree.getDepth());
    }
}

测试结果
在这里插入图片描述

5. 判断二叉树是否是一颗满二叉树

在这里插入图片描述
观察一颗满二叉树我们发现，满二叉中第一层有1个节点，第二层有2个节点，第三层有4个节点，第4层有8个节点，发现规律，1 2 4 8…，成2的倍数增加，因此，我们可以准备一个队列，先把一层的结点入队列，在节点出队列的时候，判断其左右孩子是否为空，不为空，则依次入队列，一层出完队列时，判断这一层出队列的个数是否等于该层数节点的个数，如果不等于，则不是一颗满二叉树。

代码实现如下

/**
* 判断是否是一颗满二叉树
*/
public boolean isFullBinaryTree() {
   BtNode ptr = root;
   boolean tag = true;
   Deque<BtNode> queue = new LinkedList<>();
   int n = 1;
   queue.offer(ptr);

   while (!queue.isEmpty()) {
       int i = 0;
       for (; i < n; ++i) {
           ptr = queue.poll();
           if (ptr == null) {
               break;
           }
           if (ptr.getLeftChild() != null) {
               queue.offer(ptr.getLeftChild());
           }
           if (ptr.getRightChild() != null) {
               queue.offer(ptr.getRightChild());
           }
       }
       if (i != n) {
           tag = false;
           break;
       }
       n *= 2;
   }
   return tag;
}

6. 判断二叉树是否是一颗完全二叉树

在这里插入图片描述
算法思想：如何判断是不是一颗完全二叉树呢？我们不妨先把根节点入队列，然后判断队列是否为空，若不为空，进行出队操作，出栈的同时不管其左右孩子是否为空一并入队，在队不为空的情况下，依次出队并判断，出队的结点是否为空，如果为空的话就退出循环，此时再将队列中的元素依次出队，若出队的过程中发现有不为空的元素，则该树必不是一颗完全二叉树。

代码实现如下

/**
* 判断是否是一个完全二叉树
*/
public boolean isComBinaryTree() {
   BtNode ptr = root;
   boolean tag = true;
   Deque<BtNode> queue = new LinkedList<>();
   queue.offer(ptr);
   while (!queue.isEmpty()) {
       ptr = queue.poll();
       if (ptr == null) {
           break;
       }
       queue.offer(ptr.getLeftChild());
       queue.offer(ptr.getRightChild());
   }
   while (!queue.isEmpty()) {
       BtNode poll = queue.poll();
       if (poll != null) {
           tag = false;
           break;
       }
   }
   return tag;
}

7.利用前序遍历和中序遍历构建二叉树

在这里插入图片描述
通过前序遍历我们知道根节点为A，然后根据中序遍历找到根节点的位置，通过该位置对前序遍历和中序遍历进行分割，如下图所示，我们得到以A为根节点的左右子树的前序和中序遍历，按照这种方法再进行分割。
在这里插入图片描述
代码实现如下

/**
 * 根据先序遍历和中序遍历构建二叉树
 */
private BtNode createTreeByPreIn(String pre, String in, int len) {
    BtNode s = null;

    if (len > 0) {
        s = new BtNode(pre.charAt(0));
        //通过前序遍历在中序遍历中找到根节点的下标（下标为0的位置）
        int pos = in.indexOf(pre.charAt(0));
        //没有找到则异常退出
        if (-1 == pos) {
            System.exit(-1);
        }

        s.setLeftChild(createTreeByPreIn(pre.substring(1,pos + 1),in.substring(0,pos),pos));
        s.setRightChild(createTreeByPreIn(pre.substring(pos + 1,len),in.substring(pos + 1,len),len - pos - 1));
    }
    return s;
}

public void createTreeByPreIn(String pre, String in) {
    if (pre == null || in == null) {
        root = null;
    }
    root = createTreeByPreIn(pre, in, pre.length());
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String pre = "ABCDEFGH";
        String in = "CBEDFAGH";
        BinaryTree mytree = new BinaryTree();
        mytree.createTreeByPreIn(pre,in);
        mytree.nicePreOrder();
    }
}

测试结果
在这里插入图片描述

8.利用后序遍历和中序遍历构建二叉树

在这里插入图片描述
通过后序遍历我们知道根节点为A，然后根据中序遍历找到根节点的位置，通过该位置对前序遍历和中序遍历进行分割，如下图所示，我们得到以A为根节点的左右子树的后序和中序遍历，按照这种方法再进行分割。
在这里插入图片描述
代码实现如下

/**
 * 根据后序遍历和中序遍历构建二叉树
 */
private BtNode createTreeByPostIn(String post, String in, int len) {
    BtNode s = null;

    if (len > 0) {
        s = new BtNode(post.charAt(len - 1));
        //通过后序遍历在中序遍历中找到根节点的下标（下标为len - 1的位置）
        int pos = in.indexOf(post.charAt(len - 1));
        //没有找到则异常退出
        if (-1 == pos) {
            System.exit(-1);
        }
        s.setLeftChild(createTreeByPostIn(post.substring(0, pos), in.substring(0, pos), pos));
        s.setRightChild(createTreeByPostIn(post.substring(pos,len - 1),in.substring(pos + 1,len),len - pos - 1));
    }
    return s;
}

public void createTreeByPostIn(String post, String in) {
    if (post == null || in == null) {
        root = null;
    }

    root = createTreeByPostIn(post, in, post.length());
}

测试类

public class TestBinaryTree {
    public static void main(String[] args) {
        String post = "CEFDBHGA";
        String in = "CBEDFAGH";
        BinaryTree mytree = new BinaryTree();
        mytree.createTreeByPostIn(post,in);
        mytree.nicePreOrder();
    }
}

测试结果：
在这里插入图片描述

附源码

BtNode

public class BtNode {
    private char date;
    private BtNode leftChild;
    private BtNode rightChild;

    public BtNode(char date) {
        this.date = date;
    }

    public char getDate() {
        return date;
    }

    public void setDate(char date) {
        this.date = date;
    }

    public BtNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(BtNode leftChild) {
        this.leftChild = leftChild;
    }

    public BtNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(BtNode rightChild) {
        this.rightChild = rightChild;
    }
}

BinaryTree

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
    private BtNode root;

    public BtNode getRoot() {
        return root;
    }

    /**
     * 前序遍历
     */
    private void preOrder(BtNode root) {
        if (root == null) {
            return;
        }

        System.out.print(root.getDate() + " ");
        preOrder(root.getLeftChild());
        preOrder(root.getRightChild());
    }

    /**
     * 中序遍历
     */
    private void inOrder(BtNode root) {
        if (root == null) {
            return;
        }
        inOrder(root.getLeftChild());
        System.out.print(root.getDate() + " ");
        inOrder(root.getRightChild());
    }


    /**
     * 后序遍历
     */
    private void postOrder(BtNode root) {
        if (root == null) {
            return;
        }
        postOrder(root.getLeftChild());
        postOrder(root.getRightChild());
        System.out.print(root.getDate() + " ");
    }


    public void preOrder() {
        preOrder(root);
        System.out.println();
    }

    public void inOrder() {
        inOrder(root);
        System.out.println();
    }

    public void postOrder() {
        postOrder(root);
        System.out.println();
    }

    /**
     * 创建二叉树
     */
    private BtNode createTree(char[] str, int[] x) {
        BtNode t = null;
        if (str[x[0]] != '#') {
            t = new BtNode(str[x[0]]);
            x[0] += 1;
            t.setLeftChild(createTree(str, x));
            x[0] += 1;
            t.setRightChild(createTree(str, x));
        }
        return t;
    }

    public void createTree(char[] str) {
        if (str == null) {
            return;
        }
        int[] x = {0};
        root = createTree(str, x);
    }

    /**
     * 非递归中序遍历
     */
    public void niceInOrder() {
        BtNode t = root;
        Stack<BtNode> stack = new Stack<>();

        while (t != null || !stack.isEmpty()) {
            while (t != null) {
                stack.push(t);
                t = t.getLeftChild();
            }
            t = stack.pop();
            System.out.print(t.getDate() + " ");
            t = t.getRightChild();
        }
        System.out.println();
    }

    /**
     * 非递归前序遍历
     */
    public void nicePreOrder() {
        BtNode ptr = root;
        Stack<BtNode> stack = new Stack<>();
        stack.push(ptr);

        while (!stack.isEmpty()) {
            ptr = stack.pop();
            System.out.print(ptr.getDate() + " ");
            if (ptr.getRightChild() != null) {
                stack.push(ptr.getRightChild());
            }
            if (ptr.getLeftChild() != null) {
                stack.push(ptr.getLeftChild());
            }
        }
    }

    /**
     * 非递归后序遍历
     */
    public void nicePostOrder() {
        Stack<BtNode> stack = new Stack<>();
        BtNode ptr = root;
        BtNode pre = null;

        while (ptr != null || !stack.isEmpty()) {
            while (ptr != null) {
                stack.push(ptr);
                ptr = ptr.getLeftChild();
            }
            ptr = stack.pop();
            if (ptr.getRightChild() == null || ptr.getRightChild() == pre) {
                System.out.print(ptr.getDate() + " ");
                pre = ptr;
                ptr = null;
            } else {
                stack.push(ptr);
                ptr = ptr.getRightChild();
            }
        }
    }

    /**
     * 二叉树的层次遍历
     */
    public void levelOrder() {
        BtNode ptr = root;
        Queue<BtNode> queue = new LinkedList<>();
        queue.offer(ptr);
        while (!queue.isEmpty()) {
            ptr = queue.poll();
            System.out.print(ptr.getDate() + " ");
            if (ptr.getLeftChild() != null) {
                queue.offer(ptr.getLeftChild());
            }
            if (ptr.getRightChild() != null) {
                queue.offer(ptr.getRightChild());
            }
        }
    }


    /**
     * 获取二叉树的结点个数
     */
    private int getSize(BtNode ptr) {
        if (ptr == null) {
            return 0;
        }
        return getSize(ptr.getLeftChild()) + getSize(ptr.getRightChild()) + 1;
    }

    public int getSize() {
        return getSize(root);
    }

    /**
     * 计算二叉树的高度
     */
    private int getDepth(BtNode ptr) {
        if (ptr == null) {
            return 0;
        }
        return Math.max(getDepth(ptr.getLeftChild()), getDepth(ptr.getRightChild())) + 1;
    }

    /**
     * 计算二叉树的深度
     */
    public int getDepth() {
        return getDepth(root);
    }

    /**
     * 判断是否是一颗满二叉树
     */
    public boolean isFullBinaryTree() {
        BtNode ptr = root;
        boolean tag = true;
        Deque<BtNode> queue = new LinkedList<>();
        int n = 1;
        queue.offer(ptr);

        while (!queue.isEmpty()) {
            int i = 0;
            for (; i < n; ++i) {
                ptr = queue.poll();
                if (ptr == null) {
                    break;
                }
                if (ptr.getLeftChild() != null) {
                    queue.offer(ptr.getLeftChild());
                }
                if (ptr.getRightChild() != null) {
                    queue.offer(ptr.getRightChild());
                }
            }
            if (i != n) {
                tag = false;
                break;
            }
            n *= 2;
        }
        return tag;
    }

    /**
     * 判断是否是一个完全二叉树
     */
    public boolean isComBinaryTree() {
        BtNode ptr = root;
        boolean tag = true;
        Deque<BtNode> queue = new LinkedList<>();
        queue.offer(ptr);
        while (!queue.isEmpty()) {
            ptr = queue.poll();
            if (ptr == null) {
                break;
            }
            queue.offer(ptr.getLeftChild());
            queue.offer(ptr.getRightChild());
        }
        while (!queue.isEmpty()) {
            BtNode poll = queue.poll();
            if (poll != null) {
                tag = false;
                break;
            }
        }
        return tag;
    }

    /**
     * 二叉树的s遍历
     */
    public void sOrder() {
        if (root == null) {
            return;
        }
        BtNode ptr = root;
        Stack<BtNode> stack1 = new Stack<>();
        Stack<BtNode> stack2 = new Stack<>();

        stack1.push(ptr);
        while (!stack1.isEmpty() || !stack1.isEmpty()) {
            while (!stack1.isEmpty()) {
                ptr = stack1.pop();
                System.out.print(ptr.getDate() + " ");
                if (ptr.getLeftChild() != null) {
                    stack2.push(ptr.getLeftChild());
                }
                if (ptr.getRightChild() != null) {
                    stack2.push(ptr.getRightChild());
                }
            }
            while (!stack2.isEmpty()) {
                ptr = stack2.pop();
                System.out.print(ptr.getDate() + " ");
                if (ptr.getRightChild() != null) {
                    stack1.push(ptr.getRightChild());
                }
                if (ptr.getLeftChild() != null) {
                    stack1.push(ptr.getLeftChild());
                }
            }
        }
    }

    /**
     * 根据前序遍历和中序遍历构建二叉树
     */
    private BtNode createTreeByPreIn(String pre, String in, int len) {
        BtNode s = null;

        if (len > 0) {
            s = new BtNode(pre.charAt(0));
            //通过前序遍历在中序遍历中找到根节点的下标（下标为0的位置）
            int pos = in.indexOf(pre.charAt(0));
            //没有找到则异常退出
            if (-1 == pos) {
                System.exit(-1);
            }

            s.setLeftChild(createTreeByPreIn(pre.substring(1, pos + 1), in.substring(0, pos), pos));
            s.setRightChild(createTreeByPreIn(pre.substring(pos + 1, len), in.substring(pos + 1, len), len - pos - 1));
        }
        return s;
    }

    public void createTreeByPreIn(String pre, String in) {
        if (pre == null || in == null) {
            root = null;
        }
        root = createTreeByPreIn(pre, in, pre.length());
    }


    /**
     * 根据后序遍历和中序遍历构建二叉树
     */
    private BtNode createTreeByPostIn(String post, String in, int len) {
        BtNode s = null;

        if (len > 0) {
            s = new BtNode(post.charAt(len - 1));
            //通过后序遍历在中序遍历中找到根节点的下标（下标为len - 1的位置）
            int pos = in.indexOf(post.charAt(len - 1));
            //没有找到则异常退出
            if (-1 == pos) {
                System.exit(-1);
            }
            s.setLeftChild(createTreeByPostIn(post.substring(0, pos), in.substring(0, pos), pos));
            s.setRightChild(createTreeByPostIn(post.substring(pos,len - 1),in.substring(pos + 1,len),len - pos - 1));
        }
        return s;
    }

    public void createTreeByPostIn(String post, String in) {
        if (post == null || in == null) {
            root = null;
        }

        root = createTreeByPostIn(post, in, post.length());
    }

}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/95478.html

赞 (0)
小半的头像小半
0 0

相关推荐

极客之音——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！