1004 Counting Leaves 对于树的存储方式的回顾

时间:2022-04-04 08:17:38

一种新的不使用左右子树递归进行树高计算的方法,使用层次遍历

树的存储方式:

1.本题提供的一种思路:

使用(邻接表的思想)二维数组(vector[n])表示树,横坐标表示 父节点,每一行表示孩子。

能够很轻松的使用dfs进行遍历

优点:

只需要知道输入的父和子的值,不需要清楚整个树的结构,

能够方便的使用深搜遍历,计算树高;dfs(root,high);

缺点:

占空间太大,提前要知道节点数的上限

2.双亲表示法

每个节点只有一个指向父节点的指针,

优点:

能够方便的从叶节点往回找,空间小

缺点:

叶节点不好找,可以用一个数组把所有指向叶节点的指针都存起来;

3.孩子兄弟表示法

用于多叉树,以及多棵树合并

对于输出的控制,有时候要求最后一项之后不能有空格

解决办法:在循环外先输出第一行,然后接着再循环

或者每次输出前都判断一下是不是最后一项,再输出