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;
}