11_1 韩顺平数据结构与算法树结构基础部分_二叉树( 二 ) _递归

文章插图
后序查找
先判断当前节点的左子节点是否为空，不为空则递归后序遍历如果找到，就返回，如果没有找到，就判断当前节点的右子节点是否为空，如果不为空，则右递归进行后序查找，没会找到就返回最后和当前接待你进行比较，如果是就返回，不是就返回null
代码实现（检索部分）

Main//前序遍历查找System.out.println("前序遍历方式~~~~");HeroNode resNode_pre = binaryTree.preOrderSearch(5);if (resNode_pre != null) {System.out.printf("找到了，信息为no=%d name=%s\n", resNode_pre.getNo(), resNode_pre.getName());} else {System.out.printf("没有找到no = %d的英雄\n", 5);}//中序遍历查找——3次System.out.println("中序遍历方式！！！！");HeroNode resNode_infix = binaryTree.infixOrderSearch(5);if (resNode_infix != null) {System.out.printf("找到了，信息为no=%d name=%s\n", resNode_infix.getNo(), resNode_infix.getName());} else {System.out.printf("没有找到no = %d的英雄\n", 5);}//后序遍历查找——2次System.out.println("后序遍历方式····");HeroNode resNode_Post = binaryTree.postOrderSearch(5);if (resNode_Post != null) {System.out.printf("找到了，信息为no=%d name=%s\n", resNode_Post.getNo(), resNode_Post.getName());} else {System.out.printf("没有找到no = %d的英雄\n", 5);}BinaryTree>preOrderSearch//前序查找public HeroNode preOrderSearch(int no) {if (root != null) {return root.preOrderSearch(no);} else {return null;}}BinaryTree>infixOrderSearch//中序查找public HeroNode infixOrderSearch(int no) {if (root != null) {return root.infixOrderSearch(no);} else {return null;}}BinaryTree>postOrderSearch//后序查找public HeroNode postOrderSearch(int no) {if (root != null) {return root.postOrderSearch(no);} else {return null;}}HeroNode>preOrderSearch// 1. 前序遍历查找public HeroNode preOrderSearch(int no) {System.out.println("进入前序遍历查找~~~");//自己if (this.no == no) {return this;}//向左HeroNode resNode = null;if (this.left != null) {resNode = this.left.preOrderSearch(no);}if (resNode != null) {return resNode;}//向右if (this.right != null) {resNode = this.right.preOrderSearch(no);}return resNode;}HeroNode>infixOrderSearch// 2. 中序遍历查找public HeroNode infixOrderSearch(int no) {//向左HeroNode resNode = null;if (this.left != null) {resNode = this.left.infixOrderSearch(no);}if (resNode != null) {return resNode;}//自己System.out.println("进入中序查找");if (this.no == no) {return this;}//向右if (this.right != null) {resNode = this.right.infixOrderSearch(no);}return resNode;}HeroNode>postOrderSearch// 3. 后序遍历查找public HeroNode postOrderSearch(int no) {HeroNode resNode = null;//向左if (this.left != null) {resNode = this.left.postOrderSearch(no);}if (resNode != null) {return resNode;}//向右if (this.right != null) {resNode = this.right.postOrderSearch(no);}if (resNode != null) {return resNode;}//自己System.out.println("后序遍历");if (this.no == no) {return this;}return resNode;}

4. 二叉树的删除
要求：
如果删除的节点是叶子节点，则删除该节点如果删除的节点是非叶子节点，则删除改子树（后序再说树叶上提的问题）测试，删除掉5号叶子节点和3号子树
思路：
如果只有一个root节点，就等价将二叉树置空因为二叉树是单向的，所以我们是判断当前节点的子节点是否需要删除；而不能判断当前节点是否需要删除如果当前节点的左子节点不为空，并且左子节点就是要删除的节点，就将this.left = null；并且就返回（结束递归删除）如果当前节点的右子节点不为空，并且右子节点就是要删除的节点，就将this.right = null；并且就返回（结束递归删除）如果第2步和第3步都没有删除节点，那么我们就需要向左子树进行递归删除；如果第4步也没有删除节点，那么我们就需要向右子树进行递归删除；

11_1 韩顺平 数据结构与算法 树结构基础部分_二叉树( 二 )

11_1 韩顺平数据结构与算法树结构基础部分_二叉树( 二 )