数组构造二叉树并打印的编程算法

数组构造二叉树并打印的编程算法2015-10-02数组:

构造二叉树, 需要使用两个队列（queue）, 保存子节点和父节点, 并进行交换;

打印二叉树, 需要使用两个队列（queue）, 依次打印父节点和子节点, 并进行交换;

二叉树的数据结构:

struct BinaryTreeNode {int m_nValue;BinaryTreeNode* m_pParent;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight;};

代码:

/** main.cpp**Created on: 2014.6.12*Author: Spike* *//*eclipse cdt, gcc 4.8.1*/#include <iostream>#include <stack>#include <queue>using namespace std;struct BinaryTreeNode {int m_nValue;BinaryTreeNode* m_pParent;BinaryTreeNode* m_pLeft;BinaryTreeNode* m_pRight;};void printTree （BinaryTreeNode* tree）{BinaryTreeNode* node = tree;std::queue<BinaryTreeNode*> temp1;std::queue<BinaryTreeNode*> temp2;temp1.push（node）;while （！temp1.empty（））{node = temp1.front（）;if （node->m_pLeft ！= NULL） {temp2.push（node->m_pLeft）;}if （node->m_pRight ！= NULL） {temp2.push（node->m_pRight）;}temp1.pop（）;std::cout << node->m_nValue<< " ";if （temp1.empty（））{std::cout << std::endl;temp1 = temp2;std::queue<BinaryTreeNode*> empty;std::swap（temp2, empty）;}}}BinaryTreeNode* buildTree （const std::vector<int>& L）{if （L.empty（）） return nullptr;std::queue<BinaryTreeNode*> parentQueue;std::queue<BinaryTreeNode*> childQueue;BinaryTreeNode* root = new BinaryTreeNode（）;root->m_nValue = L[0];parentQueue.push（root）;std::size_t times = 1;while （times < L.size（））{BinaryTreeNode* parent = parentQueue.front（）;parentQueue.pop（）;BinaryTreeNode* lchild = new BinaryTreeNode（）;lchild->m_nValue = L[times];lchild->m_pLeft = nullptr;lchild->m_pRight = nullptr;++times;parent->m_pLeft = lchild;lchild->m_pParent = parent;childQueue.push（lchild）;if （times == L.size（）） break;BinaryTreeNode* rchild = new BinaryTreeNode（）;rchild->m_nValue = L[times];rchild->m_pLeft = nullptr;rchild->m_pRight = nullptr;++times;parent->m_pRight = rchild;rchild->m_pParent = parent;childQueue.push（rchild）;if （parentQueue.empty（）） {parentQueue = childQueue;std::queue<BinaryTreeNode*> empty;std::swap（childQueue, empty）;}}return root;}int main （void）{std::vector<int> L = {49, 38, 65, 97, 76, 13, 27, 49};BinaryTreeNode* tree = buildTree（L）;printTree（tree）;return 0;}

输出:

49 38 65 97 76 13 27 49

作者：csdn博客 Caroline-Wendy