> For the complete documentation index, see [llms.txt](https://lfool.gitbook.io/data-structure/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lfool.gitbook.io/data-structure/shu.md).

# 树

## 1. 树的定义

**树（Tree）**： $$n(n \ge 0)$$ 个结点构成的有限集合

当 $$n = 0$$ 时，称为 **空树**

对于任一棵 **非空树** $$(n > 0)$$ ，它具备以下性质：

* 树中有一个称为 “**根（Root）**”的特殊结点，用 r 表示；
* 其余结点可分为 $$m(m > 0)$$ 个 **互不相交的** 有限集 $$T\_1,T\_2, \cdots , T\_m$$ ，其中每个集合本身又是一棵树，称为原来树的“**子树**（SubTree）”

## 2. 树的一些基本术语

1. **结点的度（Degree）**：结点的 **子树个数**
2. **树的度**：树的所有结点中最大的度数
3. **叶结点（Leaf）**：**度为 0** 的结点
4. **父节点（Parent）**：有子树的结点是其子树的根结点的父结点
5. **子结点（Child）**：若 A 结点是 B 结点的父结点，则称 B 结点是 A 结点的子结点；子结点也称 **孩子结点**
6. **兄弟结点（Sibling）**：具有同一父结点的各结点彼此是兄弟结点
7. **路径和路径长度**：从结点 $$n\_1$$ 到 $$n\_k$$ 的 **路径** 为一个结点序列 $$n\_1,n\_2, \cdots, n\_k$$ ， $$n\_i$$ 是 $$n\_{i+1}$$ 的父结点。路径所包含的个数为 **路径的长度**
8. **祖先结点（Ancestor）**：沿 **树根到某一结点路径** 上的所有结点都是这个结点的祖先结点
9. **子孙结点（Descendant）**：某一结点的 **子树中所有结点** 是这个结点的子孙结点
10. **结点的层次（Level）**：规定 **根结点在1层**，其他任一结点的层数是其父结点层数加1
11. **树的深度（Depth）**：树中所有结点中的 **最大层次** 是这棵树的深度

## 3. 树的表示

**儿子 - 兄弟表示法**

![](/files/-MC1EwRVdSsjq5BI4UEd)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://lfool.gitbook.io/data-structure/shu.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.