二叉树之中序遍历

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

图1 二叉树结点结构

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

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

三、非递归遍历
        非递归中序遍历原理：根据中序遍历二叉树的递归定义，转换成非递归函数时采用一个栈保存返回的结点，先扫描根结点的所有左结点并入栈，出栈一个结点，访问之，然后扫描该结点的右结点并入栈再扫描该右结点的所有左结点并入栈，如此这般，直到栈为空为止。其非递归算法如下：     
        void preorder(btree *b)
        {
            btree *stack[MAX_SIZE], *p;
            int top = 0;
            p = b;
            do
            {
                while (NULL != p)                   // 扫描左结点
                {
                    top++;
                    stack[top] = p;              
                    p = p->left;
                }
                if (top > 0)
                {
                    p = stack[top];                // p所指结点为无左子树的结点或其左子树已遍历过了
                    top--;
                    printf("%d ", p->data);     // 访问结点
                    p = p->right;                   // 扫描右子树
                }
            } while ((NULL != p) || (0 != top))
      }