层序遍历
层序遍历指的是对二叉树进行一层一层的遍历,每一层分别遍历,这里借助队列进行遍历,基本思路把根放到队列中,当某一个根要出队列时,就令该根的左子树和右子树进队列,这样就能实现一层一层遍历,画法如下:
代码实现相较于前面来说简单一些,但需要引入队列的,关于队列的介绍:
下面展示要使用的队列的相关函数实现
// queue.h
typedef struct BinaryTreeNode* QDataType;
typedef struct QNode
{
QDataType data;
struct QNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
// queue.c
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)
{
pq->phead = pq->ptail = NULL;
pq->size = 0;
free(pq);
}
QNode* BuyQnode(QDataType x)
{
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
return NULL;
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QNode* newnode = BuyQnode(x);
if (pq->ptail == NULL)
{
assert(pq->phead == NULL);
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;
pq->ptail = newnode;
}
pq->size++;
}
bool QueueEmpty(Queue* pq)
{
if (pq->size == 0)
{
return true;
}
return false;
}
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->phead->next == NULL)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
QNode* newhead = pq->phead->next;
free(pq->phead);
pq->phead = newhead;
}
pq->size--;
}
QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
assert(pq);
return pq->ptail->data;
}
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
那么借助队列我们来实现刚才的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
Queue 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");
//BinaryTreeDestory(&q);
}
二叉树的销毁
在知道了遍历的多种途径后,二叉树的销毁就很简单了,在确定代码如何实现前,先思考问题:应该选用哪种遍历来进行二叉树的销毁?
结果是很明显的,选用后序遍历是最方便的,原因在于销毁是需要进行节点的释放的,如果使用前序或者中序遍历,那么在遍历的过程中根节点会被先销毁,那么找左子树或者右子树就带来了不便(可以定义一个变量保存位置),因此最好用后序遍历,把子树都销毁了最后销毁根
void BinaryTreeDestory(BTNode* root)
{
if (root == NULL)
{
return;
}
BinaryTreeDestory(root->left);
BinaryTreeDestory(root->right);
free(root);
}
二叉树节点个数
二叉树节点个数也是转换成子树来解决,如果为NULL就返回0,其他情况返回左右相加再加上节点本身
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
二叉树叶子节点的个数
叶子节点个数求解和上述方法相似,也是找最小的子树,但不同的地方是,叶子节点找到的条件是叶子作为根,它的左右子树都为空,符合这样的就是叶子节点,那么根据这个想法求得代码不难得到:
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
int leftleave = BinaryTreeSize(root->left);
int rightleave = BinaryTreeSize(root->right);
return leftleave + rightleave;
}
二叉树查找值为x的节点
这个相对较麻烦一点,先上展开图和代码
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* ret1 = BinaryTreeFind(root->left, x);
if (ret1)
return ret1;
BTNode* ret2 = BinaryTreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
这里的关键动作就是判断ret1和ret2是否为空,如果是,则说明找到正确的值,那么就会一路被送出函数,相反会一直返回NULL,因此就不必担心送出其他元素的情况
二叉树是否为完全二叉树
这个思路也较为复杂,首先,需要解决的问题是用什么思路,基本思路是一个一个看,如果在某一个节点已经为空的前提下,它后面的节点还不为空,那么就说明这个不是完全二叉树
因此这个思路是不是和层序遍历很像呢?我们借助这样的思路继续写下去
当队列不为空就继续入队列出队列进行层序遍历,当遇到空就跳出,跳出循环后此时队列并不为空,继续出队列,如果发现某个元素不为空,那么就证明这并不是完全二叉树
代码实现如下:
int BinaryTreeComplete(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
QueuePush(&q,front->left);
QueuePush(&q,front->right);
}
while (!QueueEmpty(&q))
{
BTNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
BinaryTreeDestory(&q);
return 0;
}
}
BinaryTreeDestory(&q);
return 1;
}
至此,二叉树的基本功能实现就都结束了,很明显,二叉树的实现并不容易,它不仅需要对递归有一定深度的认识,还需要你对队列有足够的理解,才能解决层序遍历和判断完全二叉树
这需要进行更多的练习,也为后面更复杂的树打基础和铺垫