1.zigzagging on a tree(C语言实现)

• 7-1 zigzagging on a tree
• • 1. Question
  • 2. Solution
  • • • 2.1 递归建树
      • 2.2 双堆栈之字遍历
  • 3. Source code

Introduction:

​ Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences. And it is a simple standard routine to print the numbers in level-order. However, if you think the problem is too simple, then you are too naive. This time you are supposed to print the numbers in “zigzagging order” – that is, starting from the root, print the numbers level-by-level, alternating between left to right and right to left. For example, for the following tree you must output: 1 11 5 8 17 12 20 15.

Input Specification:

​ Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the inorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.

Output Specification:

​ For each test case, print the zigzagging sequence of the tree in a line. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

8
12 11 20 17 1 15 8 5
12 20 17 11 15 8 5 1

Sample Output:

1 11 5 8 17 12 20 15

理论出发点：一棵树可以由中序和前序或者中序和后序序列唯一确定。
具体操作(以后序为例)：

1. 由后序确定根节点(后序序列最后一个节点即为这棵树的根节点)
2. 由中序确定左右子树的前序和后序序列(中序序列根节点之前为左子树中序序列，根节点之后为右子树中序序列；再由子树序列节点数和后序序列可确定左右子树的后序序列)
3. 递归地重复1、2直到左右子树长度变为0

理论出发点：堆栈FILO特性
具体操作：

1. 创建两个堆栈S1、S2
2. 将根节点压入S1
3. S1依次出栈并访问（打印），同时将对应子节点按右左顺序压入S2，直到S1空栈
4. S2依次出栈并访问（打印），同时将对应子节点按左右顺序压入S1，直到S2空栈
5. 重复3、4直到S1和S2同时空栈

#include
#include
#include

#define MAX 100

typedef int element_type;
typedef struct tree_node *Tree;
struct tree_node{
    element_type item;
    Tree left;
    Tree right;
};
//Tree的链表节点定义

typedef struct stack *Stack;
struct stack{
    Tree Data[MAX];
    int top;
};
//Stack的顺序存储定义

Stack creat_stack(void);
bool Sis_empty(Stack S);
Tree pop(Stack S);
void push(Stack S, Tree x);

Tree build_tree(element_type inorder[], element_type postorder[], int n);
void traverse_level(Tree T);
void traverse_zigzagging(Tree T);

int main(void)
{
    int n;
    scanf("%d",&n);
    element_type inorder[n],postorder[n];

    for(int i=0;iitem=postorder[n-1];
    while(inorder[index++]!=postorder[n-1]);
    T->left=build_tree(inorder,postorder,index-1);
    T->right=build_tree(inorder+index,postorder+index-1,n-index);

    return T;
}

void traverse_zigzagging(Tree T)
{
    Stack S1=creat_stack();
    Stack S2=creat_stack();

    push(S1,T);
    while(Sis_empty(S1)==false || Sis_empty(S2)==false)
    {
        if(Sis_empty(S2)==true)
        {
            while(Sis_empty(S1)==false)
            {
                T=pop(S1);
                if(T->right){
                    push(S2,T->right);
                }
                if(T->left){
                    push(S2,T->left);
                }
                printf((Sis_empty(S1) && Sis_empty(S2))?"%d":"%d ",T->item);
            }

        }else if(Sis_empty(S1)==true){
            while(Sis_empty(S2)==false)
            {
                T=pop(S2);
                if(T->left){
                    push(S1,T->left);
                }
                if(T->right){
                    push(S1,T->right);
                }
                printf((Sis_empty(S1) && Sis_empty(S2))?"%d":"%d ",T->item);
            }        
        }
    }
}

Stack creat_stack(void)
{
    Stack S=(Stack)malloc(sizeof(struct stack));
    S->top=-1;
    return S;
}
bool Sis_empty(Stack S)
{
    return S->top==-1?true:false;
}
Tree pop(Stack S)
{
    return S->top==-1?NULL:S->Data[S->top--];
}
void push(Stack S, Tree x)
{
    S->Data[++S->top]=x;
}