09/05/2021
Binary Tree Overview
https://web.archive.org/web/20180704064217/http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html
1/4
The Wayback Machine - https://web.archive.org/web/20180704064217/http://faculty.cs.niu.edu/~mcmaho…
Binary Tree Overview
Formal Definition of a Binary Tree
A binary tree consists of a finite set of nodes that is either empty, or consists of one specially designated
node called the root of the binary tree, and the elements of two disjoint binary trees called the left subtree and
right subtree of the root.
Note that the definition above is recursive: we have defined a binary tree in terms of binary trees. This is
appropriate since recursion is an innate characteristic of tree structures.
Diagram 1: A binary tree
Binary Tree Terminology
Tree terminology is generally derived from the terminology of family trees (specifically, the type of family
tree called a lineal chart).
Each root is said to be the parent of the roots of its subtrees.
Two nodes with the same parent are said to be siblings; they are the children of their parent.
The root node has no parent.
A great deal of tree processing takes advantage of the relationship between a parent and its children,
and we commonly say a directed edge (or simply an edge) extends from a parent to its children. Thus
edges connect a root with the roots of each subtree. An undirected edge extends in both directions
between a parent and a child.
Grandparent and grandchild relations can be defined in a similar manner; we could also extend this
terminology further if we wished (designating nodes as cousins, as an uncle or aunt, etc.).
Other Tree Terms
The number of subtrees of a node is called the degree of the node. In a binary tree, all nodes have
degree 0, 1, or 2.
A node of degree zero is called a terminal node or leaf node.
A non-leaf node is often called a branch node.
The degree of a tree is the maximum degree of a node in the tree. A binary tree is degree 2.
A directed path from node n
1
to n
k
is defined as a sequence of nodes n
1
, n
2
, ..., n
k
such that n
i
is the
parent of n
i
+1 for 1 <= i < k. An undirected path is a similar sequence of undirected edges. The length
of this path is the number of edges on the path, namely k – 1 (i.e., the number of nodes – 1). There is a
资源评论
2401_87476784
- 粉丝: 0
- 资源: 1
最新资源
- Thonny 4.1.6 3.10 适用于Windows11/10/8.1系统
- 目标检测红外检测人车狗猫数据集19000张VOC+YOLO格式.zip
- 基于前端的3D动态立方体效果
- 信捷xdm plc三轴可编程运动控制程序，支持信捷XDM系列PLC 信捷TG765触摸屏 支持直线插补
- 目标检测集装箱编号检测数据集2990张VOC+YOLO格式.zip
- 光储直流微电网下垂控制母线电压分层控制（含光伏储能电网负载） 1分布式电源（光伏）：150kW，MPPT运行模式 2储能
- web前端3D动态心形，表白工具
- 飞翔的小鸟 scratch
- 目标检测红外夜间行人检测数据集8690张VOC+YOLO格式（视频截取不同时间段图片标注）.zip
- web端实现《别踩白块》小游戏
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
