java bst的中序遍历

直接上代码，仅递归实现了BST的插入，递归与循环方式实现了中序遍历；

import java.util.Stack;

public class BinarySearchTree<K extends Comparable> {
    class TreeNode<K> {
        K value;
        TreeNode<K> leftChild;
        TreeNode<K> rightChild;
        boolean hasPrint = false;

        public TreeNode(K value, TreeNode<K> leftChild, TreeNode<K> rightChild) {
            this.value = value;
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }

        public TreeNode(K value) {
            this(value, null, null);
        }
    }

    TreeNode root;

    public BinarySearchTree() {
    }

    public void add(K k) {
        root = _add(k, root);
    }

    /**
     * 递归实现树的插入节点
     *
     * @param k
     * @param node
     * @return
     */
    TreeNode _add(K k, TreeNode node) {
        if (null == node) {
            return new TreeNode(k);
        }
        if (k.compareTo(node.value) == 0) {
            // 相似 do nothing,即我们的树中不允许重复元素出现
        } else if (k.compareTo(node.value) > 0) {
            node.rightChild = _add(k, node.rightChild);
        } else {
            node.leftChild = _add(k, node.leftChild);
        }
        return node;
    }

    /**
     * 两种方式实现bst的中序遍历
     */
    public void inorder() {
        if (null == root) {
            System.out.println("empty tree");
            return;
        }
        _inorder(root);
        __inorder(root);
    }

    /**
     * 中序遍历，使用递归
     * 左子节点，节点，右子节点
     *
     * @param node
     */
    void _inorder(TreeNode node) {
        if (node.leftChild != null) {
            _inorder(node.leftChild);
        }
        System.out.println(node.value);
        if (node.rightChild != null) {
            _inorder(node.rightChild);
        }
    }

    /**
     * 中序遍历，不使用递归
     * 栈
     *
     * @param current
     */
    void __inorder(TreeNode current) {
        Stack<TreeNode> stack = new Stack();
        if (stack.size() == 0) {
            if (current.rightChild != null) {
                stack.push(current.rightChild);
            }
            stack.push(current);
            if (current.leftChild != null) {
                stack.push(current.leftChild);
            }
        }
        while ((stack.empty() == false) && ((current = stack.pop()) != null)) {
            if (current.leftChild != null) {
                if (current.leftChild.hasPrint == false) {
                    if (current.rightChild != null) {
                        stack.push(current.rightChild);
                    }
                    stack.push(current);
                    if (current.leftChild != null) {
                        stack.push(current.leftChild);
                    }
                } else {
                    System.out.println(current.value);
                    current.hasPrint = true;
                }
            }
            if (current.leftChild == null) {
                System.out.println(current.value);
                current.hasPrint = true;
                if (current.rightChild != null) {
                    stack.push(current.rightChild);
                }
            }
        }

    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();
        bst.add(10);
        bst.add(5);
        bst.add(2);
        bst.add(8);
        bst.add(6);
        bst.add(9);
        bst.add(15);
        bst.add(17);
        bst.add(20);
        bst.add(14);
        bst.inorder();
    }
}

本文地址：https://blog.csdn.net/weixin_38038479/article/details/107482573