#include<stdio.h> 
#include<stdlib.h> 
#define MAXSIZE 100 
typedef int DATATYPE; 
int n, countLevel = 0; 
typedef struct BinTreeNode 
{ 
      DATATYPE data; 
      struct BinTreeNode* rChild; 
      struct BinTreeNode* lChild; 
}tree; 
tree* stack[100]; 
tree* CreateBinTree( DATATYPE* s, int i)//递归创建二叉树 
{ 
      if (i > n || s == 0) 
      { 
            return NULL; 
      } 
      else 
      { 
           tree* node = (tree*)malloc(sizeof(tree)); 
           node->data = s; 
           node->lChild = CreateBinTree( s, i * 2);//插入左孩子 
           node->rChild = CreateBinTree( s, i * 2 + 1);//插入右孩子 
           return node; 
      } 
}
//递归前序遍历二叉树 
void PreOrder(tree* root) 
{ 
      if (root != NULL) 
      { 
           printf("%d\t", root->data); 
           PreOrder(root->lChild);//一直遍历直到找到第一个空结点。 
           PreOrder(root->rChild);//遍历右孩子 
      } 
}
//非递归前序遍历二叉树 
void preOrder(tree* root) 
{ 
      int i = -1; 
      if (root != NULL) 
      { 
           stack[++i] = root;//只将非空的根节点入栈 
      } 

     while (root != NULL) 
     { 
            //前序遍历先遍历根结点，再遍历左子树，再遍历右子树，所以对于根结点，一找到就输出，然后右孩子、左孩子分别入栈。 
            root = stack; 
            printf("%d\t", root->data); 
            if (root->rChild != NULL) 
            { 
                   stack[++i] = root->rChild; 
            } 
            if (root->lChild != NULL) 
            { 
                   stack[++i] = root->lChild; 
            } 
            if (i == -1)//当栈空时结束 
            { 
                   return ; 
            } 
       } 
}
//非递归中序遍历二叉树 
void inorder(tree* root) 
{ 
      int i = -1,j; 
      for(;;) 
      { 
           while (root != NULL)//对左孩子入栈 
           { 
                  i++; 
                  stack = root; 
                  root = root->lChild; 
           } 
           if (i != -1)//栈非空 
           { 
                  root = stack;//root指向栈顶元素 
                  i--; 
                  printf("%d\t", root->data); 
                  root = root->rChild;//遍历栈顶元素，即root的右孩子 
           } 
           else 
           { 
                  return;//栈空结束 
           } 
      } 
}
//非递归后序遍历二叉树1 
void postOrder(tree* root) 
{ 
      int i = -1, j; 
      int a[100]; 
      for(;;) 
      { 
           while (root != NULL)//对左孩子入栈 
        { 
            stack[++i] = root; 
            a = 0;//设置此结点为没被访问过 
            root = root->lChild; 
        } 
        if (i == -1)//栈空结束 
        { 
            return; 
        } 
        else 
        { 
            root = stack; 
            if (a == 0)//针对没被访问过的结点，访问其右子树，并设置该结点为已访问过的结点 
            { 
                   root = root->rChild; 
                   a = 1; 
            } 
            else//打印已访问过的结点，并将该结点置为空结点，以防访问其父结点时会在将它再次入栈 
            { 
                   printf("%d\t", root->data); 
                   i--; 
                   root = NULL; 
            } 
        } 
    } 
}
//非递归后序遍历二叉树2
void postorderz2(BinNode * p)
{
    BinNode* s[10];
    int top = -1;
    while (1)
    {
        while (p != NULL)
        {
            s[++top] = p;
            p = p->lchild;
        }
        while (1)
        {
            if (s[top]->rchild != NULL)//[1]
            {
                p = s[top]->rchild;
                break;
            }
            while (top != -1)
            {
                //右孩子为空时可以直接打印，即是为当前子树的最又叶子。当s[top]->rchild==p时，p表示已被访问的结点，所以可以打印s[top]
                if (s[top]->rchild == NULL || s[top]->rchild == p)
                {
                    p = s[top--];
                    printf("%c\t", p->data);
                }
                else//否则，表示s[top]的右孩子没被访问过且s[top] 存在右孩子，所以要对右孩子入栈,返回[1]
                {
                    break;
                }
            }
            if (top == -1)
            {
                return ;
            }
        }
    }
}
//按层遍历二叉树 
void levelorder(tree* root) 
{ 
   int front = 0, rear = 0; 
   if (root != NULL) 
   { 
        rear++; 
        stack[rear] = root;//将根结点入队 
   } 
   while (front != rear)//队非空时，将队尾元素出队，并将它的左右子树入队。 
   { 
        front++; 
        root = stack[front]; 
        printf("%d\t", root->data); 
        if (root->lChild != NULL) 
        { 
               stack[++rear] = root->lChild; 
        } 
        if (root->rChild != NULL) 
        { 
               stack[++rear] = root->rChild; 
        } 
    } 
}
//先序计算二叉树的层 
void predeep(tree* root, int i) 
{ 
      if (root != NULL) 
      { 
           i++; 
           if (countLevel < i)//counLevel是全局变量，当当前的i>countLevel是，将i赋给countLevel，此时countLevel为当前的最大层数 
           { 
                  countLevel = i; 
           } 
           predeep(root->lChild, i); 
           predeep(root->rChild, i); 
      } 
}
//前序遍历查找 
tree* FindNode(tree* root, DATATYPE key) 
{ 
   tree* left, *right;
   if (root != NULL) 
   { 
     if (root->data == key) 
     { 
         return root; 
     } 
     else 
     { 
         left = FindNode(root->lChild, key); 
         if (left != NULL) 
         { 
             return left; 
         }
         right = FindNode(root->rChild, key); 
         if (right != NULL) 
         { 
          return right; 
         } 
      } 
      return NULL; 
   } 
   return NULL; 
}

int main() 
{ 
   int i, key; 
   DATATYPE s[MAXSIZE]; 
   scanf("%d", &n); 
   for (i = 1; i <= n; i++) 
   { 
        scanf("%d", &s); 
   } 
   tree* root = NULL; 
   root = CreateBinTree( s, 1); 
   PreOrder(root); 
   printf("前序\n");
   preOrder(root); 
   printf("前序\n"); 
   inorder(root); 
   printf("中序\n");
   postOrder(root); 
   printf("后序1\n");
   postorderz2(root);
   printf("后序2\n");
   levelorder(root); 
   printf("按层\n"); 
   predeep(root, 0); 
   printf("%d\n", countLevel);
   while (1) 
   { 
        scanf("%d", &key); 
        tree* aim = FindNode(root, key); 
        if (aim != NULL) 
        { 
               printf("%d\n", aim->data); 
        } 
        else 
        { 
               printf("Can't find it\n"); 
        } 
    } 
    return 0; 
}
/* 
9 
1 2 3 4 5 6 7 8 9 
*/