二叉排序树介绍
对于二叉排序树的任何一个非叶子节点,要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大
特别说明:如果有相同的值,可以将该节点放在左子节点或右子节点
二叉排序树的创建和遍历
代码实现
public class BinarySotrTree { public static void main(String[] args) { int[] arr ={7,3,10,12,5,1,9}; BinarySortTre binarySortTre = new BinarySortTre(); for (int i = 0; i <arr.length ; i++) { binarySortTre.add(new Node(arr[i])); }
binarySortTre.infixOrder(); } }
class BinarySortTre{ private Node root; public void add(Node node){ if (root == null){ root = node; }else { root.add(node); } } public void infixOrder(){ if(root != null){ root.infixOrder(); }else { System.out.println("二叉排序树为空不能遍历"); } } }
class Node{ int value; Node left; Node right;
@Override public String toString() { return "Node{" + "value=" + value + '}'; }
public Node(int value) { this.value = value; } public void add(Node node){ if (node == null){ return; } if (node.value <this.value){ if (this.left ==null){ this.left =node; }else { this.left.add(node); } }else { if (this.right == null){ this.right =node; }else { this.right.add(node); } } } public void infixOrder() { if (this.left != null) { this.left.infixOrder(); } System.out.println(this); if (this.right != null) { this.right.infixOrder(); } } }
|