数据表示：
1 //二叉链表存储 2 struct BTNode3 {4 struct BTNode *LChild; // 指向左孩子指针5 ELEMENTTYPE data; // 结点数据6 struct BTNode *RChild; // 指向右孩子指针7 }; 前序遍历：
1 // 递归实现 2 void PreorderTraversal(BTNode *BT) 3 { 4 if(BT!=NULL) { 5 Print(BT->data); // 访问根结点 6 PreorderTraversal(BT->LChild); // 前序遍历左子树 7 PreorderTraversal(BT->RChild); // 前序遍历右子树 8 } 9 }10 11 // 非递归实现12 void PreorderTraversal(BTNode *BT)13 {14 InitStack(stack, treeDeepth); // 初始化元素为结点指针类型的栈stack，用以保存结点的指针15 BTNode *current = BT; // current指向但前要访问的结点，初始时指向根结点16 while(current != NULL || !EmptyStack(stack)) { /* current为空结点且栈空，遍历结束 */17 if(current != NULL) { /* 若current不是空结点 */18 Print(current->data); // 访问current指向的结点19 Push(stack, current); // 当前结点指针current压栈20 current = current->LChild; // 使current的左孩子成为当前结点21 } else { /* 若current指向的为空结点 */22 current = Pop(stack); // 弹出栈顶的结点指针赋给current23 current = current->RChild; // 使current的右孩子成为当前结点24 }25 }26 } 中序遍历：
1 // 递归实现 2 void InorderTraversal(BTNode *BT) 3 { 4 if(BT!=NULL) { 5 InorderTraversal(BT->LChild); // 中序遍历左子树 6 Print(BT->data); // 访问根结点 7 InorderTraversal(BT->RChild); // 中序遍历右子树 8 } 9 }10 11 // 非递归实现12 void InorderTraversal(BTNode *BT)13 {14 InitStack(stack, treeDeepth); // 初始化元素为结点指针类型的栈stack，用以保存结点的指针15 BTNode *current = BT; // current指向但前要访问的结点，初始时指向根结点16 while(current != NULL || !EmptyStack(stack)) { /* current为空结点且栈空，遍历结束 */17 if(current != NULL) { /* 若current不是空结点 */18 Push(stack, current); // 当前结点指针current压栈19 current = current->LChild; // 使current的左孩子成为当前结点20 } else { /* 若current指向的为空结点 */21 current = Pop(stack); // 弹出栈顶的结点指针赋给current22 Print(current->data); // 访问current指向的结点23 current = current->RChild; // 使current的右孩子成为当前结点24 }25 }26 } 后序遍历：
1 // 递归实现 2 void PostorderTraversal(BTNode *BT) 3 { 4 if(BT!=NULL) { 5 PostorderTraversal(BT->LChild); // 后序遍历左子树 6 PostorderTraversal(BT->RChild); // 后序遍历右子树 7 Print(BT->data); // 访问根结点 8 } 9 }10 11 // 非递归实现12 void PostorderTraversal(BTNode *BT)13 {14 InitStack(stack, treeDeepth); // 初始化元素为结点指针类型的栈stack，用以保存结点的指针15 BTNode *current = BT; // current指向但前要访问的结点，初始时指向根结点16 Push(stack, current); // 当前结点指针current压栈17 while(current->LChild != NULL) { /* 从当前结点出发，逐步找到二叉树左边结点并依次进栈 */18 current = current->LChild;19 Push(stack, current);20 }21 while(!EmptyStack(stack)) { /* 一直进行到栈空为止，整棵二叉树遍历完成 */22 current = Pop(stack); // 栈顶结点退栈作为当前结点23 if(current < 0) { /* 若当前结点指针标志为“负”，表示该结点的右子树已遍历完，应该访问该结点 */ 24 current = -current; /******* 对指针加正负号，OK，学习了，竟然这样子来标识 *******/25 Print(current->data);26 } else { /* 若当前结点标志为“正”，表示该结点的左子树已遍历完，应该遍历其右子树 */27 Push(stack, -current); // 对当前结点指针加左子树已遍历标志并入栈28 if(current->RChild != NULL) { // 若当前结点有右子树，以右孩子作为当前结点，从它出发做后序遍历29 current = current->RChild;30 Push(stack, current);31 while(current->LChild != NULL) {32 current = current->LChild;33 Push(stack, current);34 }35 }36 }37 }38 }39 40 /*41 * 非递归实现 双栈42 * 思路：43 * 按“左-右-根”顺序遍历二叉树的顺序与按“根-右-左”顺序遍历二叉树的顺序正好相反44 * 所以，将按“根-右-左”顺序遍历二叉树的结点依次压入postStack栈中，遍历完后再45 * 输出postStack栈中所有的元素结点所对应的值即是按“左-右-根”顺序遍历二叉树的顺序46 */47 void postorderTraversal(struct BTreeNode *root)48 {49 initStack(tempStack, STACKSIZE); // 初始化元素为结点类型指针的栈tempStack，用以保存刚访问过的结点，利于回溯50 initStack(postStack, BTREESIZE); // 初始化元素为结点类型指针的栈postStack，用以保存按“根-右-左”顺序依次访问的结点51 52 struct BTreeNode *currentNode = root; // currentNode指向当前要访问的结点，初始时指向根结点53 while(currentNode != NULL || !isEmpty(tempStack)) { /* 当currentNode为空结点其tempStack栈空，遍历结束 */54 if(currentNode != NULL) { // 若currentNode指向的不是空结点55 push(postStack, currentNode); // currentNode结点压入postStack栈中56 push(tempStack, currentNode); // currentNode结点压入tempStack栈中57 currentNode = currentNode->rightChild; // 使currentNode指向当前结点的右孩子结点58 } else { // 若currentNode不为空结点 59 currentNode = pop(tempStack); // 弹出tempStack栈顶结点指针并赋给currentNode指针60 currentNode = currentNode->LChild; // 是使currentNode指向当前结点的左孩子结点61 }62 }63 outStack(postStack);64 } 层序遍历：
1 /* 2 * 层序遍历二叉树 3 */ 4 void levelOrderTraversal(struct BTreeNode *root) 5 { 6 initQueue(queue, QUEUESIZE); // 初始化元素为二叉树结点指针类型的队列 7 if(root != NULL) // 若二叉树不为空，根结点指针入队 8 enQueue(queue, root); 9 10 struct BTreeNode currentNode = NULL;11 while(!isEmpty(queue)) { /* 直到队列为空，遍历结束 */12 currentNode = outQueue(queue); // 队头元素出列13 print(currentNode->data); // 访问当前结点信息14 if(currentNode->LChild != NULL) /* 若当前结点有左孩子，则将其入队 */15 enQueue(queue, currentNode->LChild);16 if(currentNode->rightChild != NULL) /* 若当前结点有右孩子，则将其入队 */17 enQueue(queue, currentNode->rightChild);18 }19 } 二叉树遍历方法的简单应用：
1 /* 2 * 前序遍历应用：输出二叉树 递归实现 3 */ 4 void outBTree(struct BTreeNode *root) 5 { 6 if(root != NULL) { // 若二叉树为空 7 print(root->data); // 输出根结点值 8 if(root->LChild != NULL || root->rightChild != NULL) { // 有左子树或右子树 9 print("("); // 输出左括号10 outBT(root->LChild); // 输出左子树11 print(","); // 输出左右子树的分隔符12 if(root->rightChild != NULL) // 若有右子树13 outBTree(root->rightChild); // 输出右子树 14 print(")"); // 输出右括号15 }16 }17 }18 19 /*20 * 前序遍历应用：查找二叉树中是否存在指定值 递归实现21 */22 bool findBTree(struct BTreeNode *root, ElementType item)23 {24 if(root == NULL) { // 二叉树为空，则返回false25 return false;26 } else {27 if(root->data == item) { // 若根结点为所找结点，返回true28 return true;29 } else {30 if(findBTree(root->LChild, item) == true) { // 递归查找当前结点的左子树，若找到，返回true31 return true;32 }33 if(findBTree(root->rightChild, item) == true) { // 递归查找当前结点的右子树，若找到，返回false34 return true;35 }36 return false; // 若左右子树都未找到，返回false37 }38 }39 }40 41 /*42 * 后序遍历应用：计算二叉树的深度 递归实现43 */44 int getBTreeDeepth(struct BTreeNode *root)45 { 46 if(root == NULL) { // 二叉树为空，返回深度为047 return 0;48 } else {49 int deepth_1 = getBTreeDeepth(root->LChild); // 递归求左子树的深度50 int deepth_2 = getBTreeDeepth(root->RChild); // 递归求右子树的深度51 return (deepth_1 > deepth_2) ? (deepth_1 + 1) : (deepth_2 + 1); // 求出树的深度并返回52 }53 }54 55 /*56 * 后序遍历应用：清空二叉树 递归实现57 */58 void clearBTree(struct BTreeNode *root)59 {60 /* 若二叉树为空树，则结束递归 */61 if(root != NULL) {62 clearBTree(root->LChild); // 递归删除根结点的左子树63 clearBTree(root->rightChild); // 递归删除根结点的右子树64 delete root; // 释放根结点65 root = NULL; // 将根结点指针置空66 }67 }
OK哒！