华为机试（根据广度优先遍历的结果生成二叉树，再进行遍历）
给定一个以顺序存储结构（按每一层从左到右顺序）存储整数值的完全二叉树序列(最多1000个整数)，请找出此完全二叉树的所有非叶子节点部分，然后采用后序遍历的方式将该树的非叶子节点输出。
只有一个节点的树，此节点是根节点，应该被认为是非叶子节点
此完全二叉树并非满二叉树，可能存在倒数第二层出现叶子节点，或者无右叶子的情况
后序遍历的顺序：左-右-根
输入描述：
一个通过空格分隔的整数序列字符串
输出描述：
非叶子部分树结构的后序遍历结果
示例1：
输入
1 2 3 4 5 6 7
输出
2 3 1
说明
找到非叶子部分树结构，然后采用后序遍历输出
#include<stdio.h>
#include<malloc.h>
const int max = 100;
typedef struct node
{
int value;
node*left;
node* right;
};
typedef struct stack
{
int top=-1;
node* nodeList;
};
void pushStack(stack *s,node n)
{
if (s->top >= max - 1)
return;
s->nodeList[++s->top] = n;
}
node* topStack(stack *s)
{
if (s->top < 0)
return NULL;
return &s->nodeList[s->top];
}
node* popStack(stack *s)
{
if (s->top < 0)
return NULL;
return &s->nodeList[s->top--];
}
typedef struct queue
{
stack input;
stack output;
};
void pushQueue(queue *q, node n)
{
pushStack(&q->input, n);
}
node *topQueue(queue *q)
{
if (topStack(&q->output) != NULL)
{
return topStack(&q->output);
}
while (topStack(&q->input)!=NULL)
{
pushStack(&q->output, *popStack(&q->input));
}
return topStack(&q->output);
}
node *popQueue(queue *q)
{
if (topStack(&q->output) != NULL)
{
return popStack(&q->output);
}
while (topStack(&q->input) != NULL)
{
pushStack(&q->output, *popStack(&q->input));
}
return popStack(&q->output);
}
void first(node *n)
{
if (n->value==-1)
return;
printf("%d ", n->value);
first(n->left);
first(n->right);
}
int main()
{
queue q;
q.input.nodeList = (node*)malloc(sizeof(node)*max);
q.output.nodeList = (node*)malloc(sizeof(node)*max);
node root;
root.left = (node*)malloc(sizeof(node));
root.right = (node*)malloc(sizeof(node));
root.value = 1;
int valueList[] = { 1, 2, 3, 4, 5, 6, 7 };
int index = 1;
pushQueue(&q, root);
while (topQueue(&q)!=NULL)
{
node *n= popQueue(&q);
if (index < 7)
{
n->left->value = valueList[index++];
n->left->left = (node*)malloc(sizeof(node));
n->left->right = (node*)malloc(sizeof(node));
pushQueue(&q, *n->left);
}
if (index < 7)
{
n->right->value = valueList[index++];
n->right->left = (node*)malloc(sizeof(node));
n->right->right = (node*)malloc(sizeof(node));
pushQueue(&q, *n->right);
}
if (index>7)
{
//set 尾节点标志位
n->left->value=-1;
n->right->value = -1;
}
if (index == 7)
{
index++;
}
}
//先序变里root 因为对有值的节点的left和right都赋值了，使用结尾的节点4 5 6 7的left right都不为NULL 在遍历的时候注意一下
first(&root);
}
