链式结构二叉树(递归暴力美学)
链式结构二叉树(递归暴力美学)
1. 链式结构二叉树
完成了顺序结构二叉树的代码实现，可以知道其底层结构是类似顺序表的结构； 因此，链式结构的二叉树类似于链表结构。
二叉树的结构一般由指数据域和左右指针域这三个域组成。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data; //当前结点数据域
struct BinaryTreeNode* left; //指向当前结点左孩⼦
struct BinaryTreeNode* right; //指向当前结点右孩⼦
}BTNode;1.1 二叉树创建
由于二叉树的代码实现过于复杂，因此这里采用手动创建一棵链式二叉树方便后续思路的代码实现。
单独封装一个函数可用来申请结点(和链表一样)； 手动创建多个结点，并让其形成一棵二叉树。
BTNode* BuyNode(BTDataType x)
{
BTNode* node = (BTNode*)malloc(sizeof(BTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
//malloc成功
node->data = x;
node->left = node->right = NULL;
return node;
}
//手动构造一颗二叉树
BTNode* CreaterTree()
{
BTNode* newnodeA = BuyNode('A');
BTNode* newnodeB = BuyNode('B');
BTNode* newnodeC = BuyNode('C');
BTNode* newnodeD = BuyNode('D');
BTNode* newnodeE = BuyNode('E');
BTNode* newnodeF = BuyNode('F');
newnodeA->left = newnodeB;
newnodeA->right = newnodeC;
newnodeB->left = newnodeD;
newnodeC->left = newnodeE;
newnodeC->right = newnodeF;
return newnodeA;
}
2. 前中后序遍历
既然是二叉树，那必然也离不开遍历。因此，我们有多种遍历方式。
2.1 遍历规则
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
- 前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前 访问顺序为：根结点、左子树、右子树（简称：根、左、右）
- 中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间） 访问顺序为：左子树、根结点、右子树（简称：左、根、右）
- 后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后 访问顺序为：左子树、右子树、根结点（简称：左、右、根）
以前序遍历为例如下图所示： 遵循前序遍历的规则： 1 先是访问A结点，然后进入左子树； 2. 在左子树中访问B根结点，进入B结点的左子树； 3. 在左子树中访问D根结点，而D中没有左子树和右子树，返回访问B的右子树； 4. B的右子树不存在，返回访问A的右子树； 5. 在右子树中访问C根结点，进入C结点的左子树； 6. 在左子树中访问E根结点，而E中没有左子树和右子树，返回访问C的右子树； 7. 在右子树中访问F根结点，F中没有左子树和右子树，遍历结束。
因此，前序遍历出来的数据是： A B D NULL NULL NULL C E NULL NULL F NULL NULL （NULL表示空）。
图文理解
2.2 代码实现
为了方便理解，建议看完此二篇。 函数栈帧的创建和销毁.
函数递归的理解 <-- 详见此文
前序遍历
//前序遍历 --- 根左右
void PreOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%c ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}图文理解
以上文的二叉树，前序遍历为例：
中序遍历
//中序遍历 --- 左根右
void InOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%c ", root->data);
InOrder(root->right);
}后序遍历
//后序遍历 --- 左右根
void PostOrder(BTNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%c ", root->data);
}3. 结点个数以及高度等
二叉树结点个数
错误示例1：
int BinaryTreeSize(BTNode* root)
{
static int size = 0;
if (root == NULL)
{
return 0;
}
++size;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
return size;
}我们开始的想法是通过调用该函数，在里面通过变量size计数，但每次递推调用函数的时候size又会重新置为0，因此我们又考虑用static修饰size延长其生命周期，使得每次递推的时候都能使size保存上一个函数调用的值，最后返回size的值得到该二叉树的结点个数。
但是，这明显存在一个错误，如果我们再次计算这个二叉树结点个数会出现什么情况？
我们打断点调试会发现size的值是从6开始的，这是为什么呢？ 很明显，size被static修饰延长了生命周期，使得该变量不再是因为栈空间的结束而销毁。因此，该做法是不可取的。
错误示例2：
void BinaryTreeSize(BTNode* root, int* psize)
{
if (root == NULL)
{
return 0;
}
++(*psize);
BinaryTreeSize(root->left,psize);
BinaryTreeSize(root->right,psize);
}既然我们不能从函数内部计数，那么我们是否能在函数外部定义指针变量size(要使得形参的改变能影响实参)来计数呢？ 虽然解决了生命周期被延长的做法，但下次调用函数依旧会出现问题，还是因为size没有从0开始(需要手动置为0)。
正确做法：
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}深刻理解了递归和栈帧空间的创建销毁思想后，一棵二叉树是由根结点、左子树和右子树组成的，那么计算结点个数自然而然就是 1 + 左子树 + 右子树。
4. 层序遍历
建议看完此篇。 栈和队列 <-- 详见此文
层序遍历：从所在二叉树的根结点出发，先访问第⼀层的树根结点，然后从左到右访问第2 层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程。
实现层序遍历需要额外借助数据结构：队列
- 将二叉树的根节点传给队列(队列可根据根节点找到左子树和右子树);
- 取队头元素并打印，同时删除队头元素；
- 若存在左孩子或右孩子，依次入队列；
- 继续取队头元素并打印，删除队头元素同时将队头的左孩子和右孩子入队列(存在情况下);
- 如此循环下去，直到队列为空完成了层序遍历。
// 层序遍历
void LevelOrder(BTNode* root)
{
//借助数据结构--队列
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
//取队头，出队头
BTNode* top = QueueFront(&q);
QueuePop(&q);
printf("%c ", top->data);
//队头左右孩子入队列(不为空)
if (top->left)
{
QueuePush(&q, top->left);
}
if (top->right)
{
QueuePush(&q, top->right);
}
}
QueueDestroy(&q);
}5. 判断是否完全二叉树
非完全二叉树：
完全二叉树：
// 判断⼆叉树是否是完全⼆叉树
bool BinaryTreeComplete(BTNode* root)
{
Queue q;
QueueInit(&q);
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top == NULL)
{
break;
}
//把不为空的队头节点的左右孩子入队列
QueuePush(&q, top->left);
QueuePush(&q, top->right);
}
//队列不一定为空，继续取队头出队头
while (!QueueEmpty(&q))
{
BTNode* top = QueueFront(&q);
QueuePop(&q);
if (top != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}腾讯云开发者
