1 /**  2  * 二叉树的前序、中序、后序遍历的递归和非递归算法实现  3  **/  4   5 //二叉链表存储   6 struct BTNode  7 {  8     struct BTNode *LChild;    // 指向左孩子指针  9     ELEMENTTYPE    data;      // 结点数据 10     struct BTNode *RChild;    // 指向右孩子指针 11 }; 12  13 /** 14  * 前序遍历 15  **/ 16 // 递归实现 17 void PreorderTraversal(BTNode *BT) 18 { 19     if(BT!=NULL) { 20         Print(BT->data);                                // 访问根结点 21         PreorderTraversal(BT->LChild);                  // 前序遍历左子树 22         PreorderTraversal(BT->RChild);                  // 前序遍历右子树 23     } 24 } 25  26 // 非递归实现 27 void PreorderTraversal(BTNode *BT) 28 { 29     InitStack(stack, treeDeepth);                       // 初始化元素为结点指针类型的栈stack，用以保存结点的指针 30     BTNode *current = BT;                               // current指向但前要访问的结点，初始时指向根结点 31     while(current != NULL || !EmptyStack(stack)) {      /* current为空结点且栈空，遍历结束 */ 32         if(current != NULL) {                           /* 若current不是空结点 */ 33             Print(current->data);                       // 访问current指向的结点 34             Push(stack, current);                       // 当前结点指针current压栈 35             current = current->LChild;                  // 使current的左孩子成为当前结点 36         } else {                                        /* 若current指向的为空结点 */ 37             current = Pop(stack);                       // 弹出栈顶的结点指针赋给current 38             current = current->RChild;                  // 使current的右孩子成为当前结点 39         } 40     } 41 } 42  43 /** 44  * 中序遍历 45  **/ 46 // 递归实现 47 void InorderTraversal(BTNode *BT) 48 { 49     if(BT!=NULL) { 50         InorderTraversal(BT->LChild);                   // 中序遍历左子树 51         Print(BT->data);                                // 访问根结点 52         InorderTraversal(BT->RChild);                   // 中序遍历右子树 53     } 54 } 55  56 // 非递归实现 57 void InorderTraversal(BTNode *BT) 58 { 59     InitStack(stack, treeDeepth);                       // 初始化元素为结点指针类型的栈stack，用以保存结点的指针 60     BTNode *current = BT;                               // current指向但前要访问的结点，初始时指向根结点 61     while(current != NULL || !EmptyStack(stack)) {      /* current为空结点且栈空，遍历结束 */ 62         if(current != NULL) {                           /* 若current不是空结点 */ 63             Push(stack, current);                       // 当前结点指针current压栈 64             current = current->LChild;                  // 使current的左孩子成为当前结点 65         } else {                                        /* 若current指向的为空结点 */ 66             current = Pop(stack);                       // 弹出栈顶的结点指针赋给current 67             Print(current->data);                       // 访问current指向的结点 68             current = current->RChild;                  // 使current的右孩子成为当前结点 69         } 70     } 71 } 72  73 /** 74  * 后序遍历 75  **/ 76 // 递归实现 77 void PostorderTraversal(BTNode *BT) 78 { 79     if(BT!=NULL) { 80         PostorderTraversal(BT->LChild);                 // 后序遍历左子树 81         PostorderTraversal(BT->RChild);                 // 后序遍历右子树 82         Print(BT->data);                                // 访问根结点 83     } 84 } 85  86 // 非递归实现 87 void PostorderTraversal(BTNode *BT) 88 { 89     InitStack(stack, treeDeepth);                       // 初始化元素为结点指针类型的栈stack，用以保存结点的指针 90     BTNode *current = BT;                               // current指向但前要访问的结点，初始时指向根结点 91     Push(stack, current);                               // 当前结点指针current压栈 92     while(current->LChild != NULL) {                    /* 从当前结点出发，逐步找到二叉树左边结点并依次进栈 */ 93         current = current->LChild; 94         Push(stack, current); 95     } 96     while(!EmptyStack(stack)) {                         /* 一直进行到栈空为止，整棵二叉树遍历完成 */ 97         current = Pop(stack);                           // 栈顶结点退栈作为当前结点 98         if(current < 0) {                       /* 若当前结点指针标志为“负”，表示该结点的右子树已遍历完，应该访问该结点 */  99             current = -current;                 /******* 对指针加正负号，OK，学习了，竟然这样子来标识 *******/100             Print(current->data);101         } else {                                /* 若当前结点标志为“正”，表示该结点的左子树已遍历完，应该遍历其右子树 */102             Push(stack, -current);                      // 对当前结点指针加左子树已遍历标志并入栈103             if(current->RChild != NULL) {               // 若当前结点有右子树，以右孩子作为当前结点，从它出发做后序遍历104                 current = current->RChild;105                 Push(stack, current);106                 while(current->LChild != NULL) {107                     current = current->LChild;108                     Push(stack, current);109                 }110             }111         }112     }113 }