# 二叉树及相关数据结构的java语言实现

***

二叉树是一种很直观的非线性数据结构。本篇主要记录与二叉树相关的数据结构的java语言实现方法。

## 一、二叉树

### 1. 节点

既然有java，就简简单单用类来实现节点。

```java
class TreeNode{
    int value;
    TreeNode leftNode;
    TreeNode rightNode;
    //构造函数
    TreeNode(int v){
        this.value = v;
    }
}
```

main函数手动建树：

```java
    public static void main(String[] args){
        TreeNode node1 = new TreeNode(10);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(30);
        TreeNode node4 = new TreeNode(15);
        TreeNode node5 = new TreeNode(6);
        node1.leftNode = node2;
        node1.rightNode = node3;
        node3.leftNode = node4;
        node2.rightNode = node5;
        //结构：10 - 30 - 15
        //        - 3  - 6
```

这样就建好了一个无序的二叉树。

### 2. 遍历

一般遍历有深度优先和广度优先两种，深度包括先序、后序、中序遍历。这三者区别主要是先序遍历优先访问中间节点，中序是在中间访问中间节点（先访问左节点，后中节点，后右节点），后序遍历是先左右节点最后中间节点。

```java
static void traversal(TreeNode node){
        //先序遍历
        if(node == null) return;
        System.out.println(node.value);
        traversal(node.leftNode);
        traversal(node.rightNode);
    }
```

广度优先遍历即层次遍历，和`bfs`类似，将首节点入队，每次循环从队伍中取出一个点，输出中间节点，把左右子节点入队，从上到下按层访问。

```java
static void layerTraversal(TreeNode node){
        //层次遍历（bfs）
        if(node == null) return;
        LinkedList<TreeNode> list = new LinkedList<TreeNode>();
        list.add(node);
        while(!list.isEmpty()){
            TreeNode node_now = list.removeFirst();
            System.out.println(node_now.value);
            // 左右儿子通通入队
            if(node_now.leftNode != null)
            list.add(node_now.leftNode);
            if(node_now.rightNode != null)
            list.add(node_now.rightNode);
        }
    }
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/shu-ju-jie-gou/er-cha-shu-ji-xiang-guan-shu-ju-jie-gou-de-java-yu-yan-shi-xian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.