树
树
树是一种重要的数据结构，通过链表建立一棵树：
//树节点的定义
public class TreeNode<T> {
public T s;
private TreeNode<T> parent;
public List<TreeNode<T>> nodeList;
public TreeNode(T str){
s = str;
parent = null;
nodeList = new ArrayList<TreeNode<T>>();
}
public TreeNode<T> getParent(){
return parent;
}
}
用链表的结构构建树，就是使树的每一条分支都建立一个链表来存储它的子节点。所以要在节点的定义中加上List<TreeNode<T>> nodeList的定义
//树的定义
public class Tree<T> {
public TreeNode<T> root;
//添加树节点
public void addNode(TreeNode<T> node,T newNode){
if(node==null){
if(root==null){
root = new TreeNode<T>(newNode);
}
}else{
TreeNode<T> tn = new TreeNode<T>(newNode);
node.nodeList.add(tn);
}
}
//查找树节点
public TreeNode<T> search(TreeNode<T> node,T newNode){
TreeNode<T> temp = null;
if(node.s.equals(newNode)){
return node;
}
for(int i=0;i<node.nodeList.size();i++){
temp = search(node.nodeList.get(i),newNode);
if(temp!=null){
break;
}
}
return temp;
}
public TreeNode<T> getNode(T newNode){
return search(root, newNode);
}
//输出树节点
public void showNode(TreeNode<T> node){
if(null != node){
System.out.println(node.s.toString());
for(int i = 0; i < node.nodeList.size(); i++){
System.out.println(i);
showNode(node.nodeList.get(i));
}
}
}
}
在search方法中，用了for循环加递归的方法来查找节点。node.nodeList.get(i)获得的是该父节点子树中的节点。通过for循环遍历这条分支。
输出节点也类似，在非二叉树等的普通树结构里，想要遍历整个树结构，for循环加递归这一组合是很好的方式。
最后可以加上主函数进行测试：
public class app {
public static void main(String[] args) {
Tree<String> tree = new Tree<String>();
tree.addNode(null, "节点1");
tree.addNode(tree.getNode("节点1"), "节点2");
tree.addNode(tree.getNode("节点1"), "节点3");
tree.addNode(tree.getNode("节点2"), "节点4");
tree.addNode(tree.getNode("节点2"), "节点5");
tree.addNode(tree.getNode("节点3"), "节点6");
tree.addNode(tree.getNode("节点3"), "节点7");
tree.showNode(tree.root);
}
}
二叉树
二叉树是树的一种特殊形式，每个节点至多有两个子树。二叉树有如下一些性质（二叉树的深度和高度的定义不同教材也不完全相同，有从0开始也有从1开始，这里根节点的深度和叶子结点的高度都为1开始算）：
- 在非空的二叉树中，第i层至多有2i-1个节点
- 深度为h的二叉树最多有2h-1个节点
- n0=n2+1，其中n0为叶子结点的个数，n2为度为2的节点个数
- n个节点的完全二叉树的深度：log2(n+1)
- 对含有n个节点的完全二叉树按照从上到下，从左至右的方式编号，其中第i个节点有以下性质：
- 若i>1，其父节点为i/2
- 若2i<n，其左孩子为2i，否则该节点无左子树
- 若2i+1<n，其右孩子为2i+1，否则该节点无右字树
完全二叉树和满二叉树，完全二叉树是除最下面一层外所有层节点都为满的，最下面一层所有节点都集中在左边。满二叉树是这颗二叉树节点达到最大值。
通过链表的形式建立一颗二叉树，并对二叉树进行遍历等操作：
public class Node {
private int data;
private Node leftChild;
private Node rightChild;
public Node(int data,Node left,Node right){
this.leftChild = left;
this.rightChild = right;
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
}
二叉树的遍历有递归和非递归两种方法，递归的方法很简单。
//前序遍历
public static void preOrderRecusion(Node node){
if(node!=null){
show(node);//打印node节点
preOrderRecusion(node.getLeftChild());
preOrderRecusion(node.getRightChild());
}
}
//中序遍历
public static void inOrderRecusion(Node node){
if(node!=null){
inOrderRecusion(node.getLeftChild());
show(node);
inOrderRecusion(node.getRightChild());
}
}
//后序遍历
public static void postOrderRecusion(Node node){
if(node!=null){
postOrderRecusion(node.getLeftChild());
postOrderRecusion(node.getRightChild());
show(node);
}
}
非递归遍历的前序和中序类似，只是输出换了个位置，后序稍有不同：
//非递归前序遍历
public static void preOrder(Node p){
//利用栈后进先出的原理来实现
Stack<Node> stack = new Stack<Node>();
Node node = p;
while(node!=null||stack.size()>0){
//先输出左子树并将左子树入栈
while(node!=null){
show(node);
stack.push(node);
node = node.getLeftChild();
}
//从栈中取出左子树的点，然后去找他们的右子树进行循环
if(stack.size()>0){
node = stack.pop();
node = node.getRightChild();
}
}
}
//非递归中序遍历
public static void inOrder(Node p){
Stack<Node> stack = new Stack<Node>();
Node node = p;
while(node!=null||stack.size()>0){
//循环将左子树放入栈中
while(node!=null){
stack.push(node);
node = node.getLeftChild();
}
//先取出最左节点然后输出，然后访问右子树
if(stack.size()>0){
node = stack.pop();
show(node);
node = node.getRightChild();
}
}
}
//非递归后序遍历
public static void postOrder(Node p){
Stack<Node> stack = new Stack<Node>();
//建立一个中间栈来按后续遍历顺序存储树节点
Stack<Node> temp = new Stack<Node>();
Node node = p;
while(node!=null||stack.size()>0){
//把当前节点和右子树存到两个栈中
while(node!=null){
temp.push(node);
stack.push(node);
node = node.getRightChild();
}
//出栈取左子树，再进入上面循环，这样stack栈不断pop()和push()，而temp一直在push()
if(stack.size()>0){
node = stack.pop();
node = node.getLeftChild();
}
}
//最后循环输出已经按照后序的顺序存储的temp栈
while(temp.size()>0){
node = temp.pop();
show(node);
}
}
关于二叉树的其他一些操作：
//返回叶子结点数量
public static int leafNum(Node node){
if(node!=null){
if(node.getLeftChild()==null&&node.getRightChild()==null){
return 1;
}
return leafNum(node.getLeftChild())+leafNum(node.getRightChild());
}
return 0;
}
//求二叉树深度
public static int deep(Node node){
int h1,h2;
if(node==null){
return 0;
}
else{
h1 = deep(node.getLeftChild());
h2 = deep(node.getRightChild());
return h1>h2?h1+1:h2+1;
}
}
//层次遍历二叉树
public static void levelOrder(Node node){
if(node==null){
return;
}
Queue<Node> queue = new LinkedList<Node>();
queue.add(node);
while(!queue.isEmpty()){
//从队列中取出并删除第一个节点
Node temp = queue.poll();
show(temp);
if(temp.getLeftChild()!=null){
queue.add(temp.getLeftChild());
}
if(temp.getRightChild()!=null){
queue.add(temp.getRightChild());
}
}
}
二叉排序树
二叉排序树又叫二叉搜索树或二叉查找树。空树可以是二叉排序树，或者具有以下性质的二叉树称为二叉排序树：
1.若左子树不空，则左子树上所有节点的值小于其根节点
- 若右子树不空，则右子树上所有节点的值大于其根节点
- 左、右子树也分别为二叉排序树
二叉排序树和二分查找类似，插入、查找的时间复杂度均为log2n，但当二叉排序树成为线性的情况下复杂度会达到n。
若当前的二叉排序树为空，则将插入的节点作为根节点。否则若插入的节点值小于根节点值，插入到左子树中。反之，插入到右子树中。
public static void insert(Node node){
if(root==null){
root = node;
return;
}
Node current = root;
while(true){
//节点值小于当前根节点
if(node.getData()<current.getData()){
//若其左子树为空，则添加节点
if(current.getLeftChild()==null){
current.setLeftChild(node);
return;
}
//否则当前结点变成其左孩子，然后继续循环
current = current.getLeftChild();
}else if(node.getData()>current.getData()){
if(current.getRightChild()==null){
current.setRightChild(node);
return;
}
current = current.getRightChild();
}else{
return;
}
}
}
查找节点一样根据当前结点与根节点的大小，利用递归实现：
//查找节点
public static Node find(Node node,int data){
if(node==null){
return null;
}else if(node.getData()==data){
return node;
}else if(node.getData()>data){
return find(node.getLeftChild(),data);
}else{
return find(node.getRightChild(),data);
}
}
二叉排序树的删除需要分为以下三种情况：
- 若删除的节点为叶子结点，则直接删除，再修改其父指针为空。
- 若删除的节点度为1，让该节点的父节点指向该节点的孩子节点，然后删除该节点。
- 若删除的节点度为2，则需要找到该节点中序遍历的前驱或后继节点，也就是找到该节点左子树中的最大值或右子树中的最小值来代替该节点。
//删除节点
public static void delete(Node node){
if(node==null){
return;
}
Node current = root;
Node parent = root;
boolean isLeftNode = true;
//while循环是为了得到该节点的父节点，和该节点是左还是右节点
while (current != node) {
parent = current;
if (node.getData() < current.getData()) {
isLeftNode = true;
current = current.getLeftChild();
} else {
isLeftNode = false;
current = current.getRightChild();
}
}
//节点为叶子节点
if (current.getLeftChild() == null && current.getRightChild() == null) {
if (current == root) { // 根节点就删除整棵树
root = null;
} else if (isLeftNode) { // 如果是左节点，做节点指向空
parent.setLeftChild(null);
} else { // 如果是右节点，右节点指向空
parent.setRightChild(null);
}
}
//节点只有左节点
else if (current.getLeftChild() == null) {
if (current == root) {
root = current.getRightChild();
} else if (isLeftNode) {
parent.setLeftChild(current.getRightChild());
} else {
parent.setRightChild(current.getRightChild());
}
}
//节点只有右节点
else if (current.getRightChild() == null) {
if (current == root) {
root = current.getLeftChild();
} else if (isLeftNode) {
parent.setLeftChild(current.getLeftChild());
} else {
parent.setLeftChild(current.getLeftChild());
}
}
//有两个孩子节点
else {
Node successor = findSuccessor(current);
if(current == root){//如果删除的是根节点，就让新的代替节点成为根节点
root = successor;
}else if(isLeftNode){//如果删除节点是左孩子就让其父节点的做指针指新的代替节点
parent.setLeftChild(successor);
}else{
parent.setRightChild(successor);
}
//把删除节点的左子树复给新的代替节点的左孩子
successor.setLeftChild(current.getLeftChild());
}
}
//找到合适的节点来代替删除节点，这里找的是后继节点，即右子树中的最小节点
public static Node findSuccessor(Node delNode){
Node parent = delNode;
Node successor = delNode;
//current为删除节点右子树的第一个节点
Node current = delNode.getRightChild();
//右子树最小节点，就是右子树的最左的节点，所以这里循环获取最左节点
while(current != null){
parent = successor;//parent为最左节点的父节点
successor = current;//successor为最左节点
current = current.getLeftChild();
}
//successor == delNode.getRightChild()也就是删除节点的右子树没有左节点，那就用其右子树的根节点做替换节点，所以也就不用if()里面的相关操作
if(successor != delNode.getRightChild()){//有左节点的情况下
parent.setLeftChild(successor.getRightChild());//代替节点的右子树复给他父节点的左子树，也就是用他的右子树代替他本来的位置
successor.setRightChild(delNode.getRightChild());//删除节点的右子树复给代替节点的右子树
}
return successor;
}
平衡二叉树
平衡二叉树就是AVL树，是二叉排序树的进化。如果二叉排序树按照最坏的情况插入就会变成一个链表，所以为了防止这种情况，就要使用平衡二叉树。
AVL树的旋转分为四种情况：
LL型：AVL树的左孩子的左子树插入结点导致失衡，此时需要把树向右旋转一次
RR型：AVL树的右孩子的右子树插入结点导致失衡，此时需要把树向左旋转一次
LR型：AVL树的左孩子的右子树插入节点导致失衡，此时需要先左子树向左旋转，再将树向右旋转
RL型：AVL树的右孩子的左子树插入节点导致失衡，此时需要先右子树向右旋转，再将树向左旋转
图示参考：AVL树调整平衡
红黑树
红黑树是一种平衡的二叉树排序树，相比于AVL树，红黑树放宽了对于平衡的要求。但它与AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
红黑树性质：
- 所有节点都是红色或黑色
- 根节点是黑色
- 所有叶子结点是黑色(叶子节点指的是NIL节点，也就是空节点)
- 每个红色节点的两个子节点都是黑色，即不能存在两个红色节点互为父子
- 从任意节点到其叶子结点的所有路径中包含的黑色节点数相同
红黑树的插入操作，我们把插入的节点置为红色，然后在根据情况进行调整。
- 插入节点为根节点，把红色变成黑色即可。
- 插入节点的父节点是黑色，无需做任何改变。
- 插入节点的父节点是红色且其父节点的兄弟节点也是红色，其祖父节点必然是黑色。此时，将父节点及其兄弟节点置为黑色，然后把祖父节点置为红色。但此时可能会发生错误，因为祖父节点的父节点也有可能是红色，所以我们要把祖父节点当成插入的节点重新进行这一切。1）如果祖父节点就是根节点，那么把祖父节点置为黑色。2）如果祖父节点的父节点为黑色，则可不变。3）如果祖父节点的父节点为红色，则递归3这种情况。
- 插入节点的父节点是红色，其叔父节点是黑色或空，且插入的节点为左孩子。这种情况下，我们先调换父节点和祖父节点颜色，然后把祖父节点进行一次右旋转。
- 插入节点的父节点是红色，其叔父节点是黑色或空，且插入的节点为右孩子。这种情况下，我们对父节点进行一次左旋转，然后情况就变成了4。接着按照4的方法进行插入。
红黑树的删除，如果需要删除的节点有两个儿子，那么问题可以被转化成删除一个只有一个儿子的节点的问题。因为对于二叉查找树，在删除带有两个非叶子儿子的节点的时候，我们找到要么在它的左子树中的最大元素、要么在它的右子树中的最小元素，并把它的值转移到要删除的节点中。我们接着删除我们从中复制出值的那个节点，它必定有少于两个非叶子的儿子。因为只是复制了一个值，不违反任何性质，这就把问题简化为如何删除最多有一个儿子的节点的问题。
- 删除的节点是红色且没有非空左右孩子，直接删除即可。
- 删除的节点是红色单支节点且有孩子，这种情况是不可能出现的，如果孩子是红色违反了性质4，如果是黑色违反了性质5。
- 删除的节点是黑色单支节点。其孩子节点代替其位置，但这样影响了平衡性，需要进行调整。
- 若孩子节点为红色，直接将孩子节点置为黑色，即可达到平衡。
- 若孩子节点为黑色，则也分为一下几种情况：具体参考
B树
Todo
B+树
Todo
B*树
Todo
Trie树
Todo
