Java树形结构的解释和用法

Java树形结构是一种可以存储元素的有层级关系的数据结构，每个元素以节点的形式存在，并且一个根节点会关联多个子节点，子节点再关联更多的子节点，以此类推。

一、树的基本概念

1、树形结构是一种递归式数据结构，它包括一个值，同时还可能包括指向其他树的引用（树是由节点（储存元素）和边（连接节点）组成的集合）

2、树形结构的特性如下: 每个节点有零个或多个子节点; 没有父节点的节点称为根节点; 每一个非根节点有且只有一个父节点; 除了根节点外，每个子节点又可以分为多个不重叠的子树.

classNode{
intdata;
Nodeleft,right;

publicNode(intitem){
data=item;
left=right=null;
}
}

二、二叉树和二叉搜索树

1、二叉树是每个节点最多只能有两个子节点的树形结构结构，一般子节点称为“左子节点”和“右子节点”。

二叉树形结构的遍历有三种方式：前序遍历、中序遍历和后序遍历。

voidprintPreorder(Nodenode){
if(node==null)
return;

//先输出当前节点的数据
System.out.print(node.data+"");

//递归打印左子节点
printPreorder(node.left);

//现在递归打印右子节点
printPreorder(node.right);
}

二叉搜索树（BST）是一种特性的二叉树：每个节点的值，都大于其左子树的所有节点的值，并且小于右子树形结构的所有节点的值。

classNode{
intkey;
Nodeleft,right;

publicNode(intitem){
key=item;
left=right=null;
}
}

classBinaryTree{
Noderoot;
voidinsert(intkey){root=insertRec(root,key);}

NodeinsertRec(Noderoot,intkey){
if(root==null){
root=newNode(key);
returnroot;
}
if(key<root.key)
root.left=insertRec(root.left,key);
elseif(key>root.key)
root.right=insertRec(root.right,key);
returnroot;
}

voidinorder(){inorderRec(root);}
voidinorderRec(Noderoot){
if(root!=null){
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
}

三、平衡二叉树形结构与红黑树形结构

1、平衡二叉搜索树是其每一个节点的两个子树的高度差最多为1的二叉搜索树，它通过旋转操作，保障树的平衡，从而优化了树的查询速度。

2、红黑树则是一种自平衡的二叉查找树，它在执行插入和删除操作的时候，通过特定的操作保持树的平衡。

以下是其特性：

（1）每个节点或是红色，或是黑色。

（2）根节点是黑色。

（3）每个叶节点（叶节点默认是空节点（NIL）或null）都是黑色的。

（4）如果一个节点是红的，则它的子节点都是黑的。

（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

classNode{
intdata;
Nodeparent;
Nodeleft;
Noderight;
intcolor;
}

publicclassRedBlackTree{

privateNoderoot;
privateNodeTNULL;

//Preorder
privatevoidpreOrderHelper(Nodenode){
if(node!=TNULL){
preOrderHelper(node.left);
preOrderHelper(node.right);
}
}

//In-order
privatevoidinOrderHelper(Nodenode){
if(node!=TNULL){
inOrderHelper(node.left);
inOrderHelper(node.right);
}
}

//Postorder
privatevoidpostOrderHelper(Nodenode){
if(node!=TNULL){
postOrderHelper(node.left);
postOrderHelper(node.right);
}
}

//Balancethetreeafterdeletionofanode
privatevoidfixDelete(Nodex){
Nodes;
while(x!=root&&x.color==0){
if(x==x.parent.left){
s=x.parent.right;
if(s.color==1){
//case3.1
s.color=0;
x.parent.color=1;
leftRotate(x.parent);
s=x.parent.right;
}

if(s.left.color==0&&s.right.color==0){
//case3.2
s.color=1;
x=x.parent;
}else{
if(s.right.color==0){
//case3.3
s.left.color=0;
s.color=1;
rightRotate(s);
s=x.parent.right;
}

//case3.4
s.color=x.parent.color;
x.parent.color=0;
s.right.color=0;
leftRotate(x.parent);
x=root;
}
}else{
//sameas"if(x==x.parent.left)"theotherwayaround
}
}
x.color=0;
}

//Balancethetreeafterinsertionofanode
privatevoidfixInsert(Nodek){
Nodeu;
while(k.parent.color==1){
if(k.parent==k.parent.parent.right){
u=k.parent.parent.left;

//uncleisRED
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);
}
//uncleisBLACK
k.parent.color=0;
k.parent.parent.color=1;
leftRotate(k.parent.parent);
}
}else{
//mirrorimageofabovecode
//theotherwayaround
}
if(k==root){
break;
}
}
root.color=0;
}

//...
}