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

二叉树概述与常用操作

二叉树是一种常见的数据结构，广泛应用于查找和排序操作中。它以数组或链表的速度优势，成为高效数据处理的重要工具。本文将深入探讨二叉树的基本概念、类型及其应用方法。

二叉树的定义

二叉树是指每个结点最多有两个子节点的树形结构。通常称左子树（left subtree）和右子树（right subtree）。二叉树在键值存储和检索方面具有独特优势，与数组的查找速度和链表的插入删除速度结合，一旦实现后，操作效率显著提升。

二叉树的关键特质

二叉树的分类

二叉搜索树属性

二叉查找树（BST）基于特定规定：任意节点所有左子树节点值小于父值，右子树节点值大于父值。保障较高的查询效率。

二叉树操作方法

1. 查找操作

查找过程从根节点开始：若目标值小于当前节点，转向左子树；若大于，转向右子树。若当前节点为None，返回null。

示例：查找节点13，路径为：

• 根节点15 → 左子节点5 → 右子节点12 → 左子节点13。

2. 插入操作

插入坐标类似查找，但非存在时新增节点。插入13：

• 根节点15 → 左子10 → 右子14 → 根节点即插入。

3. 删除操作

删除分为几种情况：

例如，删除节点25的过程涉及检查左右结构，找其继继承者，并更新父节点引lw。

二叉树遍历方法

这些遍历方式不同访问顺序，常用于数据处理任务选择优化。

实现代码示例

以下代码展示了Node结构、查找、插入、删除和遍历方法。

class Node {    public int iData; // 数据键值    public double dData; // 数据值    public Node leftChild;    public Node rightChild;    public void displayNode() {        System.out.println("{ " + iData + ", " + dData + " }");    }}class Tree {    Node root;    public Tree() {        root = null;    }    public Node find(int key) {        Node current = root;        while (current != null) {            if (key < current.iData) {                current = current.leftChild;            } else {                current = current.rightChild;            }        }        return current;    }    public void insert(int id, double dd) {        Node newNode = new Node();        newNode.iData = id;        newNode.dData = dd;        if (root == null) {            root = newNode;        } else {            Node current = root;            Node parent = current;            while (true) {                parent = current;                if (id < current.iData) {                    current = current.leftChild;                    if (current == null) {                        parent.leftChild = newNode;                        break;                    }                } else {                    current = current.rightChild;                    if (current == null) {                        parent.rightChild = newNode;                        break;                    }                }            }        }    }    public boolean delete(int key) {        Node current = root;        Node parent = root;        boolean isLeftChild = true;        while (current.iData != key) {            parent = current;            if (key < current.iData) {                isLeftChild = true;                current = current.leftChild;            } else {                isLeftChild = false;                current = current.rightChild;            }            if (current == null) {                return false;            }        }        Node successor;        if (current.leftChild == null && current.rightChild == null) {            if (current == root) {                root = null;            } else if (isLeftChild) {                parent.leftChild = null;            } else {                parent.rightChild = null;            }        } else if (current.leftChild == null) {            if (current == root) {                root = current.rightChild;            } else if (isLeftChild) {                parent.leftChild = current.rightChild;            } else {                parent.rightChild = current.rightChild;            }        } else if (current.rightChild == null) {            if (current == root) {                root = current.leftChild;            } else if (isLeftChild) {                parent.leftChild = current.leftChild;            } else {                parent.rightChild = current.leftChild;            }        } else {            successor = getSuccessor(current);            if (current == root) {                root = successor;            } else if (isLeftChild) {                parent.leftChild = successor;            } else {                parent.rightChild = successor;            }            successor.leftChild = null;            successor.rightChild = null;        }        return true;    }    private Node getSuccessor(Node delNode) {        Node successorParent = delNode;        Node successor = delNode.rightChild;        Node current = delNode.rightChild;        while (current != null) {            successorParent = successor;            successor = current;            current = current.leftChild;        }        if (successor != delNode.rightChild) {            successorParent.leftChild = successor.rightChild;            successor.rightChild = delNode.rightChild;        }        return successor;    }    public void displayTree() {        Stack globalStack = new Stack();        globalStack.push(root);        int nBlanks = 32;        boolean isRowEmpty = false;        System.out.println("========================================================================");        while (!isRowEmpty) {            Stack localStack = new Stack();            isRowEmpty = true;            for (int j = 0; j < (root.depth +1); j++) {                localStack.push(globalStack.pop());            }            while (!localStack.isEmpty()) {                Node current = localStack.pop();                localStack.push(current.rightChild);                localStack.push(current);                System.out.print("   ");            }            System.out.println("========================================================================");        }    }    List preList = new ArrayList();    List afterList = new ArrayList();    List inList = new ArrayList();    void preOrder(Node localRoot) {        if (localRoot != null) {            preList.add(localRoot.iData);            preOrder(localRoot.leftChild);            preOrder(localRoot.rightChild);        }    }    void inOrder(Node localRoot) {        if (localRoot != null) {            inOrder(localRoot.leftChild);            inList.add(localRoot.iData);            inOrder(localRoot.rightChild);        }    }    void postOrder(Node localRoot) {        if (localRoot != null) {            postOrder(localRoot.leftChild);            postOrder(localRoot.rightChild);            afterList.add(localRoot.iData);        }    }    void traverse(int type) {        switch (type) {            case 1:                System.out.print("\npre order : ");                preOrder(root);                break;            case 2:                System.out.print("\nin order : ");                inOrder(root);                break;            case 3:                System.out.print("\npost order : ");                postOrder(root);                break;            default:                break;        }    }    public static void main(String[] args) {        Tree theTree = new Tree();        theTree.insert(50, 1.3);        theTree.insert(25, 1.1);        theTree.insert(75, 1.7);        theTree.insert(12, 1.3);        theTree.insert(37, 1.9);        theTree.insert(43, 1.4);        theTree.insert(87, 1.6);        theTree.insert(93, 1.2);        theTree.insert(97, 1.5);        theTree.insert(30, 1.4);        theTree.insert(19, 1.3);        Node node = theTree.find(93);        System.out.println(node.dData);        theTree.displayTree();        System.out.println("\n删除一个节点 -------------");        theTree.delete(25);        theTree.traverse(1);    }}

测试与验证

通过上述代码和树形结构，可以运行测试程序观察结果。查找、插入、删除操作均可验证。最终，可以自行修改数据填充以适应具体需求。

二叉树作为基础数据结构，在数据存储管理中的应用广泛。理解其原理和运用方法，对于数据结构与算法的学习至关重要，同时也是提升编程能力的关键环节。