二叉树的前序、中序、后序查找
查找指定节点
前序查找思路
先判断当前结点的 no 是否等于要查找的
如果是相等，则返回当前结点
如果不等，则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
如果左递归前序查找，找到结点，则返回，否续判断，当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找.
中序查找思路
判断当前结点的左子节点是否为空，如果不为空，则递归查找
如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点，否则继续进行右递归的中序查找
如果右递归中序查找，找到就返回，否则返回 null
后序查找思路
判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
如果找到，就返回，如果没有找到，就判断当前结点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回
就和当前结点进行，比如，如果是则返回，否则返回 null
代码实现
//前序遍历查找/** * * @param no 查找no * @return 如果找到就返回该Node,如果没有找到返回null */public HeroNode preOrderSearch(int no){ //比较当前节点是不是 if(this.no==no){ return this; } //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 //2.如果左递归前序查找,找到节点,则返回 HeroNode resNode = null; if(this.left!=null){ resNode = resNode.left.preOrderSearch(no); } if (resNode!=null){ //说明左子树找到 return resNode; } //1,左递归前序查找，找到结点，则返回，否继续判断， //2,当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找 if(this.right!=null){ resNode = this.right.preOrderSearch(no); } return resNode;}
复制代码
//中序遍历查找public HeroNode infixOrderSearch(int no){ //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 HeroNode resNode = null; if (this.left!=null){ resNode = this.left.infixOrderSearch(no); } if (resNode!=null){ return resNode; } //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点 if(this.no == no){ return this; }
//否则继续进行右递归的中序查找 if (this.right!=null){ resNode = this.right.infixOrderSearch(no); } return resNode;}
复制代码
//后序遍历查找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; } //如果左右子树都没有找到，就比较当前结点是不是 if (this.no == no){ return this; } return resNode;}
复制代码
二叉树节点的删除
如果删除的节点是叶子节点，则删除该节点
如果删除的节点是非叶子节点，则删除该子树
测试，删除掉 5 号叶子节点和 3 号子树.
思路分析
考虑如果树是空树 oot,如果只有一个 root 结点，则等价将二叉树置空
1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点
2.如果当前结点的左子结点不为空，并且左子结点就是要除结点，就将 this.left=null;并且就返回（结束递归删除)
3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将 this.right=null:并且就返回（结束递归删除)
4.如果第 2 和第 3 步没有删除结点，那么我们就需要向左子树进行递归删除
5.如果第 4 步也没有删除结点，则应当向右子树进行递归删除
代码实现
//递归删除节点//1.如果删除的节点是叶子节点,则删除该节点//2.如果删除的节点是非叶子节点,则删除该子树public void delNode(int no){ /** * 1.因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点 * * 2.如果当前结点的左子结点不为空，并且左子结点就是要除结点，就将this.left=null;并且就返回（结束递归删除) * * 3.如果当前结点的右子结点不为空，并且右子结点就是要删除结点，就将this.right=null:并且就返回（结束递归删除) * * 4.如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除 * * 5.如果第4步也没有删除结点，则应当向右子树进行递归删除 */ //2. if (this.left!=null&&this.left.no == no){ this.left = null; return; } //3. if (this.right!=null&&this.right.no==no){ this.right=null; return; } //4.我们就需要向左子树进行递归删除 if (this.left!=null){ this.left.delNode(no); } //5. if (this.right!=null){ this.right.delNode(no); }}
复制代码
评论