【6.4】K叉树定义

一、K 叉树定义

K 叉树 T 是具有下列性质的有限结点集:

• (a) 集合可以为空;
• (b) 非空集合是由一个根结点 root 及 K 棵互不相交的 K 叉树构成。

其余结点被划分成 T0，T1，…，T_K-1(K ≥ 1)个子集，每个子集都是 K 叉树，使得 T = {R， T0，T1 ，…，T_K-1}。

K 叉树的各分支结点都有 K 个子结点

二、满 K 叉树和完全 K 叉树

K 叉树 (K-ary Tree) 的结点有 K 个子结点

二叉树的许多性质可以推广到 K 叉树：

• 满K叉树和完全K叉树与满二叉树和完全二叉树是类似的
• 也可以把完全K叉树存储在一个数组中

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