Java树形结构是一种可以存储元素的有层级关系的数据结构，每个元素以节点的形式存在，并且一个根节点会关联多个子节点，子节点再关联更多的子节点，以此类推。
一、树的基本概念
1、树形结构是一种递归式数据结构，它包括一个值，同时还可能包括指向其他树的引用（树是由节点（储存元素）和边（连接节点）组成的集合）
2、树形结构的特性如下: 每个节点有零个或多个子节点; 没有父节点的节点称为根节点; 每一个非根节点有且只有一个父节点; 除了根节点外，每个子节点又可以分为多个不重叠的子树.
class Node {
int data;
Node left, right;
public Node(int item) {
data = item;
left = right = null;
}
}
二、二叉树和二叉搜索树
1、二叉树是每个节点最多只能有两个子节点的树形结构结构，一般子节点称为“左子节点”和“右子节点”。
二叉树形结构的遍历有三种方式：前序遍历、中序遍历和后序遍历。
void printPreorder(Node node) {
if (node == null)
return;
// 先输出当前节点的数据
System.out.print(node.data + " ");
// 递归打印左子节点
printPreorder(node.left);
// 现在递归打印右子节点
printPreorder(node.right);
}
二叉搜索树（BST）是一种特性的二叉树：每个节点的值，都大于其左子树的所有节点的值，并且小于右子树形结构的所有节点的值。
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
class BinaryTree {
Node root;
void insert(int key) { root = insertRec(root, key); }
Node insertRec(Node root, int key) {
if (root == null) {
root = new Node(key);
return root;
}
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
return root;
}
void inorder() { inorderRec(root); }
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
}
三、平衡二叉树形结构与红黑树形结构
1、平衡二叉搜索树是其每一个节点的两个子树的高度差最多为1的二叉搜索树，它通过旋转操作，保障树的平衡，从而优化了树的查询速度。
2、红黑树则是一种自平衡的二叉查找树，它在执行插入和删除操作的时候，通过特定的操作保持树的平衡。
以下是其特性：
（1）每个节点或是红色，或是黑色。
（2）根节点是黑色。
（3）每个叶节点（叶节点默认是空节点（NIL）或null）都是黑色的。
（4）如果一个节点是红的，则它的子节点都是黑的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
class Node {
int data;
Node parent;
Node left;
Node right;
int color;
}
public class RedBlackTree {
private Node root;
private Node TNULL;
// Preorder
private void preOrderHelper(Node node) {
if (node != TNULL) {
preOrderHelper(node.left);
preOrderHelper(node.right);
}
}
// In-order
private void inOrderHelper(Node node) {
if (node != TNULL) {
inOrderHelper(node.left);
inOrderHelper(node.right);
}
}
// Post order
private void postOrderHelper(Node node) {
if (node != TNULL) {
postOrderHelper(node.left);
postOrderHelper(node.right);
}
}
// Balance the tree after deletion of a node
private void fixDelete(Node x) {
Node s;
while (x != root && x.color == 0) {
if (x == x.parent.left) {
s = x.parent.right;
if (s.color == 1) {
// case 3.1
s.color = 0;
x.parent.color = 1;
leftRotate(x.parent);
s = x.parent.right;
}
if (s.left.color == 0 && s.right.color == 0) {
// case 3.2
s.color = 1;
x = x.parent;
} else {
if (s.right.color == 0) {
// case 3.3
s.left.color = 0;
s.color = 1;
rightRotate(s);
s = x.parent.right;
}
// case 3.4
s.color = x.parent.color;
x.parent.color = 0;
s.right.color = 0;
leftRotate(x.parent);
x = root;
}
} else {
// same as "if (x == x.parent.left)" the other way around
}
}
x.color = 0;
}
// Balance the tree after insertion of a node
private void fixInsert(Node k) {
Node u;
while (k.parent.color == 1) {
if (k.parent == k.parent.parent.right) {
u = k.parent.parent.left;
// uncle is RED
if (u.color == 1) {
u.color = 0;
k.parent.color = 0;
k.parent.parent.color = 1;
k = k.parent.parent;
} else {
if (k == k.parent.left) {
k = k.parent;
rightRotate(k);
}
// uncle is BLACK
k.parent.color = 0;
k.parent.parent.color = 1;
leftRotate(k.parent.parent);
}
} else {
// mirror image of above code
// the other way around
}
if (k == root) {
break;
}
}
root.color = 0;
}
// ...
}
