树与二叉树的对应关系

当树使用 孩子兄弟表示法 作为其存储结构时,那么就可以使用二叉链表的方式来表示。

于是,任意一颗树就可以找到唯一的对应的二叉树。

树与二叉树的对应关系 - 图1树与二叉树的对应关系 - 图2

转化为:

树与二叉树的对应关系 - 图3

森林与二叉树的对应关系

如果把第二颗树的根节点,当作第一颗树的兄弟节点,依次类推。使用孩子兄弟表示法,同样可以找到与之唯一对应的二叉树。

树与二叉树的对应关系 - 图4

树与二叉树的对应关系 - 图5

于是,树和森林都可以当作是二叉树来执行相同的遍历与查找