开发者社区> 问答> 正文

非递归算法,以孩子兄弟为存储结构的计算树的深度 这个程序什么意思 该怎么理解

非递归算法,以孩子兄弟为存储结构的计算树的深度 这个程序什么意思 该怎么理解

展开
收起
知与谁同 2018-07-22 11:48:39 2405 0
1 条回答
写回答
取消 提交回答
  • 首先树的儿子会有很多的,为了解决儿子很多且不定的情况:
    也采用二叉树的存储结构类型,但做了一点改进:
    左节点vp表示大儿子,右节点hp表示兄弟,这样“树”就变成“二叉树”
    的结构了。 右节点串在一起,表示同一层。
    另要搞懂队列,是数组做的循环队列qu[ ], 头front ,尾rear;
    又增加一个数组 level [ ]是队列qu[ ]的辅助单元, 存放 队列节点的层号,两数组
    下标是一一对应的;
    这两个概念是基础,一定要懂。不懂是看不下去的。
    算法的核心:
    1. 用队列的方法遍历所有节点,从队列中取出一个节点指针进行访问,同时
    取出层号,并把这个节点的所有子节点及它的层号放入队列,以便以后取出访问;
    为了启动遍历,初始队列须压入根节点;
    2. 遍历时知道这个节点层号(m),就可比较,最大值(max)就是树的深度。
    3. 遍历访问一个节点时,左节点vp就是大儿子,属下一层,层号是m+!,
    右节点开始就是同层兄弟(第二个while就是),须压入队列,层号仍是m+1;
    4. 反复循环取出队列中节点进行访问(直到为空),并把它的把有儿子压入队列
    以便再次访问;

    这个经典算法,不复杂, 有不明白的再追问
    2019-07-17 22:55:48
    赞同 展开评论 打赏
问答排行榜
最热
最新

相关电子书

更多
数据+算法定义新世界 立即下载
袋鼠云基于实时计算的反黄牛算法 立即下载
Alink:基于Apache Flink的算法平台 立即下载