二叉树的广度优先遍历和题目

二叉树广度优先遍历利用队列 。

typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
typedef BTNode* QDataType;// 链式结构：表示队列 
typedef struct QueueNode 
{ struct QueueNode* next; QDataType data; 
}QueueNode;
// 队列的结构 两个指针分别记录链表的头和尾
typedef struct Queue 
{ QueueNode* head; QueueNode* tail; 
}Queue;
// 广度优先遍历 1.先把根入队列 2.出队头的数据,把他的下一层入进去
// 特点:借助队列的先进先出性质,上一层出的时候带入下一层 队列的代码参考前面的博客
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while(!QueueEmpty(&q)){BTNode* front = QueueFront(&q); QueuePop(&q);printf("%d ",front->left);if(front->left)QueuePush(&q, front->left);if(front->right)QueuePush(&q, front->right);}QueueDestory(&q);
}
// 判断二叉树是否为完全二叉树 完全二叉树按层序走,节点是连续的,当出到NULL之后后面全是NULL就是完全二叉树,
// 如果后面有非空,那么就不是,说明节点层序走,非空节点不连续
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);if(root)QueuePush(&q, root);while(!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if(front == NULL){break;}QueuePush(root->left);QueuePush(root->right)l}while(!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if(front)return false;}QueueDestory(&q);return true;
}
// 创建节点
BTNode* CreateTreeNode (BTDataType x)
{BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));n1->data = x;n1->left = NULL;n1->right = NULL:return node;
}
int main()
{// 手动连接上图中的树BTNode* A = CreateTreeNode('A');BTNode* B = CreateTreeNode('B');BTNode* C = CreateTreeNode('C');BTNode* D = CreateTreeNode('D');BTNode* E = CreateTreeNode('E');BTNode* F = CreateTreeNode('F');A->left = B;A->right = C;B->left = D;C->left = E;c->right = F;// 二级做法BinaryTreeDestory(&A);// 一级做法BinaryTreeDestory(A);A = NULL;
}

题目
单值二叉树

二叉树的前序遍历：用C语言做题，需要创建数组，首先确定数组大小，遍历一遍得到个数，然后用子函数进行递归，不然用主函数递归每次都需要创建数组的操作。对于i需要传地址，因为当递归返回之后，不传地址的情况下，i会倒退到之前没有++的情况，导致给数组放值会混乱

相同的树：都同时走到空的 要返回真。如果有一个为空一个不为空则返回假。如果两个值不相同返回假。这三个条件都是终止条件。值如果相同不用管相当于是往下走的进行条件。