二叉树查找和删除指定结点

二叉树查找指定的节点

前序查找的思路

1.先判断当前节点的no是否等于要查找的
2.如果是相等，则返回当前节点
3.如果不等，则判断当前节点的左子节点是否为空，如果不为空，则递归前序查找
4.如果左递归前序查找，找到节点，则返回，否继续判断，当前的节点的右子节点是否为空，如果不为空，则继续向右递归前序查找。

中序查找思路

1.判断当前节点的左子节点是否为空，如果不为空，则递归中序查找
2.如果找到，则返回，如果没有找到，就和当前节点比较，如果是则返回当前节点，否则继续进行右递归的中序查找
3.如果右递归中序查找，找到就返回，否则返回null

后序查找思路

1.判断当前节点的左子节点是否为空，如果不为空，则递归后序查找
2.如果找到，就返回，如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回
3.就和当前节点进行比较，如果是则返回，否则返回null

要求

1.请编写前序查找，中序查找和后序查找的方法。
2.并分别使用三种查找方式，查找 heroNO = 5 的节点
3.并分析各种查找方式，分别比较了多少次

代码实现：
先创建HeroNode 结点

1. class HeroNode {
2.         private int no;
3.         private String name;
4.         private HeroNode left; //默认null
5.         private HeroNode right; //默认null
6.         public HeroNode(int no, String name) {
7.                 this.no = no;
8.                 this.name = name;
9.         }
10.         public int getNo() {
11.                 return no;
12.         }
13.         public void setNo(int no) {
14.                 this.no = no;
15.         }
16.         public String getName() {
17.                 return name;
18.         }
19.         public void setName(String name) {
20.                 this.name = name;
21.         }
22.         public HeroNode getLeft() {
23.                 return left;
24.         }
25.         public void setLeft(HeroNode left) {
26.                 this.left = left;
27.         }
28.         public HeroNode getRight() {
29.                 return right;
30.         }
31.         public void setRight(HeroNode right) {
32.                 this.right = right;
33.         }
34.         @Override
35.         public String toString() {
36.                 return "HeroNode [no=" + no + ", name=" + name + "]";
37.         }
38.     //前序遍历
39.         public void preOrder() {
40.                 System.out.println(this); //先输出父结点
41.                 //递归向左子树前序遍历
42.                 if(this.left != null) {
43.                         this.left.preOrder();
44.                 }
45.                 //递归向右子树前序遍历
46.                 if(this.right != null) {
47.                         this.right.preOrder();
48.                 }
49.         }
50.         //前序遍历查找
51.         /**
52.          *
53.          * @param no 查找no
54.          * @return 如果找到就返回该Node ,如果没有找到返回 null
55.          */
56.         public HeroNode preOrderSearch(int no) {
57.                 System.out.println("进入前序遍历");
58.                 //比较当前结点是不是
59.                 if(this.no == no) {
60.                         return this;
61.                 }
62.                 //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
63.                 //2.如果左递归前序查找，找到结点，则返回
64.                 HeroNode resNode = null;
65.                 if(this.left != null) {
66.                         resNode = this.left.preOrderSearch(no);
67.                 }
68.                 if(resNode != null) {//说明我们左子树找到
69.                         return resNode;
70.                 }
71.                 //1.左递归前序查找，找到结点，则返回，否继续判断，
72.                 //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
73.                 if(this.right != null) {
74.                         resNode = this.right.preOrderSearch(no);
75.                 }
76.                 return resNode;
77.         }
78.        
79.         //中序遍历查找
80.         public HeroNode infixOrderSearch(int no) {
81.                 //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
82.                 HeroNode resNode = null;
83.                 if(this.left != null) {
84.                         resNode = this.left.infixOrderSearch(no);
85.                 }
86.                 if(resNode != null) {
87.                         return resNode;
88.                 }
89.                 System.out.println("进入中序查找");
90.                 //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
91.                 if(this.no == no) {
92.                         return this;
93.                 }
94.                 //否则继续进行右递归的中序查找
95.                 if(this.right != null) {
96.                         resNode = this.right.infixOrderSearch(no);
97.                 }
98.                 return resNode;
99.                
100.         }
101.        
102.         //后序遍历查找
103.         public HeroNode postOrderSearch(int no) {
104.                
105.                 //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
106.                 HeroNode resNode = null;
107.                 if(this.left != null) {
108.                         resNode = this.left.postOrderSearch(no);
109.                 }
110.                 if(resNode != null) {//说明在左子树找到
111.                         return resNode;
112.                 }
113.                
114.                 //如果左子树没有找到，则向右子树递归进行后序遍历查找
115.                 if(this.right != null) {
116.                         resNode = this.right.postOrderSearch(no);
117.                 }
118.                 if(resNode != null) {
119.                         return resNode;
120.                 }
121.                 System.out.println("进入后序查找");
122.                 //如果左右子树都没有找到，就比较当前结点是不是
123.                 if(this.no == no) {
124.                         return this;
125.                 }
126.                 return resNode;
127.         }
128.        
129. }

复制代码

定义BinaryTree 二叉树

