【Java】高级数据结构算法 -- BST树( 三 ) _节点

/*** 非递归* 在BST树种，搜索值为data的节点，找到返回true，找不到返回false* @param data* @return*/public boolean non_query(T data){BSTNode cur = this.root;while(cur != null){if(cur.getData().compareTo(data) > 0){cur = cur.getLeft();} else if(cur.getData().compareTo(data) < 0){cur = cur.getRight();} else {return true;}}return false;}}
/*** 递归查找元素data* @return*/public BSTNode query(T data){return query(this.root, data);}private BSTNode query(BSTNode root, T data) {if(root == null)return null;if(root.getData().compareTo(data) > 0){return query(root.getLeft(), data);} else if(root.getData().compareTo(data) < 0){return query(root.getRight(), data);} else {return root;}}
BST树的前序、中序、后序、层序遍历的递归实现
前序遍历
/*** 前序遍历BST树的API接口*/public void preOrder(){System.out.print("递归前序遍历:");preOrder(this.root);System.out.println();}/*** 前序遍历BST树的递归操作 VLR* @param root*/private void preOrder(BSTNode root) {if(root != null){System.out.print(root.getData() + " ");preOrder(root.getLeft());preOrder(root.getRight());}}
中序遍历
/*** 中序遍历BST树的API接口*/public void inOrder(){System.out.print("递归中序遍历:");inOrder(this.root);System.out.println();}/*** 中序遍历BST树的递归操作 LVR* @param root*/private void inOrder(BSTNode root) {if(root != null){inOrder(root.getLeft());System.out.print(root.getData() + " ");inOrder(root.getRight());}}
后序遍历
/*** 后序遍历BST树的API接口*/public void postOrder(){System.out.print("递归后序遍历:");postOrder(this.root);System.out.println();}/*** 后序遍历BST树的递归操作 LRV* @param root*/private void postOrder(BSTNode root) {if(root != null){postOrder(root.getLeft());postOrder(root.getRight());System.out.print(root.getData() + " ");}}
层序遍历
/*** 层序遍历BST树的API接口*/public void levelOrder(){System.out.print("递归层序遍历:");int hight = level();for (int i = 0; i < hight; i++) {levelOrder(this.root, i);}System.out.println();}/*** 层序遍历的递归实现* @param root* @param i*/private void levelOrder(BSTNode root, int i) {if(root != null){if(i == 0){System.out.print(root.getData() + " ");return;}levelOrder(root.getLeft(), i-1);levelOrder(root.getRight(), i-1);}}