二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。
二叉搜索树的建立过程.
二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
规则:若二叉树为空,则空操作返回,否则先访问根节点,再前序遍历左子树,再后序遍历右子树.
遍历结果:A-B-D-E-C-F-G-H
public class Node {
//节点值
int val;
//左子节点引用
Node leftChild;
//右子节点引用
Node rightChild;
public void printNode() {
System.out.println(val);
}
}
public class BinaryTree {
private Node root;
}
/**
* 插入节点
*/
public void insert(int data){
Node newNode = new Node();
newNode.val = data;
if(root == null){
root = newNode;
}else {
Node current = root;
Node parent;
// 循环查找插入的位置
while(true){
parent = current;
if(data < current.val){
current = current.leftChild;
// 直到当前的节点为null
if(current == null){
// 设置当前节点的父节点的左子节点为新创建的节点
parent.leftChild = newNode;
return;
}
}else {
current = current.rightChild;
// 直到当前节点为null
if(current == null){
parent.rightChild = newNode;
return;
}
}
} // end of while(true)
}
}
/**
* 查找节点
* 查找节点也是根据其特点进行查找,某个节点的值总比左子树的值大,比右子树的值小或者等于
*/
public Node find(int value){
Node current = root;
while (current.val != value){
if(value < current.val){
current = current.leftChild;
}else {
current = current.rightChild;
}
if(current == null){ // 找到最后都没有找到
return null;
}
}
return current;
}
内容来源于网络,如有侵权,请联系作者删除!