1. class BinaryTree {
2.         private HeroNode root;
4.         public void setRoot(HeroNode root) {
5.                 this.root = root;
6.         }
7.        
8.         //前序遍历查找
9.         public HeroNode preOrderSearch(int no) {
10.                 if(root != null) {
11.                         return root.preOrderSearch(no);
12.                 } else {
13.                         return null;
14.                 }
15.         }
16.         //中序遍历查找
17.         public HeroNode infixOrderSearch(int no) {
18.                 if(root != null) {
19.                         return root.infixOrderSearch(no);
20.                 }else {
21.                         return null;
22.                 }
23.         }
24.         //后序遍历查找
25.         public HeroNode postOrderSearch(int no) {
26.                 if(root != null) {
27.                         return this.root.postOrderSearch(no);
28.                 }else {
29.                         return null;
30.                 }
31.         }
32. }

复制代码

测试：

1. public class BinaryTreeDemo {
3.         public static void main(String[] args) {
4.                 //先需要创建一颗二叉树
5.                 BinaryTree binaryTree = new BinaryTree();
6.                 //创建需要的结点
7.                 HeroNode root = new HeroNode(1, "宋江");
8.                 HeroNode node2 = new HeroNode(2, "吴用");
9.                 HeroNode node3 = new HeroNode(3, "卢俊义");
10.                 HeroNode node4 = new HeroNode(4, "林冲");
11.                 HeroNode node5 = new HeroNode(5, "关胜");
12.                
13.                 //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
14.                 root.setLeft(node2);
15.                 root.setRight(node3);
16.                 node3.setRight(node4);
17.                 node3.setLeft(node5);
18.                 binaryTree.setRoot(root);
19.                
20.                 // 前序遍历
21.                 // 前序遍历的次数 ：4
22.                 System.out.println("前序遍历方式~~~");
23.                 HeroNode resNode = binaryTree.preOrderSearch(5);
24.                 if (resNode != null) {
25.                         System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
26.                 } else {
27.                         System.out.printf("没有找到 no = %d 的英雄", 5);
28.                 }
29.                
30.                 /**
31.                         // 中序遍历查找
32.                         // 中序遍历3次
33.                         System.out.println("中序遍历方式~~~");
34.                         HeroNode resNode = binaryTree.infixOrderSearch(5);
35.                         if (resNode != null) {
36.                                 System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
37.                         } else {
38.                                 System.out.printf("没有找到 no = %d 的英雄", 5);
39.                         }
40.                 */
41.                 /**
42.                         // 后序遍历查找
43.                         // 后序遍历查找的次数 2次
44.                         System.out.println("后序遍历方式~~~");
45.                         HeroNode resNode = binaryTree.postOrderSearch(5);
46.                         if (resNode != null) {
47.                                 System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
48.                         } else {
49.                                 System.out.printf("没有找到 no = %d 的英雄", 5);
50.                         }
51.                 */
52.                
53.         }
55. }

复制代码

运行结果如图：
前序遍历：
​       
中序遍历：

后序遍历：

二叉树删除指定的节点

要求

1.如果删除的节点是叶子节点，则删除该节点
2.如果删除的节点是非叶子节点，则删除该子树.
3.测试，删除掉 5 号叶子节点

思路：
1.考虑如果树是空树root,如果只有一个root节点，则等价将二叉树置空
2.因为我们的二叉树是单向的，所以我们是判断当前节点的子节点是否是需要删除节点，而不能去判断当前这个节点是不是需要删除节点。
3.如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将this.left=null;
并且就返回（结束递归删除）
4.如果当前节点的右子节点不为空，并且右子节点就是要删除节点，就将this.right=null;
并且就返回（结束递归删除）
5.如果3，4步没有删除节点，那么我们就需要向左子树进行递归删除
6.如果第5步也没有删除节点，则应当向右子树进行递归删除。

代码实现：
//HeroNode 类增加方法

1. //递归删除结点
2.         //1.如果删除的节点是叶子节点，则删除该节点
3.         //2.如果删除的节点是非叶子节点，则删除该子树
4.         public void delNode(int no) {
5.                
6.                 //思路
7.                 /*
8.                  *         1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
9.                         2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
10.                         3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
11.                         4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
12.                         5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.
14.                  */
15.                 //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
16.                 if(this.left != null && this.left.no == no) {
17.                         this.left = null;
18.                         return;
19.                 }
20.                 //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
21.                 if(this.right != null && this.right.no == no) {
22.                         this.right = null;
23.                         return;
24.                 }
25.                 //4.我们就需要向左子树进行递归删除
26.                 if(this.left != null) {
27.                         this.left.delNode(no);
28.                 }
29.                 //5.则应当向右子树进行递归删除
30.                 if(this.right != null) {
31.                         this.right.delNode(no);
32.                 }
33.         }

复制代码

//在 BinaryTree 类增加方法

1. //删除结点
2.         public void delNode(int no) {
3.                 if(root != null) {
4.                         //如果只有一个root结点, 这里立即判断root是不是就是要删除结点
5.                         if(root.getNo() == no) {
6.                                 root = null;
7.                         } else {
8.                                 //递归删除
9.                                 root.delNode(no);
10.                         }
11.                 }else{
12.                         System.out.println("空树，不能删除~");
13.                 }
14.         }

复制代码

//在 BinaryTreeDemo 类增加测试代码：

1. //测试一把删除结点
2.                 System.out.println("删除前,前序遍历");
3.                 binaryTree.preOrder(); //  1,2,3,5,4
4.                 binaryTree.delNode(5);
5.                 //binaryTree.delNode(3);
6.                 System.out.println("删除后，前序遍历");
7.                 binaryTree.preOrder(); // 1,2,3,4

复制代码

代码运行如图：

这篇博客是我在B站看韩顺平老师数据结构和算法的课时的笔记，记录一下，防止忘记，也希望能帮助各位朋友。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！