数据结构 树的遍历（中序非递归遍历）

//树的遍历--非递归遍历

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"LinkStack.h"

/*
步骤1：结点的所有路径情况
如果结点有左子树，该结点入栈；
如果结点没有左子树，访问该结点；
分析3：路径所有情况
如果结点有右子树，重复步骤1；
如果结点没有右子树（结点访问完毕），回退，让栈顶元素出栈，访问栈顶元素，并访问右子树，重复步骤1
如果栈为空，表示遍历结束。
*/

//定义二叉树结构体
typedef struct _TreeNode{
    char data;
    struct _TreeNode * leftchild;
    struct _TreeNode * rightchild;
}TreeNode, *TreeNodePointer;

TreeNodePointer GoLeft(TreeNodePointer root, LinkStack * stack){
    if (root == NULL || stack==NULL)
    {
        printf("参数不可以为空！
");
        return NULL;
    }
    while (root->leftchild){
        //入栈
        LinkStack_Push(stack, root);
        root = root->leftchild;
    }
    return root;
}

//树的非递归遍历
void TreeErgodic(TreeNodePointer root){
    if (root==NULL)
    {
        return;
    }
    //1.创建栈
    LinkStack * stack = LinkStack_Create();
    if (stack == NULL)
    {
        printf("创建栈失败
");
        return;
    }
    /*
        如果结点有左子树，该结点入栈；
        如果结点没有左子树，访问该结点；
    */
    TreeNodePointer t = GoLeft(root, stack);
    /*
       此时t不可能为NULL，因为root不为NULL
    */
    printf("%c", t->data);
    while (t){
        //如果结点有右子树，重复步骤1；
        if (t->rightchild!=NULL)
        {
            t = GoLeft(t->rightchild, stack);
            printf("%c", t->data);
        }
        //如果结点没有右子树（结点访问完毕），回退，让栈顶元素出栈，访问栈顶元素，并访问右子树，重复步骤1
        else if (LinkStack_Size(stack)>0){
            t = (TreeNodePointer)LinkStack_Pop(stack);
            printf("%c", t->data);
        }
        //如果栈为空，表示遍历结束。
        else{
            t = NULL;
        }
    }
    //销毁栈
    LinkStack_Destroy(&stack);
}

void Test(){
    //定义结构体对象
    TreeNodePointer t1 = NULL, t2 = NULL, t3 = NULL, t4 = NULL, t5 = NULL,t6=NULL,t7=NULL,t8=NULL,t9=NULL;
    t1 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t1 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t1, 0, sizeof(TreeNode));
    t2 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t2 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t2, 0, sizeof(TreeNode));
    t3 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t3 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t3, 0, sizeof(TreeNode));
    t4 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t4 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t4, 0, sizeof(TreeNode));
    t5 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t5 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t5, 0, sizeof(TreeNode));
    t6 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t6 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t6, 0, sizeof(TreeNode));
    t7 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t7 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t7, 0, sizeof(TreeNode));
    t8 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t8 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t8, 0, sizeof(TreeNode));
    t9 = (TreeNodePointer)malloc(sizeof(TreeNode));
    if (t9 == NULL)
    {
        printf("分配内存失败！");
        goto END;
    }
    //初始化数据
    memset(t9, 0, sizeof(TreeNode));
    //填充数据域
    t1->data = 'A';
    t2->data = 'B';
    t3->data = 'C';
    t4->data = 'D';
    t5->data = 'E';
    t6->data = 'F';
    t7->data = 'G';
    t8->data = 'H';
    t9->data = 'I';

    //建立树之间的关系
    t1->leftchild = t2;
    t1->rightchild = t5;

    t2->leftchild = NULL;
    t2->rightchild = t3;

    t3->leftchild = t4;
    t3->rightchild = NULL;

    // t5是t4的左孩子
    t4->leftchild = NULL;
    t4->rightchild = NULL;

    //t5没有孩子节点
    t5->leftchild = NULL;
    t5->rightchild = t6;

    t6->leftchild = t7;
    t6->rightchild = NULL;

    t7->leftchild = t8;
    t7->rightchild = t9;

    t8->leftchild = NULL;
    t8->rightchild = NULL;

    t9->leftchild = NULL;
    t9->rightchild = NULL;

    //非递归遍历
    TreeErgodic(t1);
    printf("
");
END:
    if (t1 != NULL)
    {
        free(t1);
        t1 = NULL;
    }
    if (t2 != NULL)
    {
        free(t2);
        t2 = NULL;
    }
    if (t3 != NULL)
    {
        free(t3);
        t3 = NULL;
    }
    if (t4 != NULL)
    {
        free(t4);
        t4 = NULL;
    }
    if (t5 != NULL)
    {
        free(t5);
        t5 = NULL;
    }
}

void main(){
    Test();
    system("pause");
}