【Java数据结构】BST树(二叉搜索树)总结04(返回中序遍历 第k个节点的值)

二叉树总结:入口

二叉树的基本操作:

1、插入,删除 操作

2、前、中、后序遍历,层序遍历

3、求BST树高度,求BST树节点个数

4、返回中序遍历第k个节点的值

5、判断一个二叉树是否是BST树,判断一个BST树,是否是AVL树

6、BST树的镜像

7、把BST树满足[begin,end]区间的值打印出来

8、判断是否是子树

9、打印二叉树。

 

返回中序遍历第k个节点的值:

出栈的时候  计数加一,然后达到数值栈顶元素即第k个元素。

//返回中序遍历   第k个节点的值
    public T getInOrderNoK(int k){
        return getInOrderNoK(this.root,k);
    }
    private T getInOrderNoK(BSTNode<T> root,int k){
        int count=0;
        Stack<BSTNode> st=new Stack<BSTNode>();
        if(count>k || root==null){
            return null;
        }
        while(!st.isEmpty()|| root!=null) {
            while (root != null) {
                st.push(root);
                root = root.getLeft();
            }
            root = st.peek();
            count++;
            if (count == k) {
                return root.getData();
            }
            st.pop();
            root = root.getRight();
        }
        return null;
    }

 

上一篇:【MOOC-浙大数据结构】第四周的编程作业——二叉搜索树&二叉排序树


下一篇:TR LA-41*300 SSI order no.305-00111 TR LA-41 305-0