🐱作者：傻响
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！
目录
二叉树链式结构的实现
4.1 前置说明
4.2二叉树的遍历
4.3 前序、中序以及后序的理解
4.3.1 二叉树前序遍历
4.3.2 二叉树中序遍历
4.3.3 二叉树后序遍历
4.3.4 二叉树节点个数
4.3.5 二叉树叶子节点个数
4.3.6 二叉树求高度深度
4.3.7 二叉树第k层节点个数
4.3.8 二叉树查找值为x的节点
4.3.9 二叉树构建
4.3.10 二叉树销毁
4.3.11 二叉树层序遍历
4.3.12 判断一棵树是否是完全二叉树
二叉树链式结构的实现 4.1 前置说明
在学习二叉树的基本 *** 作前，需先要创建一棵二叉树，然后才能学习其相关的基本 *** 作。由于现在大家对二 叉树结构掌握还不够深入，为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树 *** 作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
4.2二叉树的遍历4.2.1 前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的 *** 作，并且每个节点只 *** 作一次。访问结点所做的 *** 作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：
-
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的 *** 作发生在遍历其左右子树之前。
《根、左子数、右子数》
-
中序遍历(Inorder Traversal)——访问根结点的 *** 作发生在遍历其左右子树之中（间）。
《左子数、根、右子数》
-
后序遍历(Postorder Traversal)——访问根结点的 *** 作发生在遍历其左右子树之后。
《左子数、右子数、根》
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
4.3 前序、中序以及后序的理解
写一个测试程序：
#include
#include
#include
// 二叉树结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BinaryTreeNode;
BinaryTreeNode* CreateTree()
{
BinaryTreeNode* n1 = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
assert(n1);
BinaryTreeNode* n2 = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
assert(n2);
BinaryTreeNode* n3 = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
assert(n3);
BinaryTreeNode* n4 = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
assert(n4);
BinaryTreeNode* n5 = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
assert(n5);
BinaryTreeNode* n6 = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
assert(n6);
n1->data = 1;
n2->data = 2;
n3->data = 3;
n4->data = 4;
n5->data = 5;
n6->data = 6;
n1->left = n2;
n1->right = n4;
n2->left = n3;
n2->right = NULL;
n3->left = NULL;
n3->right = NULL;
n4->left = n5;
n4->right = n6;
n5->left = NULL;
n5->right = NULL;
n6->left = NULL;
n6->right = NULL;
return n1;
}
// 二叉树前序遍历
void PreOrder(BinaryTreeNode* root);
// 二叉树中序遍历
void InOrder(BinaryTreeNode* root);
// 二叉树后序遍历
void PostOrder(BinaryTreeNode* root);
int main()
{
BinaryTreeNode* root = CreateTree();
return 0;
}// 二叉树前序遍历
void PreOrder(BinaryTreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->data);
PreOrder(root->left);
PreOrder(root->right);
}递归分布图这里就先不画了，感兴趣的小伙伴可以尝试
// 二叉树中序遍历
void InOrder(BinaryTreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}递归分布图这里就先不画了，感兴趣的小伙伴可以尝试
// 二叉树后序遍历
void PostOrder(BinaryTreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}// 二叉树节点个数 - 第一种方式计数法
static int count = 0;
void BinaryTreeSize(BinaryTreeNode* root)
{
if (root == NULL)
return;
// 如果不是空，计数，递归
count++;
BinaryTreeSize(root->left);
BinaryTreeSize(root->right);
}
int main()
{
BinaryTreeNode* root = CreateTree();
count = 0;
BinaryTreeSize(root);
printf("BinaryTree Size: %d\n",count);
count = 0;
BinaryTreeSize(root);
printf("BinaryTree Size: %d\n", count);
return 0;
}
// 上面方式，是使用了静态变量，每一次调用静态变量都要进行清空。
// 方式二：使用孩子分支问题结果该问题
int BinaryTreeSize(BinaryTreeNode* root)
{
// 解释：root是NULL吗？如果是返回0，如果不是左右汇总加上自身！
return root == NULL ? 0
: BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}
int main() // 这样问题可以很好的解决！
{
BinaryTreeNode* root = CreateTree();
printf("Binary Tree Size : %d\n",BinaryTreeSize(root));
return 0;
}// 二叉树求叶子节点个数
int BinaryTreeLeafSize(BinaryTreeNode* root)
{
if (root == NULL)
return 0;
else if(root->left == NULL && root->right == NULL)
return 1;
// 如果都不是，说明我不是叶子,找下面的。
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
int main()
{
BinaryTreeNode* root = CreateTree();
printf("Binary Tree Leaf Size : %d\n",BinaryTreeLeafSize(root));
return 0;
}4.3.6 二叉树求高度深度
// 二叉树求树的高度 - 使用后序遍历
int BinaryTreeHeight(BinaryTreeNode* root)
{
if (root == NULL)
return 0;
// 左边和右边子树的高度
int leftTreeHeight = BinaryTreeHeight(root->left);
int rightTreeHeight = BinaryTreeHeight(root->right);
// 返回条件作为比较
return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1 : rightTreeHeight + 1;
}层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
// 二叉树第k层节点个数
int BinaryTreeKLevel(BinaryTreeNode* root, int k)
{
assert(k > 0);
if (root == NULL)
return 0;
if (k == 1)
return 1;
return BinaryTreeKLevel(root->left, k - 1) + BinaryTreeKLevel(root->right, k - 1);
}
int main()
{
BinaryTreeNode* root = CreateTree();
printf("Binary Tree KLevel : %d\n", BinaryTreeKLevel(root,3));
return 0;
}// 二叉树查找值为x的节点
BinaryTreeNode* BinaryTreeFind(BinaryTreeNode* root, BTDataType x)
{
if (root == NULL)
return NULL;
if (root->data == x)
return root;
// 先找左树
BinaryTreeNode* leftRet = BinaryTreeFind(root->left, x);
if (leftRet != NULL)
return leftRet;
// 在找右树
BinaryTreeNode* rightRet = BinaryTreeFind(root->right, x);
if (rightRet != NULL)
return rightRet;
// 没找到返回NULL
return NULL;
}
int main()
{
BinaryTreeNode* root = CreateTree();
printf("Binary Tree Find : %p\n", BinaryTreeFind(root, 4));
return 0;
}#include
#include
#include
// 二叉树 - 结构
typedef int HPDataType;
typedef struct HeapTreeNode
{
HPDataType data;
struct HeapTreeNode* left;
struct HeapTreeNode* right;
}HeapTreeNode;
// 二叉树 - 创建
HeapTreeNode* BinaryTreeCreate(char* arr, int* pI)
{
// 如果arr[pI]是‘#’号的话，那就直接返回。
if(arr[*pI] == '#')
{
(*pI)++;
return NULL;
}
// 开辟内存空间，并且将pI当前指向的数组值，给新的节点。
HeapTreeNode* root = (HeapTreeNode*)malloc(sizeof(HeapTreeNode));
if(root == NULL)
{
perror("BinaryTreeCreate malloc fail!");
return NULL;
}
root->data = arr[*pI];
(*pI)++;
// 上面条件满足的情况加，进行递归！
root->left = BinaryTreeCreate(arr,pI);
root->right = BinaryTreeCreate(arr, pI);
// 最后返回节点
return root;
}
// 二叉树 - 中序打印。
void InOrder(HeapTreeNode* root)
{
if(root == NULL)
return;
InOrder(root->left);
printf("%c ",root->data);
InOrder(root->right);
}
// 主程序
// abc##de#g##f###
int main()
{
// 常见可以接收的数组进行存放值。
char arr[101];
scanf("%s",&arr);
// 构建而二叉树
int i = 0;
HeapTreeNode* root = BinaryTreeCreate(arr, &i);
// 中序打印二叉树
InOrder(root);
return 0 ;
} // 二叉树销毁
void BinaryTreeDestroy(BinaryTree* root)
{
if (root == NULL)
return;
// 递归左、右、然后free
BinaryTreeDestroy(root->left);
BinaryTreeDestroy(root->right);
free(root);
}层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层 上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
二叉树的层序遍历，这里我们需要借助队列进行 *** 作：
画图分析一下：
// 层序打印
void LevelOrder(BinaryTree* root)
{
Queue q;
QueueInit(&q);
// 将root第一个数据，先放入队列！
if (root != NULL)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BinaryTree* front = QueueFront(&q);
QueuePop(&q);
printf("%c ",front->data);
// 下一层，入栈（有左边入左边，有右边入右边）
if(front->left)
QueuePush(&q, front->left);
if (front->right)
QueuePush(&q, front->right);
}
printf("\n");
}// 判断是否是完全二叉树
bool BinaryTreeComplete(BinaryTree* root)
{
Queue q;
QueueInit(&q);
// 将root第一个数据，先放入队列！
if (root != NULL)
QueuePush(&q, root);
while (!QueueEmpty(&q))
{
BinaryTree* front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
// 下一层，入栈（有左边入左边，有右边入右边）
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
// 遇到空以后，后面全是空，则是完全二叉树。
// 遇到空以后，后面非全是空，则不是完全二叉树。
while (!QueueEmpty(&q))
{
BinaryTree* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
QueueDestroy(&q);
return false;
}
}
QueueDestroy(&q);
return true;
}欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）