构建二进制排序树与各种遍历办法-Java（带有详细说明与单元测试）

二进制排序树是具有以下属性的空树或二进制树:

（1）如果左子树不为空，则左子树上所有节点的值小于其根节点的值;

（2）如果右子树不为空，则右子树上所有节点的值都大于其根节点的值；

（3）左右子树也是二进制排序树；

（4）没有节点具有相等的键值.

如下:

树遍历方法通常具有以下方法:

（1）层次遍历: 按照树的级别遍历，如树所示: 8、3、10、1、6、14、4、7、13

（2）顺序遍历: 节点遍历顺序为当前节点，左节点和右节点. 图片树: 8、3、1、6、4、7、10、14、13

（3）中序遍历: 节点遍历顺序为左节点，当前节点和右节点. 图片树: 1、3、4、6、7、8、10、13、14

（4）后续遍历: 节点遍历顺序为左节点，右节点二叉排序树的建立，当前节点. 如树所示: 1，4，7，6，3，8，13二叉排序树的建立，14，10

package com.lee.wait;
/**
 * Node 二叉树上的节点
 * @author wait
 *
 */
public class Node {
    /**
     * 节点的数据，这里我们用一个int表示
     */
    public int data;
    /**
     * 节点的左孩子
     */
    public Node left;
    /**
     * 节点的右孩子
     */
    public Node right;
    /**
     * 构造函数，data初始化节点的值
     * @param data
     */
    public Node(int data){
        this.data=data;
    }
    /**
     * 默认构造函数，data=0
     */
    public Node(){
        this(0);
    }
}

（2）二进制排序树类BTree.java

package com.lee.wait;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
/**
 * BTree二叉排序树类
 * 
 * @author wait
 * 
 */
