二叉树的概念、构造、遍历、删除

树各种概念

什么是二叉树（包含满二叉树和完全二叉树）

什么是二叉树（包含满二叉树和完全二叉树）

完全二叉树

从上到下，从左到右的节点排列

有序二叉树

有序二叉树定义

树一般 左边比他小，右边比他大

有序二叉树节点实现

package Tree; public class TreeNode { int value; TreeNode(int value){ this.value = value; } TreeNode leftChild ; TreeNode rightChild; @Override public String toString() { return "TreeNode{" + "value=" + value + ", leftChild=" + leftChild + ", rightChild=" + rightChile + '}'; } }

手动创建有序二叉树

package Tree; public class Test { public static void main(String args[]){ //手动创建链表 TreeNode node1 = new TreeNode(5); TreeNode node2 = new TreeNode(4); TreeNode node3 = new TreeNode(6); node1.leftChild = node2; node1.rightChild= node3; System.out.println(node1.toString()); } }

建立管理类

管理类中写一个

TreeNode root;

用它来表示树的根节点，从而控制整个树

自动创建有序二叉树

想法与需求： 我们想要给一个些value，就能自动创建好树

我们只需要在test类中调用管理BinaryTree类，并且调用insert函数就能自动建立树

在 text 中自动调用

package Tree; public class Test { public static void main(String args[]){ //通过管理类，自动调用链表 BinaryTree binaryTree = new BinaryTree(); binaryTree.insert(5); binaryTree.insert(4); binaryTree.insert(6); System.out.println(binaryTree.root); } }

有序二叉树的插入

有序二叉树的插入方法1

管理类中自动插入树节点

思想：

1.在管理类中写，因为有个root

2.写方法，传入参数 value

3.创建newNode，是你要插入的节点，调用构造器，赋值value

4.判断这个树是不是空的，如果是空，就直接插入

5.否则，定义一个currenNode，用它来找newNode要插在哪里，用它来找树的树叶，先让它等于root

6.再定义一个parentNode 来让它等于currentNode的前一个节点，用它插入新数据

7.循环： 如果newNode比currentNode大，就让currentNode往右走

如果currentNode变成null了说明已经走到树叶了，此处插入就好，退出循环

否则，如果newNode比currentNode小，就让currentNode往左走

如果currentNode变成null了说明已经走到树叶了，此处插入就好，退出循环

注意：插入时要用parentNode.rightChile = newNode; 这种方式插入，如果你直接 currentNode=newNode; 那就没有插入到树种，只是给currentNode 赋了一个值

package Tree; public class BinaryTree { //这是管理类，用它来构建这个树，与链表相似 TreeNode root; //插入节点的方法 public void insert(int value){ //new 一个 新节点，值是传进来的value TreeNode newNode = new TreeNode(value); //先判断root上有没有指向，没有指向就让他指向新插入的节点 if (root == null){ root = newNode; }else{ //定义一个currenNode，用它来找newNode要插在哪里， //用它来找树的树叶，先让它等于root //再定义一个parentNode 来让它等于currentNode的前一个 //用它插入新数据 TreeNode currentNode = root; TreeNode parentNode = null; while (true){ parentNode = currentNode; //如果newNode比currentNode大，就让currentNode往右走 if (newNode.value > currentNode.value){ currentNode = currentNode.rightChild; //如果currentNode变成null了说明已经走到树叶了 //此处插入就好 if (currentNode == null){ parentNode.rightChild= newNode; return; } //左边同理 }else { currentNode = currentNode.leftChild; if (currentNode == null){ parentNode.leftChild = newNode; return; } } } } } }

有序二叉树的插入方法2递归插入

思想：

1. 写递归方法，参数传入要插入的根节点node和value，其中node刚开始是root，后面随着递归node会移动。
2. 创建newNode，是你要插入的节点，调用构造器，赋值value
3. 判断root是否为空，为空就直接插入
4. 如果根节点node的值比newNode小，就看右边，如果右边没有值就直接插入，退出递归。如果右边有值就往右边递归：让node变成node.rightChild
5. 否则，根节点node的值比newNode大，就看左边，如果左边没有值就直接插入，退出递归。如果左边有值就往右边递归：让node变成node.leftChild

//递归插入 //node是代表树的根节点，刚开始是root public void insertdiGui(TreeNode node,int value){ TreeNode newNode = new TreeNode(value); if (root == null){ root = newNode; return; } //如果根节点的值比你插入的值小，就看右边是不是有值 // 如果右边没有值就直接插入，如果有值，就继续递归 //即：让根节点变成根节点右边 if (node.value < value){ if (node.rightChild == null){ node.rightChild = newNode; return; } insertdiGui(node.rightChild,value); }else { if (node.leftChild == null){ node.leftChild = newNode; return; } insertdiGui(node.leftChild,value); } }

有序二叉树的前中后序遍历

方法：

每个子树都严格按照 根左右 ，左根右，左右根

前序遍历

//递归方法前序遍历 根左右 public void beforeOrder(TreeNode node){ if (node != null){ System.out.print(node.value + " "); beforeOrder(node.leftChild); beforeOrder(node.rightChild); } }

中序遍历

//递归方法中序遍历 左根右 public void inOrder(TreeNode node){ if (node != null){ inOrder(node.leftChild); // System.out.print(node.value + " "); inOrder(node.rightChild); } }

举例讲解中序遍历代码

5不空，往左递归：3不空，往左递归：2不空，往左递归：2的左空，什么也不执行

2左完了，就输出2

输出完2，在右递归，右什么也不执行

3左完了，就输出3

输出完了3，就往右递归

4不空，往左递归：4的左空，什么也不执行

4左完了，就输出4

输出完4，在右递归，右什么也不执行

5左完了，就往右递归：

......

后续遍历

//递归方法后序遍历 左右根 public void afterOrder(TreeNode node){ if (node != null){ afterOrder(node.leftChild); afterOrder(node.rightChild); System.out.print(node.value + " "); } }

有序二叉树-删除节点

步骤

1.找到要删除的节点targetNode

2.找到要删除的节点的父节点Parent

3.判断删除节点的类型（叶子、有两个子树、有一个子树）

4.分类进行操作

叶子节点

想法：让它的上家为null，没人用它，它就删除了

1. 判断要删除的节点是父节点的左子树还是右子树
2. 如果是左子树就 Parent.left = null

如果是右子树就 Parent.right = null

删除有两个子树的节点

想法：将要删除的节点与叶子结点交换位置，再删除

1. 找删除节点左子树的最大值 或者 删除节点右子树的最小值
2. 将找到的值和要删除的值替换
3. 删除

例如：要删节点3, 将 3和2换 或者 3和4换

删除只有一个子树的节点

想法：让要删除的节点的父节点 指向 要删除的节点的子节点，它没有了引用自然就删除了

1. 确定 targetNode 是父节点的左子树还是右子树
2. 确定 targetNode 的子节点是它的的左子树还是右子树

4.代码实现

4.1.找到要删除的节点targetNode

步骤：

1. 用了递归的方法来找
2. 方法有返回值，返回一个节点类型

node：用来递归时的左右移动，调用的时候传根节点，从根节点开始查找

value：用来找要删除的节点

1. 如果 传来的value = node.value ，就是找到了，直接return退出循环
2. 否则：开始递归，传经来的值小就看左边是否有值，有就往左走，没有就退出

传经来的值大就看右边是否有值，有就往右走，没有就退出

public TreeNode search(TreeNode node,int value){ if (root == null){ return null; } if (value == node.value){ return node; }else if (value < node.value){ if (node.leftChild == null){ return null; } return search(node.leftChild,value); }else { if (node.rightChild == null){ return null; } return search(node.rightChild,value); } }

4.2找要删除的节点的父节点Parent

此处 与上面找节点有区别的，注意看

想法：

1. 用了递归的方法来找
2. 方法有返回值，返回一个节点类型
3. node：用来递归时的左右移动，调用的时候传根节点，从根节点开始查找

value：用来找要删除的节点

1. 如果 当前节点有左子树并且左子树的value就是你要的value 或者 有右子树并且右子树的value就是你要的value ， 那就是找到了，return就行了
2. 否则：就不是你要找的，所以就往左右走，
   1. 找的值小，并且左边有值，就往左走
   2. 找的值大，并且右边有值，就往右走
   3. 或者没有父节点，直接return

public TreeNode searchParent(TreeNode node,int value){ if (node == null){ return null; } if ((node.leftChild !=null && node.leftChild.value == value) || (node.rightChild!=null && node.rightChild.value == value)){ return node; }else { if (node.leftChild!=null && node.leftChild.value>value){ return searchParent(node.leftChild,value); }else if(node.rightChild!=null && node.rightChild.value

4.3 判断删除的节点是什么类型的

public int SearchRightMin(TreeNode node){ //定义一个指针 TreeNode tempNode = node; while (tempNode.leftChild !=null){ tempNode = tempNode.leftChild; } delete(root,tempNode.value); // 删除的左子树当中的最小值 return tempNode.value; } public void delete(TreeNode node,int value){ if (node == null){ return; } // 1.找到删除的节点 TreeNode targetNode = Search(node,value); // 2.如果没有删除的节点 if (targetNode == null){ System.out.println("没有删除的节点"); return; } //如果这颗树只有一个节点 if (node.leftChild == null && node.rightChild == null){ root = null; return; } //3.找到targetNode的父节点 TreeNode parentNode = SearchParent(node,value); //删除的节点是叶子节点 if (targetNode.rightChild == null && targetNode.leftChild == null){ if (parentNode.leftChild !=null && parentNode.leftChild.value == targetNode.value){ parentNode.leftChild = null; }else if (parentNode.rightChild !=null && parentNode.rightChild.value == targetNode.value){ parentNode.rightChild = null; } }else if(targetNode.rightChild!=null && targetNode.leftChild !=null){ //删除的是有两个子树的节点 //找到删除节点右子树当中最小的 int minValue = SearchRightMin(targetNode.rightChild); targetNode.value = minValue; }else { //删除只有一个子树的节点 //如果删除的节点有左子树 if (targetNode.leftChild !=null){ if (parentNode.leftChild.value == targetNode.value){ //删除的节点是父节的左子树 parentNode.leftChild = targetNode.leftChild; }else {//删除的节点是父节的右子树 parentNode.rightChild = targetNode.leftChild; } }else { if (parentNode.leftChild.value == targetNode.value){ parentNode.leftChild = targetNode.rightChild; }else { parentNode.rightChild = targetNode.rightChild; } } } }