欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java bst的中序遍历

程序员文章站 2022-06-28 18:22:12
直接上代码,仅递归实现了BST的插入,递归与循环方式实现了中序遍历;`import java.util.Stack;public class BinarySearchTree {class TreeNode {K value;TreeNode leftChild;TreeNode rightChild;boolean hasPrint = false; public TreeNode(K value, TreeNode leftChild, TreeNode

直接上代码,仅递归实现了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

相关标签: java 数据结构