链式二叉树概念和结构
文章目录
- 1. 链式二叉树概念
- 2. 再看二叉树
- 3. 二叉树的实现
- 3.1 前序、中序以及后序遍历
- 1）前序遍历
- 2）中序遍历
- 3）后序遍历
- 4）代码实现遍历
- 3.2 节点个数以及高度等
- 1）二叉树节点个数
- 2）二叉树叶子节点个数
- 3）二叉树高度
- 4）二叉树第k层节点个数
- 5）二叉树查找值为x的节点
- 6）运行效果
- 3.3 二叉树的创建和销毁
- 1）二叉树的创建
- 2）二叉树的销毁
- 3.4 二叉树的层次遍历、是否完成二叉树
- 1）层序遍历
- 2）一层一层输出的层序遍历
- 3）是否完全二叉树
- 4）运行效果
- 4. 再看二叉树性质
1. 链式二叉树概念
二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，当前讲解的是二叉链。
2. 再看二叉树
二叉树主要分为：
1）空树
2）非空：根节点，根节点的左子树、根节点的右子树组成的。
任意一颗二叉树都可以分为根节点、左子树、右子树。一个二叉树还可以继续拆分为2课子树，直到为空。
为了方便进行各项操作，将链式二叉树的结构定义如下，并简单构建一颗二叉树
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <math.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}TreeNode;
TreeNode* BuyTreeNode(int x)
{
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
if (node == NULL)
{
perror("malloc fail\n");
exit(-1);
}
node->data = x;
node->left = NULL;
node->right = NULL;
return node;
}
TreeNode* CreateTree()
{
TreeNode* node1 = BuyTreeNode(1);
TreeNode* node2 = BuyTreeNode(2);
TreeNode* node3 = BuyTreeNode(3);
TreeNode* node4 = BuyTreeNode(4);
TreeNode* node5 = BuyTreeNode(5);
TreeNode* node6 = BuyTreeNode(6);
TreeNode* node7 = BuyTreeNode(7);
node1->left = node2;
node1->right = node4;
node2->left = node3;
node4->left = node5;
node4->right = node6;
node5->right = node7;
return node1;
}
int main()
{
TreeNode* root = CreateTree();
return 0;
}
下面将根据代码定义结构进行各项操作与知识讲解。
3. 二叉树的实现
从概念中可以看出，二叉树定义是递归式的，因此后面基本操作中基本都是按照该概念实现的。
3.1 前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
注意：下面的遍历将带上NULL。原因是，既可以更彻底的理解链式二叉树的递归原理以及遍历顺序，也可以方便通过这样的遍历顺序写出对应的递归代码。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
1）前序遍历
Preorder Traversal 亦称先序遍历，访问根结点的操作发生在遍历其左右子树之前，即 根、左子树、右子树 的顺序。
2）中序遍历
Inorder Traversal，访问根结点的操作发生在遍历其左右子树之中（间），即 左子树、根、右子树 的顺序。
3）后序遍历
Postorder Traversal，访问根结点的操作发生在遍历其左右子树之后，即 左子树、右子树、根 的顺序。
上面三种遍历顺序如下：
提示：
为了方便记忆顺序，将每个树（包含子树）的根标记左中右三个方向，如图所示，前序遍历只有到达左的标记点才遍历，后面两种一致。
4）代码实现遍历
接下来，将用递归，按照带有N的遍历规则，实现前序、中序以及后序遍历。
// 前序遍历（根、左子树、右子树）
void PrevOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->data);
PrevOrder(root->left);
PrevOrder(root->right);
}
//中序遍历（左子树、根、右子树）
void InOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
PrevOrder(root->right);
}
// 后序遍历（左子树、右子树、根）
void PostOrder(TreeNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
InOrder(root->left);
PrevOrder(root->right);
printf("%d ", root->data);
}
递归展开顺序如下：
运行效果如下，和分析一致：
3.2 节点个数以及高度等
完成前序/中序/后序遍历后，二叉树的操作还有查看二叉树节点个数、叶子节点个数、二叉树高度以及第k层节点个数。
这些操作毋庸置疑都是递归实现，那怎么实现递归的代码呢？
需要明确的是，递归的思想都是
1）子问题分治。 在上述对二叉树的定义中，可以知道，任何二叉树都可以分为根、左子树、右子树，那么将利用这一特性对整个问题划分为子问题，子问题又继续按照此规则进一步划分，直到问题可以解决。（ 大问题划分小问题，小问题又划分，直到解决 ）
2）返回条件。 在二叉树中，总体可以划分为 空或者非空树，返回条件则将以此为基础设置递归返回条件。（ 终止条件 ）
接下来将按照递归思想和二叉树的定义，完成上述操作：
1）二叉树节点个数
子问题分治：左子树节点个数+右子树节点个数+1，即左/右子树节点数量+根节点（即加一）
返回条件：空则返回0，叶子则返回1
int TreeSize(TreeNode* root)
{
// 1 逻辑清晰
//if (root == NULL)
// return 0;
//return TreeSize(root->left) + TreeSize(root->right) + 1;
// 2 三目操作符，简洁清晰
return root == NULL ? 0 :
TreeSize(root->left) + TreeSize(root->right) + 1;
}
2）二叉树叶子节点个数
子问题分治：叶子节点等于左/右子树叶子之和
返回条件：空则返回0，不是空是叶子（左/右子树为空）返回1
int TreeLeafSize(TreeNode* root)
{
if (root == NULL)
return 0;
if (root->left == NULL && root->right == NULL)
return 1;
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
3）二叉树高度
子问题分治：假设知道左/右子树子树高度，两者比较返回高度大的
返回条件：空则返回0，不是空返回左/右子树高度大的那个+1，这里的加一是该树的根节点（根自身高度为1）
int TreeHeight(TreeNode* root)
{
if (root == NULL)
return 0;
// 1 函数比较最大值
//return fmax(TreeHeight(root->left),
// TreeHeight(root->right)) + 1;
// 2 不可以使用三目操作符，要先存遍历，否则相当于遍历了两次
int treeLeft = TreeHeight(root->left);
int treeRight = TreeHeight(root->right);
return treeLeft > treeRight ? treeLeft + 1 : treeRight + 1;
}
// 错误代码！！！！！！！
int TreeHeight(TreeNode* root)
{
// 使用递归找出大小，但没有保存，再次遍历了，等于遍历了两次，有一次是没必要的浪费
return root == NULL ? 0 :
TreeHeight(root->left) > TreeHeight(root->right) ?
TreeHeight(root->left) + 1 :
TreeHeight(root->right);
}
4）二叉树第k层节点个数
子问题分治：整棵树根节点和根节点的子节点个数容易算，因此可以拆分为计算根节点或者左子树和右子树的 k-1 层
返回条件：空则返回0；不是空 k==1 返回1（整棵树根节点）；不为空且 k>0 返回左/右子树 k-1 层
int TreeLevelK(TreeNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return TreeLevelK(root->left, k - 1)
+ TreeLevelK(root->right, k - 1);
}
5）二叉树查找值为x的节点
思路就是对二叉树进行遍历，这里采用前序遍历，遇到哪个节点就进行比较，效率更高
TreeNode* TreeFind(TreeNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
TreeNode* ret1 = TreeFind(root->left, x);
if (ret1)
return ret1;
// 1、不太好
//return TreeFind(root->right, x);
// 2、比较清晰
TreeNode* ret2 = TreeFind(root->right, x);
if (ret2)
return ret2;
return NULL;
}
6）运行效果
为了验证高度，在 5 节点插入右子树节点 6 进行验证，总运行效果如下：
TreeNode* node7 = BuyTreeNode(7);
node5->right = node7;
3.3 二叉树的创建和销毁
1）二叉树的创建
前提条件需要将二叉树类型修改为字符类型。
二叉树的创建采用的思想是依据给出的序列选择合适的遍历方法，创建放在此处的原因也是因为要了解相关二叉树的知识后会更容易理解。
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
TreeNode* TreeCreate(BTDataType* a, int* pi)
{
if (a[(*pi)] == '#')
{
(*pi)++;
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
if (root == NULL)
{
perror("malloc fail\n");
return NULL;
}
root->data = a[*pi];
(*pi)++;
root->left = TreeCreate(a, pi);
root->right = TreeCreate(a, pi);
return root;
}
2）二叉树的销毁
销毁主要采用后序遍历，因为如果直接销毁掉根节点，那么就没办法继续取到下一个节点，增加变量也会使开销变大，后续遍历能先销毁掉子节点，然后逐层往上。
void TreeDestory(TreeNode* root)
{
if (root == NULL)
return;
TreeDestory(root->left);
TreeDestory(root->right);
free(root);
root = NULL;
}
3.4 二叉树的层次遍历、是否完成二叉树
这里需要引入队列的知识创建队列，并利用其实现层序遍历。
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
QDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;
}Queue;
1）层序遍历
首先根节点进队列，出一个节点，左右子节点就去，直到队列为空。这里加判定条件，为空就不进队列。
需要注意的是，出队后，是队列的节点（节点指向二叉树节点指针的地址）被销毁了，二叉树的节点空间是没有被释放的，
void LevelOrder(TreeNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
TreeNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left != NULL)
QueuePush(&q, front->left);
if (front->right != NULL)
QueuePush(&q, front->right);
}
printf("\n");
}
2）一层一层输出的层序遍历
这里在上面的基础上，加一个数量 levelSize ，用其记录节点个数，每打印 levelSize 次就换行重新打印
void EachLevelOrder(TreeNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
int levelSize = QueueSize(&q);
while (!QueueEmpty(&q))
{
while (levelSize--)
{
TreeNode* front = QueueFront(&q);
QueuePop(&q);
printf("%d ", front->data);
if (front->left != NULL)
QueuePush(&q, front->left);
if (front->right != NULL)
QueuePush(&q, front->right);
}
levelSize = QueueSize(&q);
printf("\n");
}
}
3）是否完全二叉树
这里依旧利用层序遍历的知识，和上面不同的是，即使是空节点也进队，第一次循环遇到空节点就终止，然后第二次循环判定剩余节点是否为空，不为空说明后面有节点，不符合完全二叉树。
bool TreeComplete(TreeNode* root)
{
Queue q;
QueueInit(&q);
if (root)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
TreeNode* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
break;
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
while (!QueueEmpty(&q))
{
TreeNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestroy(&q);
return false;
}
}
return true;
}
4）运行效果
4. 再看二叉树性质
以上就是二叉树的全部内容
至此，树的内容基本结束！！