查找值为x的结点与层序遍历
查找值为x的结点
查找整棵树中的储存的值为x的结点首先需要遍历，然后判断哪个结点是我们要找的结点， 不过返回的时候需要进行判断，不然会出现这种情况：
找D的时候，从A的左子树开始找，找不到返回空，找到了返回该节点，但是返回该节点的时候回到的位置是上一个结点的位置，如果没有判断就会去下个树中去找，并且不会将该节点返回到我们需要的地方。
如果加一个判断，顺利的返回就好了。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->_data == x) { return root; } BTNode* x1 =BinaryTreeFind(root->_left, x);//找左子树 if (x1)//判断是否为空，空是找到了，非空是没找到 { return x1;//找到了就返回找到的结点，位置是上一层的找左子树的函数 } BTNode* y =BinaryTreeFind(root->_right , x); if (y) { return y; } return NULL; }
这里还可以进行修改值。
层序遍历
层序遍历是一层一层的进行访问：
从祖先结点开始，遇到空指针返回。
那么怎么才能把所有的都访问到呢？我们需要借助队列：
在队中的头结点出队的时候，会将左子树和右子树进行入队操作，如果左子树和右子树中有空指针将不会进行入队操作。
#include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef char BTDataType; typedef struct BinaryTreeNode { BTDataType _data; struct BinaryTreeNode* _left; struct BinaryTreeNode* _right; }BTNode; typedef BTNode* SD;//将队列中的储存的内容改成二叉树结点类型 typedef struct QListNode { struct QListNode* next; SD data; }QL; typedef struct Queue { QL* head;//头结点 QL* tail;//尾结点 int siz; }Qu; void QueueInit(Qu* q);//初始化 void QueuePush(Qu* q, SD x);//入队 void QueuePop(Qu* q);//出队 SD QueueFront(Qu* q);//获取队头元素 SD QueueBack(Qu* q);//获取队尾元素 int QueueSize(Qu* q);//获取队列中有效元素个数 bool QueueEmpty(Qu* q);//检测队列是否为空 void QueueDestroy(Qu* q);//销毁队列
#include "queue.h" void QueueInit(Qu* q)//初始化 { assert(q); q->head = q->tail = NULL; q->siz = 0; } void QueueDestroy(Qu* q)//销毁队列 { assert(q); QL* cur = q->head; while (cur) { QL* del = cur -> next; free(cur); cur = del; } q->head = q->tail = NULL; q->siz = 0; } void QueuePush(Qu* q, SD x)//入队 { assert(q); QL* w = (QL*)malloc(sizeof(Qu)); if (w == NULL) { perror("malloc tail"); exit(-1); } else { w->data = x; w->next = NULL; } if (q->head == NULL) { q->head = q->tail = w; } else { q->tail->next = w; q->tail = w; } q->siz++; } bool QueueEmpty(Qu* q)//判断 { assert(q); return q->head == NULL; } void QueuePop(Qu* q)//出队 { assert(q); assert(!QueueEmpty(q)); if (q->head == NULL)//防止tail成为野指针 { free(q->head); q->head = q->tail = NULL; } QL* cur = q->head; q->head = q->head->next; free(cur); cur = NULL; q->siz--; } SD QueueFront(Qu* q)//获取队头元素 { assert(q); assert(!QueueEmpty(q)); return q->head->data; } SD QueueBack(Qu* q)//获取队尾元素 { assert(q); assert(!QueueEmpty(q)); return q->tail->data; } int QueueSize(Qu* q)//获取队列中有效元素个数 { assert(q); return q->siz; }
#include "queue.h" void BinaryTreeLevelOrder(BTNode* root) { Qu q; QueueInit(&q);//初始化队列 if (root)//空指针不能入队 { QueuePush(&q, root);//将结点存入队列中 } while (!QueueEmpty(&q))//如果为空就不要进行入队和出队的操作了 { BTNode* Front = QueueFront(&q);//获取队头元素 printf("%c ", Front->_data);//进行打印 QueuePop(&q);//弹出队头元素 if (Front->_left)//判断左子树是不是空指针 QueuePush(&q, Front->_left); if (Front->_right)//判断右子树是不是空指针 QueuePush(&q, Front->_right); } printf("\n"); QueueDestroy(&q);//销毁队列 }
销毁二叉树与判断二叉树是否为完全二叉树
销毁二叉树
销毁树的逻辑也是遍历，然后从底部销毁。
void BinaryTreeDestory(BTNode* root) { if (root == NULL) { return;//找到底部返回上一层进行释放就可以了 } BinaryTreeDestory(root->_left);//这里就是先从左子树开始 BinaryTreeDestory(root->_right); free(root); }
判断是否为完全二叉树
想判断二叉树是否为一个完全二叉树，就用刚才说的层序遍历：
例：
层序遍历很好查看：
- 当遇到空指针的时候，这一层后面的结点必须都是空指针，
- 下面的一层也必须都是空指针。
向上面的这种肯定不是，至少要吧C的左子树换成空指针，或者是B和C的右子树不是空指针，但是他们右子树的右子树必须是空指针。
这样的话，和层序遍历没啥区别，但是也有，因为我们这里遇到空指针也要入队，不然无法判断下一层是不是空指针。
因为A出队B C才会入队，B C出队，他们的子树才能入队，D出队的时候，他的子树也如对了（红色的），这样看来如果E结点是个空结点也不用担心最后一层的NULL不在队中。
当D出队后，下一个访问的就是空指针， 这时候，后面的所有结点都必须是空指针才行，不是就说明是非完全二叉树。
int BinaryTreeComplete(BTNode* root) { Qu q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q))//还是正常的层序遍历操作 { BTNode* Front = QueueFront(&q); if (Front == NULL) { break;//这里如果空指针是对头，就跳出进行入队的操作 } QueuePop(&q); QueuePush(&q, Front->_left); QueuePush(&q, Front->_right); } while (!QueueEmpty(&q))//判断空指针 { BTNode* Front = QueueFront(&q); QueuePop(&q); if (Front != NULL)//如果队中遇到的不是空指针，那么就不是完全二叉树 { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
显然我创建的的并不是完全二叉树。
