java数据结构----树的实现
目录
一、树结构存在的原因
1、数组存储方式分析
优点：通过下表方式访问元素，速度快。对于有序数组没还可以使用二分查找提高检索速度。
缺点：如果要检索某一个具体值，效率比较低下
2、链式存储方式分析
优点：在一定程度上对数组存储方式进行优化（比如插入一个节点，只需要将插入节点，链接到链表当中可删除的效率也很好）。
缺点：在进行检索时，效率仍然比较低，比如（检索某个数值，需要从头结点开始遍历）
3、树存储方式分析
能提高数据存储，读取的效率，比如利用二叉排序树，既可以保证数据的检索速度。同时也可以保证数据的插入，删除，修改的速度。
二、树的示意图
三、树的种类
1.树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树
2.二叉树的子节点分为左节点和右节点
3.如果二叉树的所有叶子节点都在最后一层并且总结点数 = 2^n-1，(n为层数)，则我们称为满二叉数。
4.如果二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
四、二叉树的代码实现
4.1、节点类
public class TreeNode {
private TreeNode leftTreeNode;
private TreeNode rightTreeNode;
private Integer value;
public Integer getValue() {
return value;
}
public void setValue(Integer value) {
this.value = value;
}
public TreeNode(Integer value){
this.value = value;
}
public TreeNode getLeftTreeNode() {
return leftTreeNode;
}
public void setLeftTreeNode(TreeNode leftTreeNode) {
this.leftTreeNode = leftTreeNode;
}
public TreeNode getRightTreeNode() {
return rightTreeNode;
}
public void setRightTreeNode(TreeNode rightTreeNode) {
this.rightTreeNode = rightTreeNode;
}
@Override
public String toString() {
return "TreeNode{" +
"leftTreeNode=" + leftTreeNode +
", rightTreeNode=" + rightTreeNode +
", value=" + value +
'}';
}
}
4.2、有序二叉树的遍历
4.3、构建有序二叉树
//树管理类
public class BinaryTree {
//构建有序二叉树
TreeNode root;
public void insert(int value) {
//新建节点
TreeNode newNode=new TreeNode(value);
if(root==null) {
root=newNode;
}else {
//定义游标来遍历树
TreeNode currentNode=root;
//定义一个游标指向currentNode的前一个
TreeNode parentNode=null;
while(true) {
parentNode=currentNode;
if(newNode.getValue()>currentNode.getValue()) {
currentNode=currentNode.getRightTreeNode();
if(currentNode==null) {
//数据插入
parentNode.setRightTreeNode(newNode);
return;
}
}else {
currentNode=currentNode.getLeftTreeNode();
if(currentNode==null) {
//数据插入
parentNode.setLeftTreeNode(newNode);
return;
}
}
}
}
}4.4、递归实现二叉树
//递归插入二叉树节点
// 递归出口和递归表达式
// f(node,value) = f(node.left,value) node.getLeftTreeNode == null;
// = f(node.right,value) node.getRightTreeNode == null;
public void insertDiGui(TreeNode node,int value) {
//创建节点
TreeNode newNode=new TreeNode(value);
if(root==null) {
root=newNode;
return;
}
if(node.getValue()>newNode.getValue()) {
if(node.getLeftTreeNode()!=null) {
insertDiGui(node.getLeftTreeNode(), value);
}else {
node.setLeftTreeNode(newNode);
}
}else {
if(node.getRightTreeNode()!=null) {
insertDiGui(node.getRightTreeNode(), value);
}else {
node.setRightTreeNode(newNode);
}
}
}4.5、递归遍历二叉树
先中后序遍历：
//二叉树的遍历-----深度优先遍历------前中后序遍历
//先序遍历
public void beforeOrder(TreeNode treeNode) {
if(treeNode==null) {
return;
}
System.out.println(" "+treeNode.getValue()+" ");
beforeOrder(treeNode.getLeftTreeNode());
beforeOrder(treeNode.getRightTreeNode());
}
//中序遍历
public void midOrder(TreeNode treeNode) {
if(treeNode==null) {
return;
}
afterOrder(treeNode.getLeftTreeNode());
System.out.println(" "+treeNode.getValue()+" ");
afterOrder(treeNode.getRightTreeNode());
}
//后序遍历
public void afterOrder(TreeNode treeNode) {
if(treeNode==null) {
return;
}
afterOrder(treeNode.getLeftTreeNode());
afterOrder(treeNode.getRightTreeNode());
System.out.println(" "+treeNode.getValue()+" ");
}4.6、有序二叉树的删除
4.6.1、叶子结点的删除
4.6.2、删除只有一个子树的节点
4.6.3、删除有两个子树的节点
4.6.4、节点删除代码实现
/**
* 删除节点
* @param node 删的的树
* @param value 删除的值
*/
public void delNode(TreeNode node,int value) {
if(node==null) {
System.out.println("这是一颗空树");
return;
}
//找到要删除的节点
TreeNode targetNode=search(node, value);
if(targetNode==null) {
return;
}
//判断这棵树是不是只有一个节点
if(node.getLeftTreeNode()==null&&node.getRightTreeNode()==null) {
root=null;
return;
}
//找到要删除节点的父节点
TreeNode parent=SearchParent(node, value);
//删除叶子节点
if(targetNode.getLeftTreeNode()==null&&targetNode.getRightTreeNode()==null) {
// 确定targetNode是parentNode的左子树还是右子树
if(parent.getLeftTreeNode()!=null&&parent.getLeftTreeNode().getValue()==value) {
parent.setLeftTreeNode(null);
}else if(parent.getRightTreeNode()!=null && parent.getRightTreeNode().getValue() == value){ //右子节点
parent.setRightTreeNode(null);
}
//删除两个子树的节点
}else if(targetNode.getLeftTreeNode()!= null && targetNode.getRightTreeNode()!=null){
int minValue = delRightTreeMin(targetNode.getRightTreeNode());
targetNode.setValue(minValue);
}else {//删除只有一个子树的节点
//要删除的节点有左孩子
if(targetNode.getLeftTreeNode()!=null){
if(parent.getLeftTreeNode()!=null && parent.getLeftTreeNode().getValue() == value){
//targetNode是parent节点的左子树
parent.setLeftTreeNode(targetNode.getLeftTreeNode());
}else {
//targetNode是parent节点的右子树
parent.setRightTreeNode(targetNode.getLeftTreeNode());
}
}else {//要删除的节点有右孩子
if(parent.getRightTreeNode()!=null && parent.getRightTreeNode().getValue() == value){
//targetNode是parent节点的左子树
parent.setLeftTreeNode(targetNode.getRightTreeNode());
}else {
//targetNode是parent节点的右子树
parent.setRightTreeNode(targetNode.getRightTreeNode());
}
}
}
}
/**
* 查找要删除的节点
* @param node
* @param value
* @return
*/
//找到要删除的节点
public TreeNode search(TreeNode node,int value) {
if(value==node.getValue()) {
return node;
}else if(value<node.getValue()) {
if(node.getLeftTreeNode()==null) {
return null;
}
return search(node.getLeftTreeNode(), value);
}else {
if(node.getRightTreeNode()==null) {
return null;
}
return search(node.getRightTreeNode(), value);
}
}
/**
* 找到要删除节点的父节点
* @param node
* @param value
* @return
*/
public TreeNode SearchParent(TreeNode node,int value) {
if(node.getLeftTreeNode()!=null&&node.getLeftTreeNode().getValue()==value||
(node.getRightTreeNode()!=null && node.getRightTreeNode().getValue() == value)) {
return node;
}else {
if(node.getLeftTreeNode()!=null&&value<node.getValue()) {
return SearchParent(node.getLeftTreeNode(), value);
}else if(node.getRightTreeNode()!=null&&value>node.getValue()) {
return SearchParent(node.getRightTreeNode(), value);
}else {
return null;
}
}
}
/**
* 右子树的最小值
* @param node
* @return
*/
public int delRightTreeMin(TreeNode node) {
//定义指针
TreeNode current=node;
while(current.getLeftTreeNode()!=null) {
current=current.getLeftTreeNode();
}
delNode(root, current.getValue());
return current.getValue();
}