1. 二叉树非递归根据先序序列建立
比较简单的是二叉树
递归的创建方法
而非递归创建想起来有点难度,本质上是模拟函数栈的操作,所以要用到栈这一数据结构。
C++用到了STL里的栈,所以不用自己定义,而C语言需要自己定义
栈容器
,我用的是我之前写的栈容器稍加修改
2. C++代码
#include <iostream>
#include <stack>
#include <string>
using namespace std;
//二叉树节点
class node
{
public:
node* left;//左孩子
node* right;//右孩子
char data;//数据
node()
{
left = NULL;
right = NULL;
}
};
node* root;
/*
根据先序序列,非递归创建二叉树
大致思路就是利用栈模拟函数栈的过程
treeStr为先序序列的二叉树,#代表空
*/
void preCreate(node* &root,string treeStr)
{
stack<node*> ns;
node** now;
if (treeStr[0] != '#')
{
root = new node();
root->data = treeStr[0];
now = &root->left;
}
//遍历每个字符
for (int i = 1; i < treeStr.length(); i++)
{
//如果不为#,则新建一个节点,然后将当前节点调整为左孩子
if (treeStr[i] != '#')
{
*now = new node();
(*now)->data = treeStr[i];
ns.push(*now);
now = &(*now)->left;
}
//如果为#,则将当前节点调整为右孩子,并从堆栈里弹出此节点
else
{
if (!ns.empty())
{
now = &ns.top()->right;
ns.pop();
}
}
}
}
//先序遍历
void preorder(node* &root)
{
if (root == NULL)return;
cout << root->data;
preorder(root->left);
preorder(root->right);
}
int main()
{
string treeStr;
cin >> treeStr;
preCreate(root, treeStr);
preorder(root);
return 0;
}
3.C代码
#include <malloc.h>
#include <string.h>
#include <stdio.h>
char postex[200] = { '\0' };//后缀表达式
int counter = 0;
//二叉树的定义
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
}Tree, *mBTree;
typedef struct
{
mBTree* base;//指向栈底,也就是第一个元素
mBTree* top;//指向栈顶元素的下一个
int stackSize;//当前栈的空间大小,就是可以放多少个定义的数据类型
}Stack;
//初始化栈
int InitStack(Stack* stack)
{
//给栈分配空间
stack->base = (mBTree*)malloc(100 * sizeof(mBTree));
if (stack->base == NULL)
return 0;
stack->top = stack->base;
stack->stackSize = 100;
return 1;
}
//是否为空
int StackEmpty(Stack* stack)
{
if (stack->base == stack->top || stack->top == NULL)
return 1;
else
return 0;
}
//取栈顶元素
mBTree StackGetTop(Stack* stack)
{
//因为top指向的顶上元素的下一个,所以要-1
if (!StackEmpty(stack))
return *(stack->top - 1);
else
return NULL;
}
//压栈
mBTree StackPush(Stack* stack, mBTree element)
{
*stack->top = element;
stack->top++;
return 0;
}
//弹出
mBTree StackPop(Stack* stack)
{
if (StackEmpty(stack))
return NULL;
stack->top--;
return (stack->top);
}
//非递归二叉树遍历
void PreCreateBTree(mBTree *node,char* treeArray)
{
//ab##c##
Stack ms;
mBTree *n = node;
InitStack(&ms);
for(int i=0;i<strlen(treeArray);i++)
{
if(treeArray[i]!='#')
{
*n = (mBTree)malloc(sizeof(Tree));
(*n)->data = treeArray[i];
(*n)->left = NULL;
(*n)->right = NULL;
StackPush(&ms, (*n));
n = &((*n)->left);
}
else
{
n = &(StackGetTop(&ms)->right);
if(!StackEmpty(&ms))
StackPop(&ms);
}
}
}
//前序遍历
void pre(mBTree p)
{
if (p == NULL)
return;
else
{
printf("%c ", p->data);
pre(p->left);
pre(p->right);
}
}
//中序遍历
void in(mBTree p)
{
if (p == NULL)
return;
else
{
in(p->left);
printf("%c ", p->data);
in(p->right);
}
}
//后序遍历
void post(mBTree p)
{
if (p == NULL)
return;
else
{
post(p->left);
post(p->right);
printf("%c ", p->data);
}
}
int main()
{
char temp[100];
scanf("%s",temp);
mBTree bt;
PreCreateBTree(&bt,temp);
printf("前序遍历");
pre(bt);
printf("\n中序遍历");
in(bt);
printf("\n后序遍历");
post(bt);
return 0;
}
版权声明:本文为wayway0554原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。