二叉树具有唯一的根节点 二叉树每个节点最多有两个孩子 二叉树每个节点最多有一个父亲节点,根节点是唯一没有父亲节点的。 二叉树具有天然递归结构。 每个节点的子树都可以看做是二叉树。
image.png
二分搜索树是二叉树 二分搜索树的每个节点的值: 左子树上所有的节点的值都小于它的根节点的值。 右子树上所有的节点的值均小于它的根节点的值。 每一颗子树也是二分搜索树。
image.png
二分搜索树 递归实现
public void add(E e){
root = add(root,e);
}
/**
* 二分搜索树插入元素 递归实现
*/
private Node add(Node node ,E e){
if (node==null){
size++;
return new Node(e);
}
if (e.compareTo(node.data)<0){
node.left = add(node.left,e);
}else if (e.compareTo(node.data)>0){
node.right = add(node.right,e);
}
return node;
}
二分搜索树 查找递归实现
public boolean contains(E e){
return contains(root, e);
}
private boolean contains(Node node,E e){
if (node==null){
return false;
}if (e.compareTo(node.data)==0){
return true;
}else if(e.compareTo(node.data)<0){
return contains(node.left,e);
}else {
return contains(node.right,e);
}
}
前序遍历
public void preOrder(Node node){
if (node==null){
return;
}
System.out.println(node.data);
preOrder(node.left);
preOrder(node.right);
}
中序遍历
private void inOrder(Node node) {
if (node == null) {
return;
}
preOrder(node.left);
System.out.println(node.data);
preOrder(node.right);
}