Java中的二叉树结构详解

WBOY

发布时间：2023-06-16 08:58:31

2066人浏览过

来源于php中文网

原创

二叉树是计算机科学中常见的数据结构，也是java编程中常用的一种数据结构。本文将详细介绍java中的二叉树结构。

一、什么是二叉树？

在计算机科学中，二叉树是一种树形结构，每个节点最多有两个子节点。其中，左侧子节点比父节点小，右侧子节点则比父节点大。在Java编程中，常用二叉树表示排序，搜索以及提高对数据的查询效率。

二、Java中的二叉树实现

在Java中，二叉树的实现通常使用节点类（Node Class）和二叉树类（Binary Tree Class）。节点类表示二叉树中每个节点，可以有字节点和存储数据的属性。二叉树类则表示整个二叉树数据结构，具有插入节点、删除节点、遍历等功能。下面是一个简单的Java二叉树实现：

立即学习“Java免费学习笔记（深入）”；

public class Node {
    int key;
    String value;
    Node leftChild, rightChild;

    public Node(int key, String value) {
        this.key = key;
        this.value = value;
    }
}

public class BinaryTree {
    Node root;

    public void insert(int key, String value) {
        Node newNode = new Node(key, value);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            while (true) {
                if (key < current.key) {
                    if (current.leftChild == null) {
                        current.leftChild = newNode;
                        return;
                    }
                    current = current.leftChild;
                } else {
                    if (current.rightChild == null) {
                        current.rightChild = newNode;
                        return;
                    }
                    current = current.rightChild;
                }
            }
        }
    }

    public Node find(int key) {
        Node current = root;
        while (current.key != key) {
            if (key < current.key) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    public void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.leftChild);
            System.out.println(node.key + ": " + node.value);
            inOrderTraversal(node.rightChild);
        }
    }

    public void preOrderTraversal(Node node) {
        if (node != null) {
            System.out.println(node.key + ": " + node.value);
            preOrderTraversal(node.leftChild);
            preOrderTraversal(node.rightChild);
        }
    }

    public void postOrderTraversal(Node node) {
        if (node != null) {
            postOrderTraversal(node.leftChild);
            postOrderTraversal(node.rightChild);
            System.out.println(node.key + ": " + node.value);
        }
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();

        tree.insert(50, "John");
        tree.insert(25, "Alice");
        tree.insert(75, "Bob");
        tree.insert(15, "Chris");
        tree.insert(33, "Diana");
        tree.insert(60, "Emily");
        tree.insert(90, "Fred");

        Node node = tree.find(33);
        System.out.println("Find key: " + node.key + ", value: " + node.value);

        System.out.println("In-order traversal:");
        tree.inOrderTraversal(tree.root);

        System.out.println("Pre-order traversal:");
        tree.preOrderTraversal(tree.root);

        System.out.println("Post-order traversal:");
        tree.postOrderTraversal(tree.root);
    }
}

上面的二叉树代码包括三个主要功能：插入节点，搜索节点，以及三种不同的遍历方式。插入节点使用了while循环来按照二叉树的顺序插入数据；搜索节点则使用了while循环来遍历树搜索目标数据；三种遍历方式都是递归实现的。

三、二叉树的遍历方式

在上面的Java代码中，程序实现了三种不同的二叉树遍历方式：中序遍历、前序遍历和后序遍历。本节将逐一介绍这三种遍历方式。

中序遍历

中序遍历是按照从小到大的顺序遍历树中的节点。在Java代码中，中序遍历的实现使用了递归：对于每个节点，先调用自身的左节点，然后打印节点数据，最后调用自身的右节点。这样，就可以按照从小到大的顺序，遍历树中的所有节点。

前序遍历

前序遍历是按照父节点、左节点、右节点的顺序遍历树中的节点。在Java代码中，前序遍历的实现也使用了递归：对于每个节点，先打印节点数据，然后调用自身的左节点，最后调用自身的右节点。这样，就可以按照父节点、左节点、右节点的顺序，遍历树中的所有节点。

凡人网络购物系统jsp版(JspShop)

基于jsp+javabean+access(mysql)三层结构的动态购物网站，v1.2包含v1.0中未公开的数据库连接的java源文件一，网站前台功能：产品二级分类展示：一级分类－－二级分类－－产品列表－－详细介绍（名称，图片，市场价，会员价，是否推荐，功能介绍等）产品搜索：关键字模糊搜索定购产品：选择商品－－确认定购－－填写收货人信息－－选择付款方式－－订单号自动生成（限登录用户）

下载