二叉树链式结构

1.前置说明

我们手动构建一棵二叉树：

注意：上述代码并不是创建二叉树的方式

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的

2.二叉树的遍历

2.1前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础

其实可以这样理解：

前序遍历：根->左子树->右子树
中序遍历：左子树->根->右子树
后序遍历：左子树->右子树->根

以下面这个二叉树为例：

前序遍历：1->2->3->4->5->6
中序遍历：3->2->1->5->4->6
后序遍历：3->2->5->6->4->1

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树

NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历

遍历的实现需要用到递归

2.2前序遍历

代码实现是这样的：

2.3中序遍历

2.4后序遍历

2.5层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历

我们可以利用队列先进先出的特点来实现：

定义一个q队列
如果root不为空，则将root入队列
用front来保存队头数据，将队头数据pop，打印队头数据；然后遍历下一层：如果左孩子不为空，左孩子入队列；右孩子不为空，右孩子入队列；当队列不为空则继续遍历下一层，直到队列为空退出循环

关于这块的指针问题，我们画图解释一下

我们修改val也为BTNode*类型

分层打印

我们可以定义一个levelsize保存每一层的数据个数，控制一层一层打印

队列的size就是下一层的数据个数

效果是这样的

3.节点个数

3.1二叉树的节点个数

3.1叶子节点个数

4.求树的高度

如果为空返回0
不为空左子树和右子树高度更高的那个+1

5.求第k层的节点个数

如果为空返回0
如果不为空且k=1 返回1
如果不为空且k>1 返回左子树的k-1层+右子树的k-1层

5.查找值为x的节点

6.构建一棵链式二叉树

假设给一个前序遍历的数组，将其构建成一棵二叉树

7.判断完全二叉树

完全二叉树的节点都是连续的，所以不可能出现一个NULL节点的后面存在非空节点的情况，我们用层序遍历的思路，入队列的时候不管是不是NULL节点都入队列，出队列的时候如果遇到NULL节点，则停止出队列，判断后面是否还有非空节点，我们用while循环来控制，如果队列不为空则出队列，如果队头数据有不为空的情况，则返回false

8.销毁二叉树

销毁我们为了防止形成野指针，从下往上，从左往右，即后序遍历依次销毁

代码示例

Queue

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//创建
typedef struct BTNode* QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;
//把队列的头尾封装在一个结构体中

//初始化
void QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);

//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//销毁
void QDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{
	assert(pq);
	//创建newnode
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
//出队列
void QPop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;
	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
		//防止ptail成为野指针
	}
	pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}
//判空
bool QEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

TreeNode

TreeNode.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include "Queue.h"
//创建
typedef char BTDataType;
typedef struct BTNode
{
	BTDataType data;
	struct BTNode* left;
	struct BTNode* right;
}BTNode;

//BTNode* BuyNode(BTDataType x)
//{
//	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//	node->data = x;
//	node->left = NULL;
//	node->right = NULL;
//	return node;
//}
//构建二叉树
BTNode* BTCreate(BTDataType*a,int*pi)
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	if (root == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	root->data = a[(*pi)++];
	root->left = BTCreate(a,pi);
	root->right = BTCreate(a,pi);
	return root;
}
//先序遍历
void BTPrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%c ", root->data);
	BTPrevOrder(root->left);
	BTPrevOrder(root->right);
}
//中序遍历
void BTInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BTInOrder(root->left);
	printf("%c ", root->data);
	BTInOrder(root->right);
}
//后序遍历
void BTPostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	BTPostOrder(root->left);
	BTPostOrder(root->right);
	printf("%c ", root->data);
}
// 层序遍历
void BTLevelOrder(BTNode* root)
{
	Queue q;
	QInit(&q);
	if (root)
		QPush(&q, root);
	int levelsize = 1;
	while (!QEmpty(&q))
	{
		while (levelsize--)
		{
			BTNode* front = QFront(&q);
			QPop(&q);
			printf("%c ", front->data);
			if (front->left)
				QPush(&q, front->left);
			if (front->right)
				QPush(&q, front->right);
		}
		printf("\n");
		levelsize = QSize(&q);
	}
	printf("\n");
	QDestroy(&q);
}
//判断完全二叉树
bool BTComplete(BTNode* root)
{
	Queue q;
	QInit(&q);
	if (root)
		QPush(&q, root);
	int levelsize = 1;
	while (!QEmpty(&q))
	{
		BTNode* front = QFront(&q);
		QPop(&q);
		if (front == NULL)
			break;
		QPush(&q, front->left);
		QPush(&q, front->right);
	}
	while (!QEmpty(&q))
	{
		BTNode* front = QFront(&q);
		QPop(&q);
		if (front)
		{
			QDestroy(&q);
			return false;
		}
	}
	QDestroy(&q);
	return true;
}
//销毁
void BTDestroy(BTNode* root)
{
	if (root == NULL)
		return;
	BTDestroy(root->left);
	BTDestroy(root->right);
	free(root);
}
//二叉树结点个数
//static int size = 0;
int BTSize(BTNode* root)
{
	/*if (root == NULL)
	{
		return;
	}
	++size;
	BTSize(root->left);
	BTSize(root->right);
	return size;*/
	return root == NULL ? 0 : 
		BTSize(root->left) + 
		BTSize(root->right)+1;
}
//叶子节点个数
int BTLSize(BTNode* root)
{
	/*if (root == NULL)
	{
		return 0;
	}
	return root->left == NULL && root->right == NULL ? 1:
		BTLSize(root->left) + BTLSize(root->right);*/
	return (root == NULL ? 0 : 
		(root->left == NULL && root->right == NULL ? 1 :
		BTLSize(root->left) + BTLSize(root->right)));
}
//求树的高度
int BTHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int leftHeight = BTHeight(root->left);
	int rightHeight = BTHeight(root->right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//求第k层的节点个数
int BTLKSize(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTLKSize(root->left, k - 1) + BTLKSize(root->right, k - 1);
}
//查找值为x的节点
BTNode* BTFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* leftnode = BTFind(root->left, x);
	if (leftnode)
		return leftnode;
	BTNode* rightnode = BTFind(root->right, x);
	if (rightnode)
		return rightnode;
	return NULL;
}
int main()
{
	//char a[] = "ABD##E#H##CF##G##";
	char a[] = "ABC##D##EF##G##";
	int i = 0;
	BTNode* root = BTCreate(a,&i);
	BTPrevOrder(root);
	printf("\n");
	BTInOrder(root);
	printf("\n");
	BTPostOrder(root);
	printf("\n");
	int size1 = BTSize(root);
	printf("%d\n", size1);
	int size2 = BTSize(root);
	printf("%d\n", size2);
	int size3 = BTLSize(root);
	printf("%d\n", size3);
	int h = BTHeight(root);
	printf("%d\n", h);
	int s = BTLKSize(root, 3);
	printf("%d\n", s);

	BTLevelOrder(root);
	printf("%d\n", BTComplete(root));

	BTDestroy(root);
	root = NULL;
	return 0;
}