本文共 2987 字，大约阅读时间需要 9 分钟。

二叉树——查找指定节点

前序查找

思路分析

1. 先判断当前节点是否为要查找的节点，相等就返回当前节点，作为递归中值的条件
2. 如果不相等，判断左子节点是否为空，不为空，递归前序查找
3. 如果左递归前序查找，找到该节点，那就返回该节点
4. 没找到，那就判定右子节点是否为空，不为空就进行右子节点的递归前序查找

代码实现

我的代码：

public HeroNode preOrderSearch(int no){
           HeroNode temp = this;        //同链表，根节点和头节点是不动的        //前序查找，现判断当前元素        if (temp.getHeroNo() == no){
               return temp;        }        //如果不相等，再嘀咕比较左子节点是否相等        if (temp.left != null){
               return temp.left.preOrderSearch(no);        }        if (temp.right != null){
               return temp.right.preOrderSearch(no);        }        temp = null;        return temp;    }

教程代码：

public HeroNode preOrderSearch(int no){
           //同链表，根节点和头节点是不动的        //前序查找，现判断当前元素        if (this.getHeroNo() == no){
               return this;        }        HeroNode temp = this;        //如果不相等，再嘀咕比较左子节点是否相等        if (temp.left != null){
               temp = this.left.preOrderSearch(no);        }        if(temp != null){
               return temp;        }        if (this.right != null){
               temp = this.right.preOrderSearch(no);        }        return temp;    }

BinaryTree类的方法public HeroNode preOrderSearch(int no){
           //判断树是否为空        if(isEmpty()){
               return null;        }else{
               return this.root.preOrderSearch(no);        }    }

总结分析：

1. 注意不能直接返回递归的值，如果左子节点的递归没有找到对应的值，那么直接返回空，右子节点就不会在进行遍历递归。所以中间加一个判定条件，如果经历过左子节点遍历后，找到了对应的值就返回，没有找到就接着进行遍历。
   – 没找到别急着返回 –
2. 在BinaryTree类中，记得要进行判定是否为空，然后通过头结点进行调用查询。

中序查找

思路分析

1. 先判断当前节点的左子节点是否为空，不为空就递归终须查找。
2. 如果为空，就判定当前节点的值是否与为查找项，是则返回
3. 不是，那就判定右子节点是否为空，不为空就进行右子节点的递归前序查找
4. 都没有找到，就返回为null

代码实现

代码实现：

HeroNode类：   public HeroNode midOrderSearch(int no){
           HeroNode temp = null;        //首先判定当前节点左子节点是否为空        if (this.left != null){
               temp = this.left.midOrderSearch(no);        }        if (temp != null){
               return temp;        }        if (this.getHeroNo() == no){
               return this;        }        if (this.right != null){
               temp = this.right.midOrderSearch(no);        }        return temp;    }

BinaryTree类：

public HeroNode midOrderSearch(int no){
           if (isEmpty()){
               return null;        }else{
               return this.root.midOrderSearch(no);        }    }

== 原理同上，不做详解==

后序查找

思路分析

1. 先判断当前节点的左子节点是否为空，不为空就递归终须查找。
2. 如果为空，那就判定右子节点是否为空，不为空就进行右子节点的递归前序查找
3. 如果右子节点也为空，那就判定判定当前节点是否为要查找的节点。
4. 都没有找到，就返回为null

代码实现

BinaryTree类：

public HeroNode postOrderSearch(int no){
           if (isEmpty()){
               return null;        }else{
               return this.root.preOrderSearch(no);        }    }

HeroNode类：

public HeroNode postOrder(int no){
           HeroNode temp = null;        if (this.left != null){
               temp = this.left.postOrder(no);        }        if (temp != null){
               return temp;        }        if (this.right != null){
               temp = this.right.postOrder(no);        }        if (temp != null){
               return temp;        }        return this;    }

转载地址：http://nqgpb.baihongyu.com/