給定一個n節點二叉樹，寫出一個O(n)時間的非遞歸的過程，將該樹每個結點的關鍵字輸出。要求除該樹本樹的存儲空間外只能使用固定量的額外存儲空間，且過程中不得修改該樹，即使是暫時的修改也不允許。

（算法導論第三版第十章10.4-5）

template<typename T> void TraverseBinaryTreeNonRecursive(const BinaryTreeNodeIndex<T>* array,int index) {int prev = -1;int current = index;while (current!= -1){if(prev == array[current].parent){std::cout<<array[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::cout<<endl; }

輔助類 BinaryTreeNodeIndex
地址
測試代碼

BinaryTreeNodeIndex<int> binaryTreeNode[10] = {BinaryTreeNodeIndex<int>(12,5,6,2),BinaryTreeNodeIndex<int>(15,7,7,-1),BinaryTreeNodeIndex<int>(4,0,9,-1),BinaryTreeNodeIndex<int>(10,5,4,8),BinaryTreeNodeIndex<int>(2,3,-1,-1),BinaryTreeNodeIndex<int>(18,-1,0,3),BinaryTreeNodeIndex<int>(7,0,-1,-1),BinaryTreeNodeIndex<int>(14,1,5,1),BinaryTreeNodeIndex<int>(21,3,-1,-1),BinaryTreeNodeIndex<int>(5,2,-1,-1),};TraverseBinaryTreeNonRecursive(binaryTreeNode,5);

總結

以上是生活随笔為你收集整理的给定一个n节点二叉树，写出一个O(n)时间的非递归的过程，将该树每个结点的关键字输出（算法导论第三版第十章10.4-5）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。