806      人物

非遞歸方式創建二叉樹

好長時間沒摸過二叉樹了，純屬練手

我發現功能描述發布出來就亂了，還是貼圖吧

#include <iostream>

using namespace std;
#define Type char
#define MAX_BUFF 30
#define INC_BUFF 20

typedef struct _TreeNode
{
	Type data;
	struct _TreeNode *lchild;
	struct _TreeNode *rchild;
}TreeNode;


TreeNode *createNode()
{
	TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
	memset(node, 0, sizeof(TreeNode));
	return node;
}
/***************************
function: createPreBinTree
description:根據先序曆遍二叉樹序列創建二叉樹，曆遍序列需要給出空樹
如：
                                    A
				   /   \
		                 B     D
				/      /
			      C     E
                                \
				 G
先序了變序列是： ABC@G@@@DE@@@ (其中@代表空樹)
原理：每當操作一個節點就將其push壓棧，遇到空@就pop。
pop的目的就是為了創建右孩子。
****************************/
TreeNode *createPreBinTree()
{
	char buff[MAX_BUFF];
	cin >> buff;
	char *pBuffer = buff;

	TreeNode *stack[MAX_BUFF] = {0};//定義棧
	TreeNode **spHead = stack;
	TreeNode **spTail = stack;
	TreeNode *pTree = NULL;
	TreeNode *rootNode = NULL;
	bool isCreateR = false;

	if ( '@' == *pBuffer)
		return NULL;
	else
	{
		rootNode = createNode();
		pTree = rootNode;
		rootNode->data = *pBuffer;
		pBuffer++;
		*(++spHead) = rootNode;

		//if ('@' == *pBuffer)//判斷root節點是否需要壓棧
		//	isCreateR = true;
		//else
		//{
		//	
		//	isCreateR = false;
		//}
	}

	for (int i = 0;(*pBuffer); i++)
	{
		if ( '@' != *pBuffer)
		{
			if ( !isCreateR){//此時創建的是左孩子，需要壓棧，壓棧的目的是為了以後創建右孩子
				TreeNode *newNode = createNode();
				newNode->data = *pBuffer;
				pTree->lchild = newNode;
				pTree = newNode;
				*(++spHead) = newNode;
				/*spHead++;
				*spHead = newNode;*/
			}
			else
			{
				TreeNode *newNode = createNode();
				newNode->data = *pBuffer;
				pTree->rchild = newNode;
				pTree = newNode;
				*(++spHead) = newNode;
				isCreateR = false;
			}//if !isCreateR
		}
		else
		{
			if ( !isCreateR)
			{
				isCreateR = true;
				/*pTree = *spHead;
				*(spHead--) = NULL;*/
			}
			//else
			//{
			//	//isCreateR = true;//遇到右孩子是空，此時需要彈出棧頂
			//	if ( spHead == spTail)
			//		break;
			//}//if !isCreateR;

			if (spHead == spTail)
				break;
			else
			{
				pTree = *spHead;
				*(spHead--) = NULL;
			}
		}//if @
		pBuffer++;
	}
	return rootNode;
}

void visitNode(TreeNode *p)
{
	cout << p->data;
}

//先序曆遍二叉樹
void preTraverse(TreeNode *p)
{
	TreeNode *stack[MAX_BUFF] = {0};
	TreeNode **spTail = stack;
	TreeNode **spHead = spTail + 1;

	TreeNode *root = p;
	TreeNode *curr = root;

	//visitNode(root);
	//*(++spHead) = root;

	do
	{
		if (curr)
		{
			visitNode(curr);
			*(++spHead) = curr;
			curr = curr->lchild;
		}
		else 
		{
			if (spHead -1 != spTail)
			{
				curr = *spHead;
				*(spHead--) = NULL;
				curr = curr->rchild;
			}
			else
				--spHead;
		}
	}while (spHead  != spTail);
}

void main()
{
	TreeNode *node = createPreBinTree();
	preTraverse(node);
	cout << endl;

}

最後更新：2017-04-02 06:51:50

  上一篇： 一些小算法

  下一篇： android2.2完全退出程序, 使用廣播機製