Java 二叉搜索树 实现六种遍历方法_java二叉搜索树遍历

目录

 创建二叉搜索树对象

         让T泛型继承Comparable接口

         创建内部类

实现遍历方法

        前序遍历

                递归实现 

                非递归实现  

        中序遍历

                递归实现  

                非递归实现 

        后序遍历 

                递归实现  

                非递归实现  

---

 创建二叉搜索树对象

         让T泛型继承Comparable接口

public class BinarySearchTree<T extends Comparable<T>, V> {
    //  根节点
    private TreeNode<T, V> root;
}

         创建内部类

    private static class TreeNode<T, V> {
        public T key;
        public V value;
        public TreeNode<T, V> left;
        public TreeNode<T, V> right;
 
        public TreeNode(T key) {
            this.key = key;
        }
 
        public TreeNode(T key, V value) {
            this.key = key;
            this.value = value;
        }
 
        @Override
        public String toString() {
            return "{" +
                    "key=" + key +
                    ", value=" + value +
                    '}';
        }
 
        public TreeNode(T key, V value, TreeNode<T, V> left, TreeNode<T, V> right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

实现遍历方法

        前序遍历

                递归实现 

    /**
     * 前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }
 
    /**
     * 前序遍历
     *
     * @param root -根结点
     */
    private void preOrder(TreeNode<T, V> root) {
        if (root == null) {
            return;
        }
        System.out.println(root.toString());
        preOrder(root.left);
        preOrder(root.right);
    }

                非递归实现  

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
 
        TreeNode pop = null;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                //  待处理左子数
                //  将节点压入栈
                stack.push(node);
                list.add(node.val);
                node = node.left;
            } else {
                //处理右子数
 
                //  记录栈顶元素
                TreeNode peek = stack.peek();
                //  没有右子数
                if (peek.right == null) {
                    pop = stack.pop();
                }
                //  右子数处理完成
                else if (peek.right == pop) {
                    pop = stack.pop();
                }
                //  待处理右子数
                else {
                    node = peek.right;
                }
            }
        }
        return list;
    }

        中序遍历

                递归实现  

    /**
     * 中序遍历
     */
    public void inOrder() {
        inOrder(root);
    }
 
    /**
     * 中序遍历
     *
     * @param root -根结点
     */
    private void inOrder(TreeNode<T, V> root) {
        if (root == null) {
            return;
        }
        preOrder(root.left);
        System.out.println(root.toString());
        preOrder(root.right);
    }

                非递归实现 

 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
 
        Stack<TreeNode> stack = new Stack<TreeNode>();
 
        TreeNode node = root;
        TreeNode pop = null;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null) {
                    list.add(peek.val);
                    pop = stack.pop();
                } else if (peek.right == pop) {
                    pop = stack.pop();
                } else {
                    list.add(peek.val);
                    node = peek.right;
                }
            }
        }
        return list;
    }

后序遍历 

                递归实现  

   /**
     * 后序遍历
     */
    public void postOrder() {
        postOrder(root);
    }
 
    /**
     * 后序遍历
     *
     * @param root -根结点
     */
    private void postOrder(TreeNode<T, V> root) {
        if (root == null) {
            return;
        }
        preOrder(root.left);
        preOrder(root.right);
        System.out.println(root.toString());
    }

                非递归实现  

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode node = root;
        TreeNode pop = null;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null) {
                    pop = stack.pop();
                    list.add(pop.val);
                } else if (peek.right == pop) {
                    pop = stack.pop();
                    list.add(pop.val);
                } else {
                    node = peek.right;
                }
            }
        }
        return list;
    }