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