二叉树

树是特殊的图,\(T= \left ( V,E \right )\),节点数|V|=n,边数|E|=e。指定任一节点r∈V作为根后,T即称作有根树(rooted tree)。若:T1, T2, …, Td为有根树,则:T=((∪Vi)∪{r}, (∪Ei)∪{<r, ri>|1≤i≤d})也是,相对于T,Ti称作以ri为根的子树(subtree rooted at ri),记作Ti=subtree(ri)。ri称作r的孩子(child),ri之间互称兄弟(sibling),r为其父亲(parent),d=degree(r)为r的(出)(degree)。可归纳证明:,故在衡量相关复杂度时,可以n作为参照。若指定Ti作为T的第i棵子树,ri作为r的第i个孩子,则T称作有序树(ordered tree)。



发表评论

电子邮件地址不会被公开。 必填项已用*标注