編程算法 - 數組構造二叉樹並打印

數組構造二叉樹並打印

數組:

構造二叉樹, 需要使用兩個隊列(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