Initial commit

1 files changed, 78 insertions, 0 deletions

diff --git a/content/posts/【数据结构与算法】二叉树.md b/content/posts/【数据结构与算法】二叉树.md
new file mode 100644
index 0000000..2e58426
--- /dev/null
+++ b/content/posts/【数据结构与算法】二叉树.md
@@ -0,0 +1,78 @@
+---
+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);
+  }
+}
+```