本文已使用 Google Cloud Translation API 自动翻译。
某些文档最好以原文阅读。
二叉树是一种数据结构,它允许两个节点通过从根到最左边的孩子以及从最左边的孩子到最右边的孩子的路径链接在一起。该路径称为从根到最左边的孩子,以及从最左边的孩子到最右边的孩子的路径。
二叉树是一种递归数据结构,这意味着它可以根据自身来定义。二叉树是每个节点都有两个孩子的树。根节点是树中最顶端的节点。左子节点是通过从根节点到最左子节点的路径连接到根节点的节点。右孩子是通过从根节点到最右孩子的路径连接到根节点的节点。
节点的孩子有时分别称为左孩子和右孩子。父项和子项也用于描述二叉树中节点之间的关系。如果第一个节点通过从根节点到第一个节点的路径连接到第二个节点,则一个节点是另一个节点的父节点。如果第一个节点通过从第一个节点到第二个节点的路径连接到第二个节点,则该节点是另一个节点的子节点。
节点的高度是从根节点到该节点的最长路径的长度。树的高度是根节点的高度。
节点的深度是从根节点到该节点的最短路径的长度。树的深度是根节点的深度。
如果每个节点都有两个孩子或没有孩子,则称二叉树是满的。如果每个节点都有两个孩子或没有孩子,并且所有叶子都在相同的深度,则称二叉树是完整的。
如果左子树的高度和右子树的高度最多相差 1,则称二叉树是平衡的。
下面是一个二叉树的例子:
1个
/ \
2 3
/ \
4 5
根节点为1。1的左孩子为2。1的右孩子为3。2的左孩子为4。2的右孩子为5。
根节点的深度为0。节点2的深度为1。节点3的深度为1。节点4的深度为2。节点5的深度为2。
根节点的高度为2。节点2的高度为1。节点3的高度为1。节点4的高度为0。节点5的高度为0。
树满了。树完成了。树是平衡的。