二叉树中序遍历
二叉树中序遍历的实现思想是：
- 访问当前节点的左子树
- 访问根节点
- 访问当前节点的右子树
图 1 二叉树
以上图 1 为例，中序遍历的过程如下：
- 访问该二叉树的根节点，找到 1
- 遍历节点 1 的左子树，找到节点 2
- 遍历节点 2 的左子树，找到节点 4
- 由于节点 4 无左孩子，因此找到节点 4，并遍历节点 4 的右子树
- 由于节点 4 无右子树，因此节点 2 的左子树遍历完成，访问节点 2
- 遍历节点 2 的右子树，找到节点 5
- 由于节点 5 无左子树，因此访问节点 5 ，又因为节点 5 没有右子树，因此节点 1 的左子树遍历完成，访问节点 1 ，并遍历节点 1 的右子树，找到节点 3
- 遍历节点 3 的左子树，找到节点 6
- 由于节点 6 无左子树，因此访问节点 6，又因为该节点无右子树，因此节点 3 的左子树遍历完成，开始访问节点 3 ，并遍历节点 3 的右子树，找到节点 7
- 由于节点 7 无左子树，因此访问节点 7，又因为该节点无右子树，因此节点 1 的右子树遍历完成，即整棵树遍历完成
因此，图 1 中二叉树采用中序遍历得到的序列为：
二叉树中序遍历代码实现
先谈一下递归实现！！！
#include <stdio.h>
#include <stdlib.h>typedef struct MyBiTNode{int data; // 数据域struct MyBiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode;BiTNode *CreateBiTree(BiTNode *T){// 结点 1 T = (BiTNode*)malloc(sizeof(BiTNode));T->data = 1;// 结点 2T->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->data = 2;// 结点 3T->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->data = 3;// 结点 4 T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->lchild->data = 4;T->lchild->lchild->lchild = NULL;T->lchild->lchild->rchild = NULL;// 结点 5T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->rchild->data = 5;T->lchild->rchild->lchild = NULL;T->lchild->rchild->rchild = NULL;// 结点 6T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->lchild->data = 6;T->rchild->lchild->lchild = NULL;T->rchild->lchild->rchild = NULL;// 结点 7T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->rchild->data = 7; T->rchild->rchild->lchild = NULL;T->rchild->rchild->rchild = NULL;return T;
}// 模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){printf("%d ", elem->data);
}// 中序遍历
void INOrderTraverse(BiTNode *T){if(T){INOrderTraverse(T->lchild); // 遍历左孩子displayElem(T); // 调用操作结点数据的函数方法INOrderTraverse(T->rchild); // 遍历右孩子}// 如果结点为空，返回上一层return;
} int main() {BiTNode *Tree = NULL; // 结构体指针指向空 Tree = CreateBiTree(Tree); // 传入结构体指针 printf("%d\n",Tree->rchild->lchild->data); // 6INOrderTraverse(Tree);return 0;
}再谈一下非递归实现！！！
#include <stdio.h>
#include <stdlib.h>int top = -1; // top变量表示栈顶元素所在位置typedef struct MyBiTNode{int data; // 数据域struct MyBiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode;BiTNode *CreateBiTree(BiTNode *T){// 结点 1 T = (BiTNode*)malloc(sizeof(BiTNode));T->data = 1;// 结点 2T->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->data = 2;// 结点 3T->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->data = 3;// 结点 4 T->lchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->lchild->data = 4;T->lchild->lchild->lchild = NULL;T->lchild->lchild->rchild = NULL;// 结点 5T->lchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->lchild->rchild->data = 5;T->lchild->rchild->lchild = NULL;T->lchild->rchild->rchild = NULL;// 结点 6T->rchild->lchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->lchild->data = 6;T->rchild->lchild->lchild = NULL;T->rchild->lchild->rchild = NULL;// 结点 7T->rchild->rchild = (BiTNode*)malloc(sizeof(BiTNode));T->rchild->rchild->data = 7; T->rchild->rchild->lchild = NULL;T->rchild->rchild->rchild = NULL;return T;
}// 模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){printf("%d ", elem->data);
}// 先序和中序遍历使用的进栈函数
void push(BiTNode **a, BiTNode *elem){a[++top] = elem;
}// 弹栈函数
void pop(){if(top == -1){return;}top--;
}// 拿到栈顶元素
BiTNode *getTop(BiTNode **a){return a[top];
}// 中序遍历非递归算法
void InOrderTraverse_1(BiTNode *Tree){BiTNode *a[20]; BiTNode *p; push(a, Tree); while(top != -1){ while((p = getTop(a)) && p){ push(a, p->lchild);}pop();if(top != -1){p = getTop(a);pop();displayElem(p);push(a, p->rchild);}}
}// 中序遍历实现的另一种方法
void InOrderTraverse_2(BiTNode *Tree){BiTNode *a[20];BiTNode *p;p = Tree;while(p || top!=-1){if(p){push(a, p);p = p->lchild;}else{ // 如果 p为 NULL，表明左子树遍历完成，需要遍历上一层结点的右子树 p = getTop(a);pop();displayElem(p);p = p->rchild;}}
}int main() {BiTNode *Tree = NULL; // 结构体指针指向空 Tree = CreateBiTree(Tree); // 传入结构体指针 printf("%d\n",Tree->rchild->lchild->data); // 6InOrderTraverse_2(Tree);InOrderTraverse_2(Tree);return 0;
}
