本章将讲解:
二叉树的概念以及各种接口实现
注:这里我们不会像之前数据结构那样去学习二叉树的增删查改,二叉树不是一个线性结构,并不适合用来储存数据,也就是增删查改并不适合它,这里我们主要是在它本身的性质上拓展
二叉树是一棵度不大于二的树,可能有左子树和右子树,也可能为空树
用链表来表示一棵二叉树,即用链来指示元素的逻辑关系
链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址
链式结构又分为二叉链和三叉链,当前我们所讲的是二叉链,当学到高阶数据结构如红黑树等会用到三叉链
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;//数据
struct BinaryTreeNode* left;//左子节点地址
struct BinaryTreeNode* right;//右子节点地址
}BTNode;
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
//二叉树的深度
int BinaryTreeDepth(BTNode* root);
注:这里我们主要学习二叉链表
二叉链表具有数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址
typedef char BTDataType;//数据类型
typedef struct BinaryTreeNode
{
BTDataType data;//数据
struct BinaryTreeNode* left;//左子节点地址
struct BinaryTreeNode* right;//右子节点地址
}BTNode;
注:因为二叉树结构的特点(子树的根结点有且只有一个前驱,可以有最多两个后继)–是递归定义的,所以接下来对二叉树的多种操作需要依靠递归,可以快速解决
在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作
由于对二叉树结构掌握还不够深入,为了降低学习成本,这里手动快速创建一棵简单的二叉树,快速进入二叉树操作学习,检验操作的正确性(等深入了解后再来学习二叉树真正的创建方式)
注:#代表NULL,即空树
//开辟节点
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->data = x;
node->left = node->right = NULL;
return node;
}
BTNode* CreatBinaryTree()
{
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}
二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次
注:访问结点所做的操作依赖于具体的应用问题,遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础
二叉树的遍历有前序/中序/后序的递归结构遍历:
注意:
// 二叉树前序遍历(根左右)
void BinaryTreePrevOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
BinaryTreePrevOrder(root->left);//前序递归调用
BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历(左根右)
void BinaryTreeInOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreeInOrder(root->left);//中序递归调用
printf("%c ", root->data);
BinaryTreeInOrder(root->right);
}
注:递归过程示图可以自己动手画解哦
// 二叉树后序遍历(左右根)
void BinaryTreePostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
BinaryTreePostOrder(root->left);//后序递归调用
BinaryTreePostOrder(root->right);
printf("%c ", root->data);
}
注:递归过程示图可以自己动手画解哦
除了前中后序遍历,还有层序遍历 设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点 以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历
注:对与非内置类型我们需要进行前置声明,否则编译器会当做不认识该类型并报错
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
if (root == NULL)
return;
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
struct BinaryTreeNode* front = QueueFront(&q);//保存节点地址
printf("%c ", front->data);
QueuePop(&q);//出队列
if (front->left)//带入孩子节点
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
QueueDestroy(&q);
}
int main()
{
BTNode* root = CreatBinaryTree();
BinaryTreePrevOrder(root);
printf("\n");
BinaryTreeInOrder(root);
printf("\n");
BinaryTreePrevOrder(root);
printf("\n");
BinaryTreeLevelOrder(root);
printf("\n");
BinaryTreeDestory(&root);
return 0;
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
assert(root);
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
struct BinaryTreeNode* front = QueueFront(&q);//保存节点地址
QueuePop(&q);//出队列
if (front == NULL)//出队列遇到空指针,直接退出循环
break;
else//不是空指针才能带入孩子节点,否则访问空指针报错
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
//遇到空节点,如果剩下的都是NULL则为完全二叉树
//否则为不完全二叉树
while (!QueueEmpty(&q))
{
if (QueueFront(&q))
{
QueueDestroy(&q);//返回前先销毁
return 0;//0表示假
}
QueuePop(&q);
}
QueueDestroy(&q);//返回前先销毁
return 1;//非0表示真
}
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)//root本身为地址,传入二级指针才能修改root
{
if (root == NULL)//空树
return;
BinaryTreeDestory(&(*root)->left);//递归释放节点
BinaryTreeDestory(&(*root)->right);
free(*root);
*root = NULL;//释放并且置空
}
注:画递归图是一个理解递归操作很好的方式
二叉树节点个数==当前根节点+左右子树节点个数
注:如果对递归思想有问题的话,可以画递归展开图以便于理解,以下接口实现都同理
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)//空树不计数
return 0;
return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;//递归计数
}
叶子结点个数==左右子树叶子结点个数(当前节点不为叶子结点的话)
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)//空树
return 0;
if (root->left == NULL && root->right == NULL)//不是空树且无左右子树为叶子结点
return 1;
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);//不是叶子结点则继续递归
}
第k层节点==左右子树第k层结点个数(当前节点不为第k层的话)
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)//k用来控制递归次数
{
assert(k >= 1);//断言k一定大于0
if (root == NULL)//空树
return 0;
if (k == 1)//为所层数
return 1;
return BinaryTreeLevelKSize(root->left,k-1) + BinaryTreeLevelKSize(root->right,k-1);//不是则递归
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
BTNode* left = BinaryTreeFind(root->left, x);//依次在左右子树中查找
if (left != NULL)//找到了
return left;
BTNode* right = BinaryTreeFind(root->right, x);
if (right != NULL)
return right;
return NULL;
//return BinaryTreeFind(root->right, x);
}
当前层数加上左右子树的最大层数为二叉树的深度
//二叉树的深度
int BinaryTreeDepth(BTNode* root)
{
if (root == NULL)
return 0;
int left = BinaryTreeDepth(root->left);//查找左右子树深度并比较
int right = BinaryTreeDepth(root->right);
return left > right ? left + 1 : right + 1;
}
BTNode* CreatBinaryTree()
{
BTNode* nodeA = BuyNode('A');
BTNode* nodeB = BuyNode('B');
BTNode* nodeC = BuyNode('C');
BTNode* nodeD = BuyNode('D');
BTNode* nodeE = BuyNode('E');
BTNode* nodeF = BuyNode('F');
nodeA->left = nodeB;
nodeA->right = nodeC;
nodeB->left = nodeD;
nodeC->left = nodeE;
nodeC->right = nodeF;
return nodeA;
}
int main()
{
BTNode* root = CreatBinaryTree();
printf("TreeSize:%d\n", BinaryTreeSize(root));
printf("TreeLeafSize:%d\n", BinaryTreeLeafSize(root));
printf("TreeLevelKSize:%d\n", BinaryTreeLevelKSize(root, 3));
printf("BinaryTreeFind:%p\n", BinaryTreeFind(root, 'F'));
printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root));
printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));
BinaryTreeDestory(root);
root = NULL;
return 0;
}