电子网站建,wordpress计次查询,营销方式和手段有哪些,网站 框架网页建设给定一个n节点二叉树#xff0c;写出一个O(n)时间的非递归的过程#xff0c;将该树每个结点的关键字输出。要求除该树本树的存储空间外只能使用固定量的额外存储空间#xff0c;且过程中不得修改该树#xff0c;即使是暂时的修改也不允许。
#xff08;算法导论第三版第十…给定一个n节点二叉树写出一个O(n)时间的非递归的过程将该树每个结点的关键字输出。要求除该树本树的存储空间外只能使用固定量的额外存储空间且过程中不得修改该树即使是暂时的修改也不允许。
算法导论第三版第十章10.4-5
templatetypename T
void TraverseBinaryTreeNonRecursive(const BinaryTreeNodeIndexT* array,int index)
{int prev -1;int current index;while (current! -1){if(prev array[current].parent){std::coutarray[current].key ;prev current;if(array[current].left! -1){current array[current].left;}else{if(array[current].right! -1){current array[current].right;}elsecurrent array[current].parent;}}else if(prev array[current].left array[current].right! -1){prev current;current array[current].right;}else{prev current;current array[current].parent;}}std::coutendl;
}辅助类 BinaryTreeNodeIndex 地址 测试代码 BinaryTreeNodeIndexint binaryTreeNode[10] {BinaryTreeNodeIndexint(12,5,6,2),BinaryTreeNodeIndexint(15,7,7,-1),BinaryTreeNodeIndexint(4,0,9,-1),BinaryTreeNodeIndexint(10,5,4,8),BinaryTreeNodeIndexint(2,3,-1,-1),BinaryTreeNodeIndexint(18,-1,0,3),BinaryTreeNodeIndexint(7,0,-1,-1),BinaryTreeNodeIndexint(14,1,5,1),BinaryTreeNodeIndexint(21,3,-1,-1),BinaryTreeNodeIndexint(5,2,-1,-1),};TraverseBinaryTreeNonRecursive(binaryTreeNode,5);
