二叉树分为:
普通的二叉树;线索二叉树;二叉排序树;平衡二叉树;哈夫曼树
下面的代码是 BST 的实现
package 算法;
public class 树 {
// 树的抽象类
interface Tree {
// 查找节点
Node find(int key);
// 插入新节点
boolean insert(int key);
// 删除节点
boolean delete(int key);
// 中序遍历
public void infixOrder(Node current);
// 前序遍历
public void preOrder(Node current);
// 后序遍历
public void postOrder(Node current);
}
// 树中的每个结点
public static class Node {
private int data; // 数据节点
private Node leftNode; // 左节点
private Node rightNode; // 右节点
// 输出节点数据
public void display() {
System.out.println(data);
}
public void setData(int data) {
this.data = data;
}
public Node() {
}
public Node(int data) {
this.data = data;
}
}
// 二叉树 (二叉排序树)
public static class BinaryTree implements Tree {
Node root;
// 查找节点
@Override
public Node find(int key) {
Node current = root;
while (current != null) {
if (current.data > key) {
current = current.leftNode;
} else if (current.data < key) {
current = current.rightNode;
} else {
return current;
}
}
return null;
}
// 插入节点
@Override
public boolean insert(int key) {
Node newNode = new Node(key);
if (root == null) {
root = newNode;
return true;
} else {
Node current = root;
Node parentNode = null;
while (current != null) {
parentNode = current;
if (current.data > key) {
current = current.leftNode;
if (current == null) {
parentNode.leftNode = newNode;
return true;
}
}else {
current = current.rightNode;
if (current == null) {
parentNode.rightNode = newNode;
return true;
}
}
}
}
return false;
}
// 删除节点
@Override
public boolean delete(int key) {
return false;
}
/**
* 中序
* <p>
* 遍历顺序:
* </p>
* </br>
* <p>
* 左节点->根节点->右节点
* </p>
* @param current 当前遍历的节点
*/
@Override
public void infixOrder(Node current) {
if (current != null) {
infixOrder(current.leftNode); // 左节点
System.out.print(current.data+" \t"); // 根节点
infixOrder(current.rightNode); // 右节点
}
}
/**
* 前序
* <p>
* 遍历顺序:
* </p>
* </br>
* <p>
* 根节点->左节点->右节点
* </p>
* @param current 当前节点
*/
@Override
public void preOrder(Node current) {
if (current != null) {
System.out.print(current.data + "\t"); // 根节点
preOrder(current.leftNode); // 左节点
preOrder(current.rightNode); // 右节点
}
}
/**
* 后序
* </p>
* </br>
* <p>
* 左节点->右节点->根节点
* </p>
* @param current 当前节点
*/
@Override
public void postOrder(Node current) {
if (current != null) {
postOrder(current.leftNode); // 左节点
postOrder(current.rightNode);// 右节点
System.out.println(current); // 根节点
}
}
}
}
