非递归算法,以孩子兄弟为存储结构的计算树的深度 这个程序什么意思 该怎么理解-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

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

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

    这个经典算法,不复杂, 有不明白的再追问
    0 0
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题
推荐课程