计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2011年
9期
16-20,40
,共6页
算法设计%二叉树%中序遍历%快速访问
算法設計%二扠樹%中序遍歷%快速訪問
산법설계%이차수%중서편력%쾌속방문
通过研究二又树结点顺序存储序号的性质,演绎出了二叉树非递归无堆栈的一些新算法,包括完全二叉树两结点最近共同祖先(LCA)的查询算法、中序遍历算法、顺序序列与中序序列的互转算法以及从中序序列恢复层次结构的算法.新的算法都具有很好的时间复杂度,其中LCA查询算法可在常数时间内实现且不需要任何顸处理过程,其他算法均为线性时问复杂度.所有算法均为常数空间复杂度,仅涉及到简单的加减运算与位运算,既可用于常规程序设计也可用于嵌入式等专业开发.
通過研究二又樹結點順序存儲序號的性質,縯繹齣瞭二扠樹非遞歸無堆棧的一些新算法,包括完全二扠樹兩結點最近共同祖先(LCA)的查詢算法、中序遍歷算法、順序序列與中序序列的互轉算法以及從中序序列恢複層次結構的算法.新的算法都具有很好的時間複雜度,其中LCA查詢算法可在常數時間內實現且不需要任何頇處理過程,其他算法均為線性時問複雜度.所有算法均為常數空間複雜度,僅涉及到簡單的加減運算與位運算,既可用于常規程序設計也可用于嵌入式等專業開髮.
통과연구이우수결점순서존저서호적성질,연역출료이차수비체귀무퇴잔적일사신산법,포괄완전이차수량결점최근공동조선(LCA)적사순산법、중서편력산법、순서서렬여중서서렬적호전산법이급종중서서렬회복층차결구적산법.신적산법도구유흔호적시간복잡도,기중LCA사순산법가재상수시간내실현차불수요임하한처리과정,기타산법균위선성시문복잡도.소유산법균위상수공간복잡도,부섭급도간단적가감운산여위운산,기가용우상규정서설계야가용우감입식등전업개발.
