---
abbrlink: 1421131593
categories:
- 往昔
date: "2025-05-25 18:46:37"
tags:
- 数据结构与算法
title: 【数据结构与算法】二叉树
---
## 定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

## 实现

### 结构定义

~~尝试了一下C语言，各种指针乱指，各种bug，暂时放自己一马，跟自己和解一下用js写写吧。~~

```js
class TreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;  // 左节点
    this.right = null; // 右边节点
  }
}
```

### 创建对象并绑定节点

```js
// 手动绑定节点
let root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(3)
root.left.left = new TreeNode(4)
root.right.right = new TreeNode(5)
```

此时树的结构：
```
      1
     /  \
     2   3
   /  \   \
  4    5   6
```

### 遍历二叉树

#### 前序遍历（DFS）

```js
function preOrder(node) {
  if(node) {
    console.log(node.data)
    preOrder(node.left)
    preOrder(node.right)
  }
}
```
这里用递归调用，遍历到左右元素

#### 层序遍历（BFS）

```js
function levelOrder(root) {
  const queue = [];
  queue.push(root);
  while (queue.length) {
    const node = queue.shift();
    console.log(node.data);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}
```