二叉树的基本概念

树的基本术语

Root The top node in a tree. 树的顶端结点
Child A node directly connected to another node when moving away from the Root. 孩子 当远离根(Root)的时候,直接连接到另外一个结点的结点被称之为孩子(Child); 
Parent The converse notion of a child. 双亲 相应地,另外一个结点称为孩子(child)的双亲(parent)。
Siblings A group of nodes with the same parent. 兄弟 具有同一个双亲(Parent)的孩子(Child)之间互称为兄弟(Sibling)。
Ancestor A node reachable by repeated proceeding from child to parent. 祖先 结点的祖先(Ancestor)是从根(Root)到该结点所经分支(Branch)上的所有结点。
Descendant A node reachable by repeated proceeding from parent to child. 子孙 以某结点为根的子树中的任一结点都称为该结点的子孙(后代)。
Leaf A node with no children. 叶子(终端结点) 没有孩子的结点(也就是度为0的结点)称为叶子(Leaf)或终端结点。
Branch A node with at least one child. 分支(非终端结点) 至少有一个孩子的结点称为分支(Branch)或非终端结点。
Degree The number of sub trees of a node. 结点所拥有的子树个数称为结点的度(Degree)。
Edge The connection between one node and another. 一个结点和另一个结点之间的连接被称之为边(Edge)。
Path A sequence of nodes and edges connecting a node with a descendant. 路径 连接结点和其后代的结点之间的(结点,边)的序列。 
Level The level of a node is defined by 0 + (the number of connections between the node and the root). 层次 结点的层次(Level)从根(Root)开始定义起,根为第0层,根的孩子为第1层。以此类推,若某结点在第i层,那么其子树的根就在第i+1层。
Height of node The height of a node is the number of edges on the longest path between that node and a leaf. 结点的高度 结点的高度是该结点和某个叶子之间存在的最长路径上的边的个数。 
Height of tree The height of a tree is the height of its root node. 树的高度 树的高度是其根结点的高度。 
Depth of node The depth of a node is the number of edges from the tree's root node to the node. 结点的深度 结点的深度是从树的根结点到该结点的边的个数。 (注:树的深度指的是树中结点的最大层次。)
Forest A forest is a set of n ≥ 0 disjoint trees. 森林 森林是n(>=0)棵互不相交的树的集合。

二叉树的定义

树形结构是一种非线性结构,二叉树是度为2,即子结点的个数最多为2的有序树(左右子树是有次序的)。 

二叉树的性质

(1)若二叉树的层次从0开始,则在二叉树的第i层至多有2^i个结点(i>=0)。

(2)高度为k的二叉树最多有2^(k+1) - 1个结点(k>=-1)。 (空树的高度为-1)

(3)对任何一棵二叉树,如果其叶子结点(度为0)数为m, 度为2的结点数为n, 则m = n + 1。

完全二叉树

A Complete Binary Tree (CBT) is a binary tree in which every level, 
except possibly the last, is completely filled, and all nodes 
are as far left as possible.

满二叉树

A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. 
All internal nodes have degree 2.

一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树

 

最后修改于 2019-11-13 15:46:20
如果觉得我的文章对你有用,请随意赞赏
扫一扫支付
上一篇