二叉树的删除内含全部代码

要求

1. 如果删除的节点是叶子节点&＃xff0c;则删除该节点
2. 如果删除的节点是非叶子节点&＃xff0c;则删除该子树.
3. 测试&＃xff0c;删除掉 5 号叶子节点 和 3 号子树.
4. 完成删除思路分析
   

代码实现

package com.iflytek.tree;//先创建HeroNode 结点
class HeroNode {private int no;private String name;private HeroNode left;//默认 nullprivate HeroNode right;//默认 nullpublic HeroNode(int no, String name) {this.no &＃61; no;this.name &＃61; name;}public int getNo() {return no;}public void setNo(int no) {this.no &＃61; no;}public String getName() {return name;}public void setName(String name) {this.name &＃61; name;}public HeroNode getLeft() {return left;}public void setLeft(HeroNode left) {this.left &＃61; left;}public HeroNode getRight() {return right;}public void setRight(HeroNode right) {this.right &＃61; right;}&＃64;Overridepublic String toString() {return "HeroNode{" &＃43;"no&＃61;" &＃43; no &＃43;", name&＃61;&＃39;" &＃43; name &＃43; &＃39;\&＃39;&＃39; &＃43;&＃39;}&＃39;;}//编写前序遍历的方法public void preOrder() {System.out.println(this);//先输出父结点//递归向左子树前序遍历if (this.left !&＃61; null) {this.left.preOrder();}//递归向右子树前序遍历if (this.right !&＃61; null) {this.right.preOrder();}}//中序遍历public void infixOrder() {//递归向左子树中序遍历if (this.left !&＃61; null) {this.left.infixOrder();}//输出父结点System.out.println(this);//递归向右子树中序遍历if (this.right !&＃61; null) {this.right.infixOrder();}}//后序遍历public void postOrder() {//递归向左子树中序遍历if (this.left !&＃61; null) {this.left.postOrder();}//递归向右子树中序遍历if (this.right !&＃61; null) {this.right.postOrder();}//输出父结点System.out.println(this);}/*** 前序遍历查找** &＃64;param no 查找 no* &＃64;return 如果找到就返回该Node ,如果没有找到返回 null*/public HeroNode preOrderSearch(int no) {System.out.println("进入前序遍历");//比较当前结点是不是if (this.no &＃61;&＃61; no) {return this;}//1.则判断当前结点的左子节点是否为空&＃xff0c;如果不为空&＃xff0c;则递归前序查找//2.如果左递归前序查找&＃xff0c;找到结点&＃xff0c;则返回HeroNode resNode &＃61; null;if (this.left !&＃61; null) {resNode &＃61; this.left.preOrderSearch(no);}if (resNode !&＃61; null) {//说明我们左子树找到return resNode;}//1.左递归前序查找&＃xff0c;找到结点&＃xff0c;则返回&＃xff0c;否继续判断&＃xff0c;//2.当前的结点的右子节点是否为空&＃xff0c;如果不空&＃xff0c;则继续向右递归前序查找if (this.right !&＃61; null) {resNode &＃61; this.right.preOrderSearch(no);//不需要在判断的&＃xff0c;直接返回}return resNode;}/*** 中序遍历查找** &＃64;param no 查找 no* &＃64;return 如果找到就返回该Node ,如果没有找到返回 null*/public HeroNode infixOrderSearch(int no) {//判断当前结点的左子节点是否为空&＃xff0c;如果不为空&＃xff0c;则递归中序查找HeroNode resNode &＃61; null;if (this.left !&＃61; null) {resNode &＃61; this.left.infixOrderSearch(no);}if (resNode !&＃61; null) {return resNode;}System.out.println("进入中序查找");//如果找到&＃xff0c;则返回&＃xff0c;如果没有找到&＃xff0c;就和当前结点比较&＃xff0c;如果是则返回当前结点if (this.no &＃61;&＃61; no) {return this;}//否则继续进行右递归的中序查找if (this.right !&＃61; null) {resNode &＃61; this.right.infixOrderSearch(no);}return resNode;}/*** 后序遍历查找** &＃64;param no 查找 no* &＃64;return 如果找到就返回该Node ,如果没有找到返回 null*/public HeroNode postOrderSearch(int no) {//判断当前结点的左子节点是否为空&＃xff0c;如果不为空&＃xff0c;则递归后序查找HeroNode resNode &＃61; null;if (this.left !&＃61; null) {resNode &＃61; this.left.postOrderSearch(no);}if (resNode !&＃61; null) {//说明在左子树找到return resNode;}//如果左子树没有找到&＃xff0c;则向右子树递归进行后序遍历查找if (this.right !&＃61; null) {resNode &＃61; this.right.postOrderSearch(no);}if (resNode !&＃61; null) {return resNode;}System.out.println("进入后序查找");//如果左右子树都没有找到&＃xff0c;就比较当前结点是不是if (this.no &＃61;&＃61; no) {return this;}return resNode;}//1.如果删除的节点是叶子节点&＃xff0c;则删除该节点//2.如果删除的节点是非叶子节点&＃xff0c;则删除该子树/*** 分析&＃xff1a;思路* 1. 因为我们的二叉树是单向的&＃xff0c;所以我们是判断当前结点的子结点是否需要删除结点&＃xff0c;* 而不能去判断 当前这个结点是不是需要删除结点.* 2. 如果当前结点的左子结点不为空&＃xff0c;并且左子结点就是要删除结点&＃xff0c;就将 this.left &＃61; null;* 并且就返回(结束递归删除)* 3. 如果当前结点的右子结点不为空&＃xff0c;并且右子结点就是要删除结点&＃xff0c;就将 this.right&＃61; null ;* 并且就返回(结束递归删除)* 4. 如果第 2 和第 3 步没有删除结点&＃xff0c;那么我们就需要向左子树进行递归删除* 5. 如果第 4 步也没有删除结点&＃xff0c;则应当向右子树进行递归删除.*/public void delNode(int no) {if (this.left !&＃61; null && this.left.no &＃61;&＃61; no) {this.left &＃61; null;return;}if (this.right !&＃61; null && this.left.no &＃61;&＃61; no) {this.right &＃61; null;return;}if (this.left !&＃61; null) {this.left.delNode(no);}if (this.right !&＃61; null) {this.right.delNode(no);}}}class BinaryTree {private HeroNode root;public void setRoot(HeroNode root) {this.root &＃61; root;}//前序遍历public void preOrder() {if (this.root !&＃61; null) {this.root.preOrder();} else {System.out.println("二叉树为空&＃xff0c;无法遍历");}}//中序遍历public void infixOrder() {if (this.root !&＃61; null) {this.root.infixOrder();} else {System.out.println("二叉树为空&＃xff0c;无法遍历");}}//后序遍历public void postOrder() {if (this.root !&＃61; null) {this.root.postOrder();} else {System.out.println("二叉树为空&＃xff0c;无法遍历");}}//前序查找public HeroNode preOrderSearch(int no) {if (this.root !&＃61; null) {return this.root.preOrderSearch(no);} else {return null;}}//中序查找public HeroNode infixOrderSearch(int no) {if (this.root !&＃61; null) {return this.root.infixOrderSearch(no);} else {return null;}}//后序查找public HeroNode postOrderSearch(int no) {if (this.root !&＃61; null) {return this.root.postOrderSearch(no);} else {return null;}}//删除结点public void delNode(int no) {if (root !&＃61; null) {//如果只有一个 root 结点, 这里立即判断 root 是不是就是要删除结点if (root.getNo() &＃61;&＃61; no) {root &＃61; null;} else {//递归删除root.delNode(no);}} else {System.out.println("空树&＃xff0c;不能删除");}}}public class BinaryTreeDemo {public static void main(String[] args) {//先需要创建一颗二叉树BinaryTree binaryTree &＃61; new BinaryTree();//创建需要的结点HeroNode root &＃61; new HeroNode(1, "宋江");HeroNode node2 &＃61; new HeroNode(2, "吴用");HeroNode node3 &＃61; new HeroNode(3, "卢俊义");HeroNode node4 &＃61; new HeroNode(4, "林冲");HeroNode node5 &＃61; new HeroNode(5, "关胜");//说明&＃xff0c;我们先手动创建该二叉树&＃xff0c;后面我们学习递归的方式创建二叉树root.setLeft(node2);root.setRight(node3);node3.setRight(node4);node3.setLeft(node5);binaryTree.setRoot(root);/* //测试System.out.println("前序遍历"); // 1,2,3,5,4binaryTree.preOrder();//测试System.out.println("中序遍历");binaryTree.infixOrder(); // 2,1,5,3,4//测试System.out.println("后序遍历");binaryTree.postOrder(); // 2,5,4,3,1*//* HeroNode resNode&＃61;null;//前序遍历查找//前序遍历的次数 &＃xff1a;4System.out.println("前序遍历方式~~~");resNode &＃61; binaryTree.preOrderSearch(5);if (resNode!&＃61;null){System.out.printf("找到了&＃xff0c;信息为 no&＃61;%d name&＃61;%s\n", resNode.getNo(), resNode.getName());}else {System.out.printf("没有找到 no &＃61; %d 的英雄",5);}//中序遍历查找//中序遍历 3 次System.out.println("中序遍历方式~~~");resNode &＃61; binaryTree.infixOrderSearch(5);if (resNode!&＃61;null){System.out.printf("找到了&＃xff0c;信息为 no&＃61;%d name&＃61;%s\n", resNode.getNo(), resNode.getName());}else {System.out.printf("没有找到 no &＃61; %d 的英雄", 5);}//后序遍历查找//后序遍历查找的次数 2 次System.out.println("后序遍历方式~~~");resNode &＃61; binaryTree.postOrderSearch(5);if (resNode!&＃61;null){System.out.printf("找到了&＃xff0c;信息为 no&＃61;%d name&＃61;%s\n", resNode.getNo(), resNode.getName());}else {System.out.printf("没有找到 no &＃61; %d 的英雄", 5);}*/System.out.println("删除前,前序遍历");binaryTree.preOrder(); // 1,2,3,5,4binaryTree.delNode(5);//binaryTree.delNode(3);System.out.println("删除后&＃xff0c;前序遍历");binaryTree.preOrder(); // 1,2,3,4}
}

思考题(课后练习)

1. 如果要删除的节点是非叶子节点&＃xff0c;现在我们不希望将该非叶子节点为根节点的子树删除&＃xff0c;需要指定规则, 假如 规定如下:
2. 如果该非叶子节点A只有一个子节点 B&＃xff0c;则子节点 B替代节点A
3. 如果该非叶子节点A有左子节点 B 和右子节点 C&＃xff0c;则让左子节点 B 替代节点A。
4. 请大家思考&＃xff0c;如何完成该删除功能, (课后练习)
5. 后面在讲解 二叉排序树时&＃xff0c;在给大家讲解具体的删除方法