文章目录

• 树的概述
• 树的分类
• 二叉树的遍历
• 有序二叉树代码
• • 通过链表方式构建有序二叉树
  • 通过递归方式实现有序二叉树
  • 递归遍历有序二叉树
  • • 中序遍历：
    • 先序遍历：
    • 后序遍历：
• 删除节点
• • 1、删除叶子节点
  • • 删除叶子节点总结图示
  • 2、删除只有一个子树的节点
  • • 删除只有一个子树的节点总结图示
  • 3、删除有两个子树的节点
  • • 删除有两个子树的节点总结图示

树的概述

树——>链式存储结构
注：
数组：查询简单，插入删除复杂
链表：增删改简单，查询复杂
树：即保证查找速度，又保证增删改速度根节点比要查找的数大的话，相当于根节点右边的树可以不需要查询，类似于二分查找

树的分类

二叉树的遍历

例：

有序二叉树代码

有序二叉树特点：左子节点的值小于父节点，右子节点的值大于父节点


（1）首先5做根节点，7和5比较，7比5大则作为5的右子节点；
（2）4和5比较，4比5小则作为5的左子节点；
（3）2和5比较，2比5小，则向左走，5右左子节点4，2和4比较，2比4小且4没有左子节点，则2作为4的左子节点；
（4）向后重复上述步骤

通过链表方式构建有序二叉树

—1—>创建类，创建管理类，创建新节点newNode，创建指向根节点的变量root
—2—>如果root为空，将newNode放再root上面
—3—>当root不为空时，定义游标p指向root，准备向后遍历二叉树
—4—>newNode和游标p指向的根节点进行值得比较，newNode小则向左走，newNode大则向右走
—5—>判断现在p指向是否为空，p不为空则表示有左(右)子节点，继续让newNode和p指向的节点判断大小；p为空则插入数据
—6—>p当前指向为空，该如何解决插入数据得问题？=>定义另一个游标pre指向p游标得前一个节点
—7—>在每次循环时让pre指向p当前指向的节点，后面p向后走时，pre指向不动；因为p向下走一步且指向不为空时，会进行while循环，pre再次指向p，而此时p已经指向下一个了，所以pre始终指向p的前一个。
—8—>有了pre指向p的前一个节点，因此当p指向空时，给pre的左（右）节点赋值，就完成了节点的插入操作

import java.util.LinkedList;public class BinaryTree{TreeNode root;/** 【1】构建有序二叉树* */public void insert(int value) {//传值//新建节点TreeNode newNode=new TreeNode(value);//判断树是否为空//为空if(root == null) {
root=newNode;}else {//不为空//定义游标，游标1和pre游标TreeNode currentNode=root;TreeNode parentNode = null;
//循环操作比较
while(true) {parentNode=currentNode;//parentNode指向游标1指向的节点//判断新节点的值和当前节点的值大小if(newNode.getValue()//新节点值大时
currentNode=currentNode.getLeftTreeNode();//游标向if(currentNode==null) {
parentNode.setLeftTreeNode(newNode);return;}}else {
currentNode=currentNode.getRightTreeNode();
if(currentNode == null) {parentNode.setRightTreeNode(newNode);return;
}}
}//while}//else}//insert
}

通过递归方式实现有序二叉树

import java.util.LinkedList;public class BinaryTree{TreeNode root;
/** 【2】递归实现树* 
*/public void DiguiInsert(TreeNode node,int value) {
TreeNode newNode = new TreeNode(value);
if(root==null) {root=newNode;return;
}
//当前节点和新节点比较
if(node.getValue()>newNode.getValue()) {//左
//判断当前节点左子树是否为空if(node.getLeftTreeNode() != null) {//当前节点左子树不为空继续调用方法，进行比较
DiguiInsert(node.getLeftTreeNode(), value);}else {//当前节点左子树为空就添加node.setLeftTreeNode(newNode);}
}else {//右
//判断当前节点右子树是否为空if(node.getRightTreeNode() != null) {//当前节点右子树不为空继续调用方法，进行比较
DiguiInsert(node.getRightTreeNode(), value);}else {
//当前节点右子树为空就添加
node.setRightTreeNode(newNode);}}}
}

递归遍历有序二叉树

中序遍历：

先向左进行遍历，直到节点没有子树的时候输出，方法出栈，这样就回到上一个节点；
节点再输出后看有没有右子树，有就输出，没有就再返回上一个节点

递归方程式：向左走时：midOrder（node）= midOrder（node.left）

public void midOrder(TreeNode treeNode) {if(treeNode==null) {
return;}midOrder(treeNode.getLeftTreeNode());System.out.println(treeNode.getValue());midOrder(treeNode.getRightTreeNode());
}

先序遍历：

先输出节点，再向左进行遍历，直到节点没有子树的时候输出，方法出栈，这样就回到上一个节点，输出节点，节点再输出后看有没有右子树，有就输出，没有就再返回上一个节点。

public void beforeOrder(TreeNode treeNode) {if(treeNode==null) {return;}System.out.println(treeNode.getValue());beforeOrder(treeNode.getLeftTreeNode());beforeOrder(treeNode.getRightTreeNode());
}

后序遍历：

先向左进行遍历，直到节点没有子树的时候输出，方法出栈，再向右进行遍历，直到节点没有子树的时候输出，方法出栈，这样就回到上一个节点，输出节点。

public void afterOrder(TreeNode treeNode) {if(treeNode==null) {return;}afterOrder(treeNode.getLeftTreeNode());afterOrder(treeNode.getRightTreeNode());System.out.println(treeNode.getValue());}

删除节点

1、删除叶子节点

（1）找到要删除的节点targetNode
（2）找到要删除的节点的父节点parentNode
（3）确定targetNode是parentNode的左子树还是右子树
（4）根据第3点进行删除
targetNode是左子节点：parentNode.setleftTreeNode(null)
targetNode是右子节点：parentNode.setrightTreeNode(null)

删除叶子节点总结图示

2、删除只有一个子树的节点

（1）找到要删除的节点targetNode
（2）找到要删除的节点的父节点parentNode
（3）确定targetNode是parentNode的左子树还是右子树
（4）确定targetNode有左子树还是右子树
（5）如果targetNode有左子树
（5.1）如果targetNode是parentNode的左子树：parentNode.left=targetNode.left
（5.2）如果targetNode是parentNode的右子树：parentNode.right=targetNode.left
（6）如果targetNode有右子树
（6.1）如果targetNode是parentNode的左子树：parentNode.left=targetNode.right
（6.2）如果targetNode是parentNode的右子树：parentNode.right=targetNode.right

删除只有一个子树的节点总结图示

3、删除有两个子树的节点

（1）找到要删除的节点targetNode
（2）找到要删除的节点的父节点parentNode
（3）找到targetNode右子树的最小值（左子树的最大值）temp
（4）用temp替换要删除的节点值
（5）删除右子树的最小值（左子树的最大值）

删除有两个子树的节点总结图示