二叉搜索树

1、想让二叉搜索树实现按序输出，则只需要中序遍历即可

2、最大关键字和最小关键字元素

通过从树根开始沿着left leftleft孩子指针直到遇到一个null nullnull，我们总能在一颗二叉搜索树中找到一个元素，如下所示。
                                         、

二叉搜索树性质保证了MINIMUM过程的正确性。如果结点x xx没有左子树，那么由于x xx的右子树中的结点的关键字都不小于x xx的关键字，则以x xx为根的子树中的最小关键字元素就是x xx。如果结点x xx有左子树，那么由于其右子树中没有关键字小于x.key x.keyx.key，且在左子树中的每个关键字不大于x.key x.keyx.key，则以x xx为根的子树中的最小关键字一定在以x.left x.leftx.left为根的子树中。因此，MINIMUM MINIMUMMINIMUM过程一定能找到以x xx为根结点的子树的最小元素。同样地，寻求最大关键字元素的过程MAXMUM是对称的。这两个过程在一棵高度为h hh的树中均能在O(h) O(h)O(h)时间内执行完毕。

思路：用栈礼包保存，下面在判断栈为空的时候看清楚，是的用的if，为啥用if，为啥不用while，这个只有自己撸一遍代码就知道了：不能一下就把栈中 的元素弄完。

package chap8;import java.util.LinkedList;
/*** 给定一颗二叉搜索树，请找出排名第k的结点。*/
public class FindKthNode {public TreeNode  findKthNode(TreeNode pRoot,int k) {if (pRoot==null||k<=0) {return null;}LinkedList<TreeNode> stack=new LinkedList<>();int count=0;while(pRoot!=null||!stack.isEmpty()) {while(pRoot!=null) {stack.push(pRoot);pRoot=pRoot.left;}if (!stack.isEmpty()) {pRoot=stack.pop();if (++count==k) return pRoot;pRoot=pRoot.right;}}return null;}	public static void main(String[] args) {// TODO Auto-generated method stub}}