public class BTree {
    /**
     * 树的根节点
     */
    public Node root;
    /**
     * 记录树的节点个数
     */
    public int size;
    /**
     * 默认构造函数，树的根节点为null
     */
    public BTree() {
        root = null;
        size = 0;
    }
    /**
     * 插入一个新的节点node
     * 
     * @param node
     */
    public void insert(Node node) {
        if (root == null) {
            root = node;
            size++;
            return;
        }
        Node current = root;
        while (true) {
            if (node.data <= current.data) {
                // 如果插入节点的值小于当前节点的值，说明应该插入到当前节点左子树，而此时如果左子树为空，就直接设置当前节点的左子树为插入节点。
                if (current.left == null) {
                    current.left = node;
                    size++;
                    return;
                }
                current = current.left;
            } else {
                // 如果插入节点的值大于当前节点的值，说明应该插入到当前节点右子树，而此时如果右子树为空，就直接设置当前节点的右子树为插入节点。
                if (current.right == null) {
                    current.right = node;
                    size++;
                    return;
                }
                current = current.right;
            }
        }
    }
    /**
     * 插入一个值为data的节点
     * 
     * @param data
     */
    public void insert(int data) {
        insert(new Node(data));
    }
    /**
     * 根据int数组里面的值建立一个二叉排序树
     * 
     * @param datas
     */
    public void bulidTree(int[] datas) {
        for (int i = 0, len = datas.length; i < len; i++) {
            insert(datas[i]);
        }
    }
    /**
     * 返回二叉排序树的层次遍历的结果，使用通用的广度优先遍历方法
     * 
     * @return 以int数组的形式返回结果
     */
    public int[] layerOrder() {
        int[] res = new int[size];
        if (root == null) {
            return res;
        }
        // 用一个队列存储节点的顺序，一次放入根节点，根的左孩子节点，根的右孩子节点
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        int i = 0;
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            res[i++] = current.data;
            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }
        }
        return res;
    }
    /**
     * 先序遍历二叉排序树，非递归的方法，深度优先思想
     * 
     * @return 以int数组的形式返回结果
     */
    public int[] preOrder() {
        int[] res = new int[size];
        int i = 0;
        //使用stack存储遍历到的节点
        Stack<Node> stack = new Stack<Node>();
        Node node = root;
        while (node != null) {
            //一直往下遍历，知道到左孩子节点为空
            while (node != null) {
                stack.push(node);
                res[i++] = node.data;
                node = node.left;
            }
            //左孩子节点为空之后，往后找，如果找到的上一个节点的右孩子节点为空，那么继续往上找，直到找到一个右孩子节点不为空的
            while (!stack.isEmpty() && stack.peek().right == null) {
                node = stack.pop();
            }
            if(!stack.isEmpty()){
                node=stack.pop();
                //找到了一个右孩子节点不为空的节点，就去遍历他的右孩子节点
                if (node != null) {
                    node = node.right;
                }
            }else{
                node=null;
            }
        }
        return res;
    }
    /**
     * 中序遍历二叉排序树  非递归的方法，深度优先思想
     * @return
     */
    public int[] inOrder() {
        int[] res = new int[size];
        int i = 0;
        //使用stack存储遍历到的节点
        Stack<Node> stack = new Stack<Node>();
        Node node = root;
        while (node != null) {
            //一直往下遍历，知道到左孩子节点为空
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            //左孩子节点为空之后，往后找，找到上一个节点.如果找到的上一个节点的右孩子节点为空，那么继续往上找，直到找到一个右孩子节点不为空的
            while (!stack.isEmpty() && stack.peek().right == null) {
                node = stack.pop();
                res[i++] = node.data;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                res[i++] = node.data;
                //找到了一个右孩子节点不为空的节点，就去遍历他的右孩子节点
                if (node != null) {
                    node = node.right;
                }
            }else{
                node=null;
            }
        }
        return res;
    }
    /**
     * 后序遍历二叉排序树  非递归的方法，深度优先思想
     * @return
     */
    public int[] postOrder() {
        int[] res = new int[size];
        int i = 0;
        //使用stack存储遍历到的节点
        Stack<Node> stack = new Stack<Node>();
        Node node = root;
        //存储每个节点是否访问被回访过，也就是是否是从左子树还是右子树回访的。
        Stack<Boolean> stackFlag=new Stack<Boolean>();
        while (node != null) {
            //一直往下遍历，知道到左孩子节点为空
            while (node != null) {
                stack.push(node);
                stackFlag.add(false);
                node = node.left;
            }
            //左孩子节点为空之后，往后找，找到上一个节点.如果找到的上一个节点的右孩子节点为空，那么继续往上找，直到找到一个右孩子节点不为空的
            while (!stack.isEmpty() && (stack.peek().right == null||stackFlag.peek()==true)) {
                node = stack.pop();
                stackFlag.pop();
                res[i++] = node.data;
            }
            if (!stack.isEmpty()) {
                node=stack.peek();
                stackFlag.pop();
                stackFlag.add(true);
                //找到了一个右孩子节点不为空的节点，就去遍历他的右孩子节点
                if (node != null) {
                    node = node.right;
                }
            }else{
                node=null;
            }
        }
        return res;
    }
    /**
     * 先序遍历，递归方法实现
     * @param node 当前访问的节点
     * @param list 存储节点值的容器
     */
    private void preOrderRe(Node node,List<Integer> list){
        if(list==null){
            list=new ArrayList<>();
        }
        if(node==null){
            return;
        }
        list.add(node.data);
        if(node.left!=null){
            preOrderRe(node.left,list);
        }
        if(node.right!=null){
            preOrderRe(node.right,list);
        }
    }
    /**
     * 先序遍历，递归 调用上面实现函数
     * @return
     */
    public int[] preOrderRe(){
        List<Integer> list = new ArrayList<>();
        preOrderRe(root, list);
        int[] res=new int[size];
        for(int i=0,size=list.size();i<size;i++){
            res[i]=list.get(i);
        }
        return res;
    }
    /**
     * 中序遍历，递归方法实现
     * @param node 当前访问的节点
     * @param list 存储节点值的容器
     */
    private void inOrderRe(Node node,List<Integer> list){
        if(list==null){
            list=new ArrayList<>();
        }
        if(node==null){
            return;
        }
        if(node.left!=null){
            inOrderRe(node.left,list);
        }
        list.add(node.data);
        if(node.right!=null){
            inOrderRe(node.right,list);
        }
    }
    /**
     * 中序遍历，递归 调用上面实现函数
     * @return
     */
    public int[] inOrderRe(){
        List<Integer> list = new ArrayList<>();
        inOrderRe(root, list);
        int[] res=new int[size];
        for(int i=0,size=list.size();i<size;i++){
            res[i]=list.get(i);
        }
        return res;
    }
    /**
     * 后序遍历，递归方法实现
     * @param node 当前访问的节点
     * @param list 存储节点值的容器
     */
    private void postOrderRe(Node node,List<Integer> list){
        if(list==null){
            list=new ArrayList<>();
        }
        if(node==null){
            return;
        }
        if(node.left!=null){
            postOrderRe(node.left,list);
        }
        if(node.right!=null){
            postOrderRe(node.right,list);
        }
        list.add(node.data);
    }
    /**
     * 后序遍历，递归 调用上面实现函数
     * @return
     */
    public int[] postOrderRe(){
        List<Integer> list = new ArrayList<>();
        postOrderRe(root, list);
        int[] res=new int[size];
        for(int i=0,size=list.size();i<size;i++){
            res[i]=list.get(i);
        }
        return res;
    }
}

（3）测试代码TestBTree.java

本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-252817-1.html