二叉排序树的asl公式

145次

问题描述:

二叉排序树构造算法

推荐答案

2023-10-24 18:22:03

对于二叉排序树的ASL算法

二叉排序树的特点是左孩子小于根节点,右孩子大于根节点

之前寻找博客上计算ASL的算法时,看到用的是设置一个max值来判断是否换层,遍历二叉排序树,若是大于max则是属于同一层,赋值给max,直到找到小于max的节点就是下一层,但是对于如果一层中只有最后一个节点(即这一层最大的节点)有右孩子,max值就一直是增加的,则不会换层

解决方法

使用一个父节点数组和队列,有孩子节点则加入父节点队列,存储每一层的父节点数,一层结束后输出前面的父节点,只留下该层最后一父节点,则可以判断一层结束;

若节点队列为空且当前节点无孩子,则整个二叉排序树结束。

知道问答相关问答

(c)2008-2025 自学教育网 All Rights Reserved 汕头市灵创科技有限公司
粤ICP备2024240640号-6