数组构造二叉树并打印

?

数组:

构造二叉树, 需要使用两个队列(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 
  
   
#include 
   
     #include 
    
      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
     
       temp1; std::queue
      
        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
       
         empty; std::swap(temp2, empty); } } } BinaryTreeNode* buildTree (const std::vector
        
         & L) { if (L.empty()) return nullptr; std::queue
         
           parentQueue; std::queue
          
            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
           
             empty; std::swap(childQueue, empty); } } return root; } int main (void) { std::vector
            
              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 

?

?

?

?

?