📚 Tree Data Structure: Key Concepts for IB & OCR Computer Science | 树数据结构：IB 与 OCR 计算机科学考点精讲
A tree is a fundamental non-linear data structure that models hierarchical relationships. For IB and OCR Computer Science students, understanding trees is essential for topics such as data representation, algorithm design, and abstract data types. This revision guide covers definitions, terminology, binary trees, binary search trees, traversal methods, implementations, and exam-focused tips, ensuring you are well-prepared for both multiple-choice and written questions.
树是一种基本的非线性数据结构，用于模拟层次关系。对于 IB 和 OCR 计算机科学学生而言，理解树对于数据表示、算法设计和抽象数据类型等主题至关重要。这份复习指南涵盖定义、术语、二叉树、二叉搜索树、遍历方法、实现及考试技巧，帮助您充分准备选择题和书面题。
1. What is a Tree? | 什么是树？
A tree is a connected, acyclic graph consisting of nodes and edges. It has a designated root node, from which all other nodes descend. This hierarchical structure ensures that there is exactly one path between any two nodes. Trees are widely used to represent directory filesystems, organisation charts, HTML DOM objects, and network routing algorithms.
树是由节点和边组成的连通无环图。它有一个指定的根节点，所有其他节点都由此衍生。这种层次结构确保任意两个节点之间只有唯一一条路径。树广泛用于表示目录文件系统、组织架构图、HTML DOM 对象和网络路由算法。
If a tree contains n nodes, it will always have n – 1 edges. Adding any extra edge would create a cycle, violating the tree property. Every node except the root has exactly one parent, making it a natural model for one-to-many relationships.
如果一棵树有 n 个节点，则它一定有 n – 1 条边。添加任何额外的边都会产生环路，破坏树的性质。除根节点外，每个节点恰好有一个父节点，这使其成为一对多关系的天然模型。
2. Tree Terminology | 树的术语
Root: the topmost node of the tree, with no parent. Leaf: a node with no children. Internal node: a node that has at least one child. Subtree: a node together with all its descendants. Siblings: nodes that share the same parent.
根：树的最顶层节点，没有父节点。叶：没有子节点的节点。内部节点：至少有一个子节点的节点。子树：节点及其所有后代构成的树。兄弟节点：拥有相同父节点的节点。
Depth of a node: the number of edges from the root to that node. The root has depth 0. Height of a node: the number of edges on the longest downward path from that node to a leaf. The height of the tree is the height of the root. Level: all nodes at the same depth form a level; the root is at level 0.
节点的深度：从根到该节点的边数，根的深度为 0。节点的高度：从该节点到叶节点的最长向下路径上的边数。树的高度等于根的高度。层：同一深度的所有节点构成一层，根在第 0 层。
Degree of a node: the number of children
Published by TutorHao | IB Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图