合肥网站开发招聘,做网站属于什么科目,万网网站发布,wordpress匿名投稿个人主页:Lei宝啊
愿所有美好如期而遇 目录
二叉树层序遍历#xff1a;
判断完全二叉树#xff1a; 二叉树层序遍历#xff1a; 层序遍历就是一层一层#xff0c;从上到下遍历#xff0c;上图遍历结果为#xff1a;4 2 7 1 3 6 9 思路#xff1a;
通过队列来实现层序…个人主页:Lei宝啊
愿所有美好如期而遇 目录
二叉树层序遍历
判断完全二叉树 二叉树层序遍历 层序遍历就是一层一层从上到下遍历上图遍历结果为4 2 7 1 3 6 9 思路
通过队列来实现层序遍历让父节点带孩子节点。将父节点入队列当其孩子节点不为空时入队列将父节点出队列依次类推。
代码
树的结构
typedef struct BT_Tree
{char data;struct BT_Tree* left;struct BT_Tree* right;
}BT_Tree; 队列结构
typedef struct BT_Tree* DataType;
typedef struct Queue
{DataType data;struct Queue *next;
}Queue;typedef struct Q
{Queue* head;Queue* tail;int size;
}Q;
层序实现
void Sequence(BT_Tree* node)
{if (node NULL){printf(NULL\n);return;}Q queue;Init(queue);QueuePush(queue, node);while (!Empty(queue)){BT_Tree* front GetQueueFrontNum(queue);printf(%d , front-data);if (front-left)QueuePush(queue, front-left);if (front-right)QueuePush(queue, front-right);QueuePop(queue);}}
图解 判断完全二叉树
思路
这里同层序遍历的思路非常相似但是不同的地方在于这里孩子节点为空我们仍要将其入队列最后我们检查队列若队列空后仍有非空的值则不是完全二叉树。
代码
bool JudgeTreeComplete(BT_Tree* node)
{if (node NULL)return true;Q queue;Init(queue);QueuePush(queue, node);while (!Empty(queue)){BT_Tree* front GetQueueFrontNum(queue);if (front NULL)break;QueuePush(queue, front-left);QueuePush(queue, front-right);QueuePop(queue);}while (!Empty(queue)){BT_Tree* front GetQueueFrontNum(queue);if (front ! NULL){Destroy(queue);return false;}QueuePop(queue);}Destroy(queue);return true;}
图解
