华为机试（根据广度优先遍历的结果生成二叉树，再进行遍历）

给定一个以顺序存储结构（按每一层从左到右顺序）存储整数值的完全二叉树序列(最多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);

}