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