长春行业网站,重庆智能建站模板,做网站月度总结,网站需要写哪些内容第六部分、数据结构树#xff0c;树存储结构详解 数据结构的树存储结构#xff0c;常用于存储逻辑关系为 一对多 的数据。
树存储结构中#xff0c;最常用的还是二叉树#xff0c;本章就二叉树的存储结构、二叉树的前序、中序、后序以及层次遍历、线索二叉树、…第六部分、数据结构树树存储结构详解 数据结构的树存储结构常用于存储逻辑关系为 一对多 的数据。
树存储结构中最常用的还是二叉树本章就二叉树的存储结构、二叉树的前序、中序、后序以及层次遍历、线索二叉树、哈夫曼树等详细介绍二叉树。
树是数据结构中的重点同时更是难点没有捷径需要初学者静下心死扣各个知识点。
五、由浅入深讲二叉树4种遍历算法的由来
遍历二叉树可以算作是对树存储结构做的最多的操作既是重点也是难点。本节将从初学者的角度给大家分析一下 4 种遍历二叉树算法的由来。
1、遍历二叉树的算法 图 1 二叉树示意图
图 1 是一棵二叉树对于初学者而言遍历这棵二叉树无非有以下两种方式。
1层次遍历
前面讲过树是有层次的拿图 1 来说该二叉树的层次为 3。通过对树中各层的节点从左到右依次遍历即可实现对正棵二叉树的遍历此种方式称为层次遍历。 比如对图 1 中二叉树进行层次遍历遍历过程如图 2 所示 图 2 层次遍历二叉树示意图
2普通遍历
其实还有一种更普通的遍历二叉树的思想即按照 从上到下从左到右 的顺序遍历整棵二叉树。 还拿图 1 中的二叉树举例其遍历过程如图 3 所示 图 3 普通方式遍历二叉树
以上仅是从初学者的角度对遍历二叉树的过程进行了分析。接下来我们从程序员的角度再对以上两种遍历方式进行剖析。 这里我们要建立一个共识即成功遍历二叉树的标志是能够成功访问到二叉树中所有的节点。 2、二叉树遍历算法再剖析
首先观察图 2 中的层次遍历整个遍历过程只经过各个节点一次因此在层次遍历过程每经过一个节点都必须立刻访问该节点否则错失良机后续无法再对其访问。 若对图 1 中二叉树进行层次遍历则访问树中节点的次序为 1 2 3 4 5 6 7 而普通遍历方式则不同通过观察图 3 可以看到整个遍历二叉树的过程中每个节点都被经过了 3 次虽然叶子节点看似只经过了 2 次但实际上可以看做是 3 次。以图 3 中的节点 2 为例如图 4 所示它被经过了 3 次。 图 4 遍历节点 2 的过程示意图
因此在编程实现时我们可以设定真正访问各个节点的时机换句话说我们既可以在第一次经过各节点时就执行访问程序也可以在第二次经过各节点时访问甚至可以在最后一次经过各节点时访问。 这也就引出了以下 3 种遍历二叉树的算法
先序遍历每遇到一个节点先访问然后再遍历其左右子树对应图 4 中的 ①中序遍历第一次经过时不访问等遍历完左子树之后再访问然后遍历右子树对应图 4 中的 ②后序遍历第一次和第二次经过时都不访问等遍历完该节点的左右子树之后最后访问该节点对应图 4 中的 ③
以图 1 中的二叉树为例其先序遍历算法访问节点的先后次序为 1 2 4 5 3 6 7 中序遍历算法访问节点的次序为 4 2 5 1 6 3 7 后序遍历访问节点的次序为 4 5 2 6 7 3 1 以上就是二叉树 4 种遍历算法的由来其各个算法的具体实现过程其代码实现后续章节会详解介绍。 六、二叉树先序遍历递归与非递归及C语言实现
二叉树先序遍历的实现思想是
访问根节点访问当前节点的左子树若当前节点无左子树则访问当前节点的右子树 图 1 二叉树
以图 1 为例采用先序遍历的思想遍历该二叉树的过程为
访问该二叉树的根节点找到 1访问节点 1 的左子树找到节点 2访问节点 2 的左子树找到节点 4由于访问节点 4 左子树失败且也没有右子树因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树因此现在开始遍历即访问节点 5由于节点 5 无左右子树因此节点 5 遍历完成并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1 并开始遍历该节点的右子树即访问节点 3访问节点 3 左子树找到节点 6由于节点 6 无左右子树因此节点 6 遍历完成回到节点 3 并遍历其右子树找到节点 7节点 7 无左右子树因此以节点 3 为根节点的子树遍历完成同时回归节点 1。由于节点 1 的左右子树全部遍历完成因此整个二叉树遍历完成
因此图 1 中二叉树采用先序遍历得到的序列为 1 2 4 5 3 6 7 1、递归实现
二叉树的先序遍历采用的是递归的思想因此可以递归实现其 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)-data1; (*T)-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-rchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-data2; (*T)-lchild-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-rchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-rchild-data5; (*T)-lchild-rchild-lchildNULL; (*T)-lchild-rchild-rchildNULL; (*T)-rchild-data3; (*T)-rchild-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-rchild-lchild-data6; (*T)-rchild-lchild-lchildNULL; (*T)-rchild-lchild-rchildNULL; (*T)-rchild-rchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-rchild-rchild-data7; (*T)-rchild-rchild-lchildNULL; (*T)-rchild-rchild-rchildNULL; (*T)-lchild-lchild-data4; (*T)-lchild-lchild-lchildNULL; (*T)-lchild-lchild-rchildNULL; } //模拟操作结点元素的函数输出结点本身的数值 void displayElem(BiTNode* elem){ printf(%d ,elem-data); } //先序遍历 void PreOrderTraverse(BiTree T){ if (T) { displayElem(T);//调用操作结点数据的函数方法 PreOrderTraverse(T-lchild);//访问该结点的左孩子 PreOrderTraverse(T-rchild);//访问该结点的右孩子 } //如果结点为空返回上一层 return; } int main() { BiTree Tree; CreateBiTree(Tree); printf(先序遍历: \n); PreOrderTraverse(Tree); } 运行结果 先序遍历: 1 2 4 5 3 6 7 2、非递归实现
而递归的底层实现依靠的是栈存储结构因此二叉树的先序遍历既可以直接采用递归思想实现也可以使用栈的存储结构模拟递归的思想实现其 C 语言实现代码为 #include stdio.h #include string.h #define TElemType int int top-1;//top变量时刻表示栈顶元素所在位置 //构造结点的结构体 typedef struct BiTNode{ TElemType data;//数据域 struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; //初始化树的函数 void CreateBiTree(BiTree *T){ *T(BiTNode*)malloc(sizeof(BiTNode)); (*T)-data1; (*T)-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-rchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-data2; (*T)-lchild-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-rchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-lchild-rchild-data5; (*T)-lchild-rchild-lchildNULL; (*T)-lchild-rchild-rchildNULL; (*T)-rchild-data3; (*T)-rchild-lchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-rchild-lchild-data6; (*T)-rchild-lchild-lchildNULL; (*T)-rchild-lchild-rchildNULL; (*T)-rchild-rchild(BiTNode*)malloc(sizeof(BiTNode)); (*T)-rchild-rchild-data7; (*T)-rchild-rchild-lchildNULL; (*T)-rchild-rchild-rchildNULL; (*T)-lchild-lchild-data4; (*T)-lchild-lchild-lchildNULL; (*T)-lchild-lchild-rchildNULL; } //前序遍历使用的进栈函数 void push(BiTNode** a,BiTNode* elem){ a[top]elem; } //弹栈函数 void pop( ){ if (top-1) { return ; } top--; } //模拟操作结点元素的函数输出结点本身的数值 void displayElem(BiTNode* elem){ printf(%d ,elem-data); } //拿到栈顶元素 BiTNode* getTop(BiTNode**a){ return a[top]; } //先序遍历非递归算法 void PreOrderTraverse(BiTree Tree){ BiTNode* a[20];//定义一个顺序栈 BiTNode * p;//临时指针 push(a, Tree);//根结点进栈 while (top!-1) { pgetTop(a);//取栈顶元素 pop();//弹栈 while (p) { displayElem(p);//调用结点的操作函数 //如果该结点有右孩子右孩子进栈 if (p-rchild) { push(a,p-rchild); } pp-lchild;//一直指向根结点最后一个左孩子 } } } int main(){ BiTree Tree; CreateBiTree(Tree); printf(先序遍历: \n); PreOrderTraverse(Tree); } 运行结果 先序遍历: 1 2 4 5 3 6 7
