从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

⑴访问结点本身（N），

⑵遍历该结点的左子树（L），

⑶遍历该结点的右子树（R）。

以上三种操作有六种执行次序：

NLR、LNR、LRN、NRL、RNL、RLN。

遍历命名

根据访问结点操作发生位置命名：

① NLR：前序遍历(Preorder Traversal 亦称（先序遍历））

——访问根结点的操作发生在遍历其左右子树之前。

② LNR：中序遍历(Inorder Traversal)

——访问根结点的操作发生在遍历其左右子树之中（间）。

讯享网

③ LRN：后序遍历(Postorder Traversal)

——访问根结点的操作发生在遍历其左右子树之后。

注意：

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

前序：        A                B   D   G        C  E  F

中序：         D G       B                A               E  C  F

后序：         G D       B         E F  C                   A

#include <iostream> #include <stdio.h> #include <unordered_map> #include<stack> using namespace std; typedef struct treeNode { char data; struct treeNode* Lchild; struct treeNode* Rchild; }TREE,*LPTREE; LPTREE creatNode(char data) { LPTREE newNode = (LPTREE)malloc(sizeof(TREE)); newNode->data = data; newNode->Lchild = NULL; newNode->Rchild = NULL; return newNode; } // 没有规律的树 void insertNode(LPTREE parentNode, LPTREE Lchild, LPTREE Rchild) { parentNode->Lchild = Lchild; parentNode->Rchild = Rchild; } // 打印当前节点中的元素 void printCurNodeData(LPTREE curData) { printf("%c\t", curData->data); } //递归法 //先序：根左右 void preOrder(LPTREE root) { if (root != NULL) { printCurNodeData(root); preOrder(root->Lchild); preOrder(root->Rchild); } } //中序：左根右 void midOrder(LPTREE root) { if (root != NULL) { midOrder(root->Lchild); printCurNodeData(root); midOrder(root->Rchild); } } //后序：左右根 void LastOrder(LPTREE root) { if (root != NULL) { LastOrder(root->Lchild); LastOrder(root->Rchild); printCurNodeData(root); } } int main() { // 创建过程比较死板 LPTREE A = creatNode('A'); LPTREE B = creatNode('B'); LPTREE C = creatNode('C'); LPTREE D = creatNode('D'); LPTREE E = creatNode('E'); LPTREE F = creatNode('F'); LPTREE G = creatNode('G'); insertNode(A, B, C); insertNode(B, D, NULL); insertNode(D, NULL, G); insertNode(C, E, F); printf("先序遍历： \n"); preOrder(A); printf("\n"); printf("中序遍历： \n"); midOrder(A); printf("\n"); printf("后序遍历： \n"); LastOrder(A); return 0; }

讯享网// 非递归方式 void preOderBystack(LPTREE root) { if (root == NULL) return; //准备栈 //LPTREE stack[10]; //存储每次打印节点的位置 struct treeNode* stack[10]; int stackTop = -1; //栈顶标记 LPTREE pMove = root; while (stackTop != -1 || pMove) { //把当前的节点打印 while (pMove) { printf("%c \t", pMove->data); //把走过的节点入栈 stack[++stackTop] = pMove; pMove = pMove->Lchild; } // 无路可走 if (stackTop != -1) { pMove = stack[stackTop]; // 获取栈顶元素 stackTop--; pMove = pMove->Rchild; } } }

// 非递归方式 中序 // 1.定义一个指针移动到最左边，把走过的地方入栈 // 2.无路的时候，出栈，打印当前节点中的元素 void midOderBystack(LPTREE root) { if (root == NULL) return; //准备栈 //LPTREE stack[10]; //存储每次打印节点的位置 struct treeNode* stack[10]; int stackTop = -1; //栈顶标记 LPTREE pMove = root; while (stackTop != -1 || pMove) { //把当前的节点打印 while (pMove) { //printf("%c \t", pMove->data); //把走过的节点入栈 stack[++stackTop] = pMove; pMove = pMove->Lchild; } // 无路可走 if (stackTop != -1) { pMove = stack[stackTop]; // 获取栈顶元素 printf("%c \t", pMove->data); stackTop--; pMove = pMove->Rchild; } } }

讯享网// 后序， 左右根 void lastOderBystack(LPTREE root) { if (root == NULL) return; //准备栈 //LPTREE stack[10]; //存储每次打印节点的位置 struct treeNode* stack[10]; int stackTop = -1; //栈顶标记 struct treeNode* pMove = root; struct treeNode* PLastVisit = NULL; //访问标记 while (pMove) { //printf("%c \t", pMove->data); //把走过的节点入栈 stack[++stackTop] = pMove; pMove = pMove->Lchild; } // 左右根 while (stackTop != -1) { // 无路可走 if (stackTop != -1) { pMove = stack[stackTop--]; // 获取栈顶元素 // 判断左右元素是不是被访问 if (pMove->Rchild == NULL || pMove->Rchild == PLastVisit) { // 如果被访问就打印当前节点的数据 printf("%c \t", pMove->data); PLastVisit = pMove; //保存当前节点做下一次判断，改变标记的位置 } else { // 右边没有被访问 stack[++stackTop] = pMove; pMove = pMove->Rchild; while (pMove) { stack[++stackTop] = pMove; pMove = pMove->Lchild; } } } } }