前序遍历:先访问根节点，再访问左子树，最后访问右子树。设置一个栈，出栈即为访问节点。先将根节点进栈，在栈不空时一直如下循环:出栈，访问，将其右孩子进栈，再将左孩子进栈。
中序遍历:先访问左子树，再访问根节点，最后访问右子树。设置一个栈，出栈即为访问节点。先将根节点的左节点全部进栈，然后出栈一个节点，访问。将该节点的右孩子节点进栈，再将右孩子节点的所有左节点全部进栈...如此这般直到栈空为止。
后序遍历:先访问左子树，再访问右子树，最后访问根节点。设置一个栈。先将根节点的左节点全部进栈。出栈一个节点，将该节点的右孩子进栈，再将右孩子的左节点全部进栈...当一个节点的左、右孩子都被访问过后再访问该节点，如此这般直到栈空为止。(判断某节点的右孩子是否被访问，需要单独设置一个指针跟踪刚刚访问的节点。在后序遍历中，某节点的右孩子节点一定刚好在该节点之前被访问)
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int Elemtype; typedef struct BinNode { Elemtype data; struct BinNode *left; struct BinNode *right; }BinNode,*BinTree; BinTree creatTree() { char c; BinTree T; scanf_s("%c", &c); if (c == '#') T =NULL; else { T = (BinTree)malloc(sizeof(BinNode)); T->data = c; T->left = creatTree(); T->right = creatTree(); } return T; } void PreOrder(BinTree T) { BinTree stack[MAXSIZE]; int top = -1; if(T) { top++; stack[top] = T; while (top != -1) { T = stack[top]; top--; printf("]", T->data); if (T->right) { top++; stack[top] = T->right; } if (T->left) { top++; stack[top] = T->left; } } } printf("\n"); } void InOrder(BinTree T) { BinTree stack[MAXSIZE]; int top = -1; if (T) { while (T || top > -1) { while (T) { top++; stack[top] = T; T = T->left; } if (top > -1) { T = stack[top]; printf("]", T->data); top--; T = T->right; } } } printf("\n"); } void PostOrder(BinTree T) { BinTree stack[MAXSIZE],BT; int top = -1; int sign; if (T) { do { while (T != NULL) { top++; stack[top] = T; T = T->left; } BT = NULL; sign = 1; while (sign == 1 && top > -1) { T = stack[top]; if (T->right == BT) //这里不能用NULL，否则会出现输出无限循环的情况 { printf("]", T->data); top--; BT = T; //标志该结点已访问过 } else { T = T->right; sign = 0; } } } while (top > -1); } printf("\n"); } void LevelOrder(BinTree T) { BinTree stack[MAXSIZE]; int front, rear; front = rear = -1; if (T) { rear++; stack[rear] = T; while (front != rear) { T = stack[front + 1]; printf("]", T->data); front++; if (T->left) { rear++; stack[rear] = T->left; } if (T->right) { rear++; stack[rear] = T->right; } } } printf("\n"); } int main() { BinTree T = NULL; T = creatTree(); PreOrder(T); InOrder(T); PostOrder(T); LevelOrder(T); system("pause"); return 0; }文章转载自 ( www.slyar.com )
