树与二叉树
树的定义树(Tree)默认指有根树(Rooted Tree),无根树(Unrooted Tree)之后会在图结构(Graph)中讨论。树是种非线性结构,树中的元素一般称为树节点(Tree Node),线性表元素的前驱后继是空或唯一的,一个树节点可以有不止一个“后继节点”,“前驱节点”是空或唯一的。给出树\(T\)的递归定义如下,递归定义法在算法中经常使用到:
1) \(T\)是由\(n\geq 0\)个节点(Node)组成的有限集合;
2) 当\(n=0\)时,\(T\)是空集称为空树;
3) 当\(n\geq 1\)时,\(T\)有且仅有1个节点被指定为\(T\)的树根(Root);
4) 当\(n\geq 2\)时,\(T\)除树根外的所有节点被划入\(m\geq 1\)个不相交有限集合\(T_1,T_2…T_m\)(即它们的并集是\(T\)除树根外的所有节点,它们中任意2个的交集为空集),并要求\(T_1,T_2…T_m\)都递归的满足树的定义,它们被称为\(T\)的子树(Subtree);… 阅读全文