手机智能建网站,南宁360网,无备案网站微信,rdm响应式网站开发前言#xff1a;二叉树的实现方式多种多样#xff0c;有数组实现满二叉树#xff0c;有链表实现完全二叉树#xff0c;今天我们就用队列来实现二叉树。 创建二叉树#xff1a;
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTre… 前言二叉树的实现方式多种多样有数组实现满二叉树有链表实现完全二叉树今天我们就用队列来实现二叉树。 创建二叉树
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}TreeNode;层序遍历
void LevelOrder(TreeNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1;while (!QueueEmpty(q)){// 一层一层出while (levelSize--){TreeNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);levelSize QueueSize(q);}printf(\n);QueueDestroy(q);
}我们的队列是用来存放二叉树节点的所以我们的目的是将节点一层一层的遍历出来所以我们的第一层是根节点我们把它放入队列出队列的时候就要带它的左子树和右子树节点进入队列那么我们怎么知道每层的节点数呢我们定义一个levelSize初始值为1。 我们的levelSize是每层的节点个数我们的节点个数因为在队列中所以我们的个数就等于队列的数据个数即levelSize QueueSize(q)我们通过循环让节点一层一层的出队列打印出来就达到了我们的目的。整个过程如下图所示 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1;while (!QueueEmpty(q)){TreeNode* front QueueFront(q);QueuePop(q);if (front NULL)break;QueuePush(q, front-left);QueuePush(q, front-right);}// 前面遇到空以后后面还有非空就不是完全二叉树while (!QueueEmpty(q)){TreeNode* front QueueFront(q);QueuePop(q);if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
}我们这里同样按照节点的顺序给它入队列和出队列我们的levelSize控制每一层的数据我们的根节点出队列就将它的左子树和右子树带入队列如果中间有一个子树为空那么就退出循环但是我们后面如果还有不为空的节点也就是不连续的话那么就不是完全二叉树。 我们拿到2的左子树3后出队列再拿2的右子树2的右子树为空所以就结束循环我们在到队列里面取队列首元素再出队列队列的元素不为空说明二叉树不连续所以该树就不是完全二叉树反之就是完全二叉树。 如果对大家有帮助的话就支持一下吧感谢大家的支持
