带你图解二叉树的多种递归遍历（建议收藏！！） |
您所在的位置：网站首页 › 二叉树的深度算法实现递归 › 带你图解二叉树的多种递归遍历（建议收藏！！） |
带你图解二叉树的多种递归遍历（建议收藏！！）
|
文章目录
二叉树的构建结点类型的定义构建二叉树之间的关系
深度优先遍历前序遍历代码实现图解递归（由于图片大小问题，建议用手机客户端查看，以下图解也是）
中序遍历代码实现图解递归
后序遍历代码实现图解递归
广度优先遍历层序遍历代码实现
二叉树的构建
为了实现二叉树的遍历，我们要先构建一个二叉树，这里就先简单构建一个。 结点类型的定义既然是链式二叉树，那必须得有自己的结点类型，以下是链式二叉树结点类型的定义 typedef char BTDataType; typedef struct BinaryNode { BTDataType x; struct BinaryNode* left; struct BinaryNode* right; }BT; 构建二叉树之间的关系 BT* BuyNode(BTDataType x) { BT* new = (BT*)malloc(sizeof(BT)); if (new == NULL) { printf("malloc failed\n"); exit(-1); } new->x = x; new->left = NULL; new->right = NULL; return new; } void BinaryCreat() { BT* n1 = BuyNode('A'); BT* n2 = BuyNode('B'); BT* n3 = BuyNode('C'); BT* n4 = BuyNode('D'); BT* n5 = BuyNode('E'); BT* n6 = BuyNode('F'); n1->left = n2; n1->right = n3; n2->left = n4; n3->left = n5; n3->right = n6; }构建完之后的二叉树是这个样子的： 二叉树的深度优先遍历有以下三种 前序遍历前序遍历，又叫先根遍历。 遍历顺序：根 -> 左子树 -> 右子树 代码实现 void BinaryPrev(BT* n1) { if (n1==NULL) { printf("NULL "); return ; } printf("%c ", n1->x); BinaryPrev(n1->left); BinaryPrev(n1->right); }很多小伙伴可能会觉得：哇！这么少的代码就可以解决了吗？对，就是这么几行，这也就是递归遍历的强大之处。但是这之间的递归过程是很复杂的。 图解递归（由于图片大小问题，建议用手机客户端查看，以下图解也是）
中序遍历，又叫中根遍历。 遍历顺序：左子树 -> 根 -> 右子树 代码实现 void MiddleOrder(BT* n1) { if (n1 == NULL) { printf("NULL "); return; } MiddleOrder(n1->left); printf("%c ", n1->x); MiddleOrder(n1->right); }这个也是同样的简单，只要按着它的顺序写就行了，但其中的过程很复杂。 图解递归
后序遍历，又叫后根遍历。 遍历顺序：左子树 -> 右子树 -> 根 代码实现 void AfterOrder(BT* n1) { if (n1 == NULL) { printf("NULL "); return; } AfterOrder(n1->left); AfterOrder(n1->right); printf("%c ", n1->x); }这个同样也是只要按着顺序写就可以了，递归起来很复杂。 图解递归
层序遍历，自上而下，从左往右逐层访问树的结点的过程就是层序遍历。
思路（借助一个队列）： 1.先把根入队列，然后开始从队头出数据。 2.出队头的数据，把它的左孩子和右孩子依次从队尾入队列（NULL不入队列）。 3.重复进行步骤2，直到队列为空为止。 代码实现在实现过程中要用到队列，具体队列的实现这儿就不说了，博主之前的博客中有相关的文章。 void BinaryLevelOrder(BT* n1) { Queue q; QueueInit(&q); if (n1!=NULL) { QueuePush(&q, n1); } while (!QueueEmpty(&q)) { BT* front = QueueTop(&q); QueuePop(&q); printf("%c ", front->x); // 不把NULL打印出来 //if (front->left!=NULL) //{ // QueuePush(&q, front->left); //} //if (front->right != NULL) //{ // QueuePush(&q, front->right); //} if (front->left != NULL) { QueuePush(&q, front->left); } else { printf("NULL "); } if (front->right != NULL) { QueuePush(&q, front->right); } else { printf("NULL "); } } QueueDestory(&q); }
|
【本文地址】
今日新闻 |
推荐新闻 |