杭州 高端网站定制,泸州网站建设多少钱,手机微网站建设,郑州新闻发布会目录
链式二叉树示意图编辑
何为层序遍历
手搓一个链式二叉树
实现层序遍历链式二叉树 链式二叉树示意图 何为层序遍历
和前中后序遍历不同#xff0c;前中后序遍历链式二叉树需要利用递归才能遍历 而层序遍历是非递归的形式#xff0c;如上图#xff1a;层序遍历的…目录
链式二叉树示意图编辑
何为层序遍历
手搓一个链式二叉树
实现层序遍历链式二叉树 链式二叉树示意图 何为层序遍历
和前中后序遍历不同前中后序遍历链式二叉树需要利用递归才能遍历 而层序遍历是非递归的形式如上图层序遍历的结果124356 手搓一个链式二叉树
代码演示以上图为例
// 数据类型
typedef int BTDataType;// 二叉树节点的结构
typedef struct BinaryTreeNode
{BTDataType data; //每个节点的数据struct BinaryTreeNode* left; //指向左子树的指针struct BinaryTreeNode* right; //指向右子树的指针
}BTNode;// 申请新节点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));// 判断是否申请成功if (newnode NULL){perror(malloc fail);return NULL;}// 初始化newnode-data x;newnode-left NULL;newnode-right NULL;return newnode;
}BTNode* CreatBinaryTree()
{BTNode* n1 BuyNode(1);assert(n1);BTNode* n2 BuyNode(2);assert(n2);BTNode* n3 BuyNode(3);assert(n3);BTNode* n4 BuyNode(4);assert(n4);BTNode* n5 BuyNode(5);assert(n5);BTNode* n6 BuyNode(6);assert(n6);n1-left n2;n1-right n4;n2-left n3;n4-left n5;n4-right n6;return n1;
} 实现层序遍历链式二叉树
实现思路
利用队列的先进先出的性质实现层序遍历链式二叉树 如上图所示先将 1 节点入队列再将 1 节点出队列在 1 节点出队列的时候把 2、4 节点带入队列2 节点再出队列2 节点出队列的时候把 3 节点带入队列然后就是 4 节点出队列同样出队列的时候将 5、6 节点带入队列最后再依次出队列所有数据出完队列后根据出队列的顺序就是层序遍历的顺序
实现前要先构建一个简易队列以及队列的基本函数
// 数据类型
typedef BTNode* QDataType;// 链式队列每个节点的结构
typedef struct QueueNode
{struct QueueNode* next; //指向下一个节点的指针QDataType data; //当前节点的数据
}QNode;// 链式队列的结构
typedef struct Queue
{QNode* phead; //指向队头节点的指针QNode* ptail; //指向队尾节点的指针int size; //队列的总数据个数
}Queue;// 初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}// 数据入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);// 申请新节点QNode* newnode (QNode*)malloc(sizeof(QNode));// 判断是否申请成功if (newnode NULL){perror(malloc fail);return;}// 初始化新节点newnode-data x;newnode-next NULL;if (pq-phead NULL) //当队列中没有数据的情况{// 双重判断更加保险assert(pq-ptail NULL);// 头尾都指向新节点即可pq-phead newnode;pq-ptail newnode;}else //当队列已有数据的情况{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}// 数据出队列
void QueuePop(Queue* pq)
{assert(pq);// 当队列中没有数据的情况if (pq-phead NULL){perror(pq-phead);return;}if (pq-phead-next NULL) //当队列中只有一个数据的情况{free(pq-phead);pq-phead NULL;pq-ptail NULL;}else //当队列中有多个数据的情况{QNode* next pq-phead-next;free(pq-phead);pq-phead next;}pq-size--;
}// 访问队头数据
QDataType QueueFront(Queue* pq)
{assert(pq);// 当队列中没有数据的情况if (pq-phead NULL){perror(pq-phead);return -1;}return pq-phead-data;
}// 判断队列是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return (pq-phead NULL) (pq-ptail NULL);
}// 释放队列
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur ! NULL){QNode* next cur-next;free(cur);cur next;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}
在定义队列数据时需要定义链式二叉树节点的指针这样才能找到二叉树节点的左右子树
代码实现
void LevelOrder(BTNode* root)
{// 定义队列Queue q;// 初始化队列QueueInit(q);// 先将二叉树的根节点的指针入队列if (root ! NULL)QueuePush(q, root);while (!QueueEmpty(q)){// 访问队头数据BTNode* front QueueFront(q);printf(%d , front-data);// 队头数据出队列QueuePop(q);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);
}
代码解析
当队列为空时链式二叉树的层序遍历就实现了 但最开始队列没有数据所以要先将指向根节点的指针存放入队列 且存放节点指针是为了方便查找左右子树 然后在利用 while 循环只要队列不为空就循环下去 先访问队头的数据队头的数据就是链式二叉树节点的指针 所以使用 BTNode* front 来接收再利用 printf 函数打印指针所指向节点中的数据 再把队头数据出队列并且把出队列那个节点的左右子树存放入队列 注意为空时就不要放入队列所以每次放入队列前要判断是否为空 直到队列为空时也就是不满足 while 循环时层序遍历就实现了
此代码的关键是利用 BTNode* front 接收每次要出队列的节点指针这样就方便查找当前节点的左右子树并且利用 BTNode* front 接收从而替代了递归逻辑
代码验证
