二叉树之前序遍历

一、结点结构
        在二叉树的链接存储中，通常采用的方法是：每个结点中设置三个域，即值域、左指针域和右指针域，其结点结构如下：

图1 二叉树结点结构

        其中，data表示值域，用于存储放入结点的数据元素，left和right分别表示左指针域和右指针域，用于分别存储左孩子和右孩子结点（即左右子树的根结点）的存储位置（即指针）。
        链接存储的指针类型和结点定义如下：
        typedef struct bnode
        {
            ElemType data;
            struct bnode *left, *right;
        }btree;
        其中，ElemType可以是任意数据类型如int、float或者char等，在算法中，规定其默认为int类型。

二、递归遍历
        前序遍历原理：按照先访问根节点，再访问左子树，最后访问右子树的次序访问二叉树中所有节点，且每个结点仅访问一次。其递归算法如下：
        void preorder(btree *p)
        {
            if (NULL != p)
            {
                printf("%d ", p->data)
                preorder(p->left);
                preorder(p->right);
            }
        }

三、非递归遍历
       void preorder(btree *b)
      {
            btree *stack[MAX_SIZE], *p;
            int top;
            if (NULL != b)
            {
                top = 1;                            // 根结点入栈
                stack[top] = b;                   
                while (top > 0)                   // 栈不为空时循环
                {
                    p = stack[top];                // 退栈并访问该节点
                    top--;
                    printf("%d ", p->data);
                    if (NULL != p->right)        // 右孩子入栈
                    {
                        top++;
                        stack[top] = p->right;
                    }
                    if (NULL != p->left)         // 左孩子入栈           
                    {
                        top++;
                        stack[top] = p->left;
                    }
                }
            }
      }