教育改变生活

标题: 【数据结构】二叉树中序遍历的递归实现 [打印本页]

作者: wander 时间: 2023-9-18 21:26
标题: 【数据结构】二叉树中序遍历的递归实现
二叉树中序遍历的实现思想是：

访问当前节点的左子树；
访问根节点；
访问当前节点的右子树；

图 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 中二叉树采用中序遍历得到的序列为：

4 2 5 1 6 3 7

递归实现二叉树的中序遍历采用的是递归的思想，因此可以递归实现，其 C 语言实现代码为：
#include <stdio.h>#include <string.h>#define TElemType int//构造结点的结构体typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;//初始化树的函数void CreateBiTree(BiTree *T){ *T=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->data=1; (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->data=2; (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->lchild->rchild->data=5; (*T)->lchild->rchild->lchild=NULL; (*T)->lchild->rchild->rchild=NULL; (*T)->rchild->data=3; (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->lchild->data=6; (*T)->rchild->lchild->lchild=NULL; (*T)->rchild->lchild->rchild=NULL; (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode)); (*T)->rchild->rchild->data=7; (*T)->rchild->rchild->lchild=NULL; (*T)->rchild->rchild->rchild=NULL; (*T)->lchild->lchild->data=4; (*T)->lchild->lchild->lchild=NULL; (*T)->lchild->lchild->rchild=NULL;}//模拟操作结点元素的函数，输出结点本身的数值void displayElem(BiTNode* elem){ printf("%d ",elem->data);}//中序遍历void INOrderTraverse(BiTree T){ if (T) { INOrderTraverse(T->lchild);//遍历左孩子 displayElem(T);//调用操作结点数据的函数方法 INOrderTraverse(T->rchild);//遍历右孩子 } //如果结点为空，返回上一层 return;}int main() { BiTree Tree; CreateBiTree(&Tree); printf("中序遍历算法: \n"); INOrderTraverse(Tree);}

欢迎光临教育改变生活 (http://bbs.goldoar.com/)