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

二叉树查找技术详解

二叉树在数据结构中扮演着重要角色，常用于查找、排序等操作。本文将详细介绍二叉树的前序、中序、后序查找技术及其实现。

前序查找思想

前序查找法首先检查当前节点是否为目标值。如果是，立即返回该节点。如果不是，则先递归查找左子节点，若找到目标节点则返回，否则继续查找右子节点。

中序查找思想

中序查找法则先递归查找左子节点。如果左子节点未找到目标值，则检查右子节点。若在右子节点中找到目标值，则返回该节点，否则返回null。

后序查找思想

后序查找法则首先递归查找左子节点。如果左子节点未找到目标值，则检查右子节点。若在右子节点中找到目标值，则返回该节点，否则检查当前节点是否为目标值。

二叉树实现代码

package com.shujujiegou;public class Ran {    public static void main(String[] args) {        // 创建二叉树根节点        HeroNode root = new HeroNode(1, "qqq");        HeroNode node2 = new HeroNode(2, "www");        HeroNode node3 = new HeroNode(3, "eee");        HeroNode node4 = new HeroNode(4, "rrr");                // 设置子节点        root.setLeft(node2);        root.setRight(node3);        node3.setRight(node4);                // 前序遍历        System.out.println("前序遍历：");        root.printPreOrder();                // 中序遍历        System.out.println("中序遍历：");        root.printInOrder();                // 后序遍历        System.out.println("后序遍历：");        root.printPostOrder();                // 查找测试        HeroNode emp = root.findPreOrder(1);        if (emp != null) {            System.out.println("找到了节点： " + emp);        } else {            System.out.println("未找到节点5");        }    }}class HeroNode {    private int no;    private String name;    private HeroNode left;    private HeroNode right;    public HeroNode(int no, String name) {        this.no = no;        this.name = name;    }    public void printPreOrder() {        System.out.println(this);        if (left != null) {            left.printPreOrder();        }        if (right != null) {            right.printPreOrder();        }    }    public void printInOrder() {        if (left != null) {            left.printInOrder();        }        System.out.println(this);        if (right != null) {            right.printInOrder();        }    }    public void printPostOrder() {        if (left != null) {            left.printPostOrder();        }        if (right != null) {            right.printPostOrder();        }        System.out.println(this);    }    public HeroNode findPreOrder(int no) {        if (this.no == no) {            return this;        }        HeroNode result = null;        if (left != null) {            result = left.findPreOrder(no);        }        if (result != null) {            return result;        }        if (right != null) {            result = right.findPreOrder(no);        }        return result;    }    public HeroNode findInOrder(int no) {        if (left != null) {            HeroNode result = left.findInOrder(no);            if (result != null) {                return result;            }        }        if (this.no == no) {            return this;        }        if (right != null) {            HeroNode result = right.findInOrder(no);            return result;        }        return null;    }    public HeroNode findPostOrder(int no) {        HeroNode result = null;        if (left != null) {            result = left.findPostOrder(no);        }        if (result != null) {            return result;        }        if (right != null) {            result = right.findPostOrder(no);        }        if (result != null) {            return result;        }        if (this.no == no) {            return this;        }        return null;    }    public void setLeft(HeroNode left) {        this.left = left;    }    public void setRight(HeroNode right) {        this.right = right;    }}

代码运行效果

通过上述代码，可以完成二叉树的查找操作。前序遍历输出顺序为1 2 3 4，中序遍历顺序为2 1 3 4，后序遍历顺序为2 4 3 1。查找测试结果显示能够正确找到目标节点。

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