数据结构—树（java实现）

一、树的基本概念

1.树的术语

树是由节点和边构成的一种层次性的结构，包括一个根节点，根节点下面连接很多个子节点。树结构的术语如下：
1、根节点：树的第一个节点，没有父节点。
2、子节点：根节点下面的节点为子节点。
3、叶子节点：没有子节点的节点。
4、父节点：子节点的上面的节点为父节点。
5、子树：一个节点以及其所有的子节点、以及子节点的子节点构成子树。
6、森林：森林是指互相不交并树的集合。
7、节点的权：节点的值
8、路径：从根节点到该节点的距离。

2.常见的树结构

1.二叉树：每一个节点最多只有两个子节点的树叫做二叉树。
2.完全二叉树：按照节点的输入顺序进行构造树，使每一层的树节点达到要求的规定值（2^n-1）。
3.有序二叉树：每一个节点最多只有两个子节点的树，且左子节点小于父节点的值，右子节点大于父节点的值。
4.二叉平衡树：每个节点的左子树和右子树的高度差绝对值不超过1。
5.红黑树：是一种自平衡的二叉查找树。

二、节点的定义

节点是树构造的基本单元，树是由节点按照一定顺序构造而出的。

package Tree;public class Node {Node left;Node right;int value;public Node(int value) {this.value = value;}public Node() {}@Overridepublic String toString() {return "Node{" +"left=" + left +", right=" + right +", value=" + value +'}';}
}

节点的定义需要包括空参构造和有参构造，以及节点的值，节点的左子节点和右子节点。

三、有关树结构的操作

1.按照数组构造平衡 二叉搜索树

根据输入的数组，直接构造平衡 二叉搜索树，不需要进行调整，左旋右旋等操作，非常简便有效的操作

    public void makeTree(int[] nums){Arrays.sort(nums);Node node = fenzhi(nums,0,nums.length-1);root = node;}public Node fenzhi(int[] nums,int left,int right){if(left > right){return null;}int mid = (left+right)/2;Node head = new Node(nums[mid]); // 创建当前节点head.left = fenzhi(nums,left,mid-1);head.right = fenzhi(nums,mid+1,right);return head;}

运行代码如下：

package Tree;public class Test {public static void main(String[] args) {int[] nums = {1,4,9,5,2,10,18,3};Tree tree = new Tree();tree.makeTree(nums);tree.cengxu();}
}

运行结果如下：

2.层序遍历树

层序遍历需要用到队列辅助进行，队列具有先进先出的效果，比较适合进行层序遍历的操作。

 public void cengxu(){Node head = root;Queue<Node> queue = new LinkedList<>();queue.offer(head);while (!queue.isEmpty()){Node node = queue.poll();if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}System.out.println(node.value);}}

3.前、中、后序遍历树

(1).前序遍历树

    public void beforeOrder(Node node){if(node == null){return;}System.out.print(node.value+" ");beforeOrder(node.left);beforeOrder(node.right);}

(2).中序遍历树

    public void inOrder(Node node){if(node == null){return;}inOrder(node.left);System.out.print(node.value+" ");inOrder(node.right);}

(3).后序遍历树

    public void LastOrder(Node node){if(node == null){return;}LastOrder(node.left);LastOrder(node.right);System.out.print(node.value+" ");}

(4).各种遍历的情况的效果对比

package Tree;public class Test {public static void main(String[] args) {int[] nums = {1,4,9,5,2,10,18,3};Tree tree = new Tree();tree.makeTree(nums);System.out.println("————————————————————————层序遍历————————————————");tree.cengxu();System.out.println(" ");System.out.println("————————————————————————前序遍历————————————————");tree.beforeOrder(tree.root);System.out.println(" ");System.out.println("————————————————————————中序遍历————————————————");tree.inOrder(tree.root);System.out.println(" ");System.out.println("————————————————————————后序遍历————————————————");tree.LastOrder(tree.root);}
}

运行结果如下：

4.元素添加

添加元素需要按照有序二叉树的形式添加元素，需要判断该值与节点值的大小，直到找到与其符合的位置，并且完成插入操作，代码如下：

public void insert(int num){Node node = new Node(num);Node head = root;if(root == null){root  = node;}while(true){if(num <head.value){if(head.left == null){head.left = node;break;}else{head = head.left;}} else if (num >= head.value) {if(head.right == null){head.right = node;break;}else{head = head.right;}}}}

5.元素删除

树节点的删除需要分成三种情况1.删除叶子节点2.删除只有一个子节点的节点3.删除两侧节点齐全的节点

1.删除叶子节点

1.找到要删除的元素
2.找到要删除元素的父节点
3.判断其父节点是否为空
4.父节点为空的话为：则该节点为根节点 可以将 root = null
5.父节点不为空的话：判断是父节点的左子节点还是父节点的右子节点 后删除

2.删除单一子节点的节点

1.找到要删除的节点
2,找到要删除节点的父节点
3.考虑有没有父节点
4.没有父节点：判断该节点有左子树还是右子树，如果目标节点有左子树的话 root = root.left 如果目标节点有右子树的话 root = root.right
5.有父节点的情况下：1、判断该节点是父节点的左子节点还是右子节点 左子节点的情况下：判断该节点有左子树还是右子树，如果目标节点有左子树的话 parent.left =target.left 如果目标节点有右子树的话 parent.left = target.right。2、判断该节点是父节点的左子节点还是右子节点 右子节点的情况下：判断该节点有左子树还是右子树，如果目标节点有左子树的话 parent.right = target.left 如果目标节点有右子树的话 parent.right = target.right。

3.删除双子节点的节点

1.找目标节点右子树的最小值（或者左子树的最大值）替换掉要删除的值
2.找目标节点右子树的最小值（或者左子树的最大值

4.总结代码

   //查找目标元素public Node search(int num){Node index = root;while(index!=null && index.value!=num){if(num > index.value){index = index.right;}else{index = index.left;}}return index;}//查找目标元素的父节点public Node searchParent(int num){Node node = root;while (node != null) {if (num < node.value) {if (node.left != null && node.left.value == num) {return node;}node = node.left;}else if (num >= node.value) {if (node.right != null && node.right.value == num) {return node;}node = node.right;}}return null;}//查找目标元素的右子树的最小值public int min(Node node){Node index = node;while(index.left != null){index = index.left;}return index.value;}//删除代码public void delete(int num){if(root == null){System.out.println("空树");return;}Node target = search(num);if(target == null){System.out.println("没有这个节点");return;}Node parent = searchParent(num);if(target.left == null && target.right == null){
//            删除叶子节点
//            父节点为空if(parent == null){root = null;return;}
//            父节点存在，且左子树if(parent.left != null && parent.left.value==num){parent.left = null;}else{
//                父节点存在，为右孩子parent.right = null;}}else if(target.left != null && target.right != null){
//            删除两个子树的int min = min(target.right);delete(min);target.value = min;}else{
//            删除一个子树的
//            没有父节点if(parent == null){
//                判断目标节点有左子树if(target.left != null){root = root.left;}else{root = root.right;}return;}
//            有父节点
//            目标节点是父节点的左子节点if(parent.left != null && parent.left.value==num){
//                判断目标节点是有左/右节点if(target.left!=null){parent.left = target.left;}else{parent.left = target.right;}
//                目标节点是父节点的右子节点}else{if(target.left!=null){parent.right = target.left;}else{parent.right=target.right;}}}}