北京通信管理局网站备案处,代做网站微信号,企业微信app下载安装安卓版,网站文章优化技巧#x1f4f7; 江池俊#xff1a; 个人主页 #x1f525;个人专栏#xff1a; ✅数据结构冒险记 ✅C语言进阶之路 #x1f305; 有航道的人#xff0c;再渺小也不会迷途。 文章目录 前言一、二叉树的存储结构二、二叉树链式结构的实现三、二叉树的前、中、后续遍历 江池俊 个人主页 个人专栏 ✅数据结构冒险记 ✅C语言进阶之路 有航道的人再渺小也不会迷途。 文章目录 前言一、二叉树的存储结构二、二叉树链式结构的实现三、二叉树的前、中、后续遍历三种遍历四、二叉树的层次遍历五、二叉树节点个数以及高度等5.1 二叉树节点个数5.2 二叉树叶子节点个数5.3 二叉树的高度5.4 二叉树第k层节点个数5.5 二叉树查找值为x的节点 六、根据所给数组构建一颗二叉树七、二叉树的销毁八、判断二叉树是否是完全二叉树 前言 二叉树的相关概念和结构在上一章节已经有详细介绍传送门二叉树数据结构中的灵魂 一、二叉树的存储结构
BTDataType 表示二叉树的节点存储元素的类型BTNode 表示二叉树的节点left 和 right 分别表示节点的左右孩子节点data 表示节点存储的元素。
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;二、二叉树链式结构的实现 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
// 申请节点
BTNode* BuyTreeNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));assert(node);node-data x;node-left NULL;node-right NULL;return node;
}//建树
BTNode* CreateTree()
{BTNode* node1 BuyTreeNode(1);BTNode* node2 BuyTreeNode(2);BTNode* node3 BuyTreeNode(3);BTNode* node4 BuyTreeNode(4);BTNode* node5 BuyTreeNode(5);BTNode* node6 BuyTreeNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}注意上述代码并不是创建二叉树的方式真正创建二叉树方式在本文后重点讲解。
在看二叉树基本操作前再回顾下二叉树的概念二叉树是
空树非空根节点根节点的左子树、根节点的右子树组成的。
从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。 三、二叉树的前、中、后续遍历三种遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
下面请看二叉树三种遍历方法的代码实现
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL) {return;}BinaryTreePrevOrder(root-left);printf(%d , root-data);BinaryTreePrevOrder(root-right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){return;}BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);printf(%d , root-data);
}下面主要分析前序递归遍历中序与后序图解类似。
前序遍历递归图解 四、二叉树的层次遍历
层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 二叉树的层次遍历通常是通过队列来实现的这是因为我们需要利用队列先进先出的特性来保存之前被访问过的节点的孩子节点这是一种广度优先搜索BFS的策略。下面是一个基本的实现思路
首先我们需要一个队列来保存待处理的节点。一开始队列中只有根节点。然后进入一个循环条件是队列不为空。在循环中我们首先取出队列的第一个节点并访问它比如打印节点的值。接着如果这个节点有左孩子就把左孩子加入队列的末尾。然后如果这个节点有右孩子就把右孩子也加入队列的末尾。最后把刚才取出的节点从队列中移除然后回到步骤2继续处理队列中的下一个节点。
这个过程会一直持续到队列为空也就是所有的节点都已经被访问过了。
辅助队列代码
// 链式结构表示队列
typedef struct BinaryTreeNode* QDataType; //元素类型此处类型是二叉树节点的指针
//队列的节点
typedef struct QListNode
{QDataType data;struct QListNode* next;
}QNode;
// 队列的结构
typedef struct Queue
{QNode* front; //对头QNode* rear; //队尾int size; //队列元素个数
}Queue;// 初始化队列
void QueueInit(Queue* q)
{assert(q);q-front q-rear NULL;q-size 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc);return;}newnode-data data;newnode-next NULL;if (q-front NULL){q-front q-rear newnode;}else{q-rear-next newnode;q-rear newnode;}q-size;//队列元素加一
}
// 队头出队列
void QueuePop(Queue* q)
{assert(q);//队列不为空assert(q-front);QNode* cur q-front;q-front q-front-next;//队列只有一个元素的情况要考虑队尾的指针防止野指针if (q-front NULL)q-rear NULL;free(cur);q-size--;//队列元素减一
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{assert(q);//队列不为空assert(q-front);return q-front-data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{assert(q);return q-size;
}
// 检测队列是否为空如果为空返回非零结果如果非空返回0
int QueueEmpty(Queue* q)
{assert(q);return q-front NULL;
}
// 销毁队列
void QueueDestroy(Queue* q)
{assert(q);QNode* cur q-front;while (cur)//当cur为空时结束{QNode* next cur-next;free(cur);cur next;}q-front q-rear NULL;q-size 0;
}二叉树层次遍历代码
// 非递归遍历二叉树
// 层序遍历(利用队列“先进先出”--出去一个节点就立即带入此节点的左右节点进队)
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}QueueDestroy(q);
}
// 一层一层访问节点
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1; //控制层数第一层数据个数为1while (!QueueEmpty(q)){// 一层一层出数据while (levelSize--){BTNode* 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);levelSize QueueSize(q);}QueueDestroy(q);
}五、二叉树节点个数以及高度等
5.1 二叉树节点个数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL) // 空树return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}5.2 二叉树叶子节点个数
// 二叉树叶子节点个数
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);
}5.3 二叉树的高度
// 二叉树的高度
int BinaryTreeHeight(BTNode* root)
{if (root NULL)return 0;int leftHeight BinaryTreeHeight(root-left); // 左子树的高度int rightHeight BinaryTreeHeight(root-right); //右子树的高度return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}5.4 二叉树第k层节点个数
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL) // 空树return 0;if (k 1) // 第一层return 1;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}5.5 二叉树查找值为x的节点
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BinaryTreeFind(root-left, x);if (ret1){return ret1;}BTNode* ret2 BinaryTreeFind(root-right, x);if (ret2){return ret2;}return NULL;
}六、根据所给数组构建一颗二叉树
例 通过前序遍历的数组 “ABD##E#H##CF##G##” 构建二叉树“#”表示的是空格空格字符代表空树。
// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi) //这里pi的类型为int*是为了递归时确保值的完整性
{assert(*pi 0 *pi n);if (a[(*pi)] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc error);return;}root-data a[(*pi)];root-left BinaryTreeCreate(a, n, pi);root-right BinaryTreeCreate(a, n, pi);return root;
}该函数接受三个参数a 是指向前序遍历数组的指针n 是数组的长度pi 是一个指向整数的指针用于记录当前处理的元素索引。
函数首先使用断言 assert(*pi 0 *pi n) 确保索引 *pi 在合法范围内。然后判断当前元素是否为特殊字符 #如果是则表示当前节点为空将索引 *pi 加一后返回 NULL。如果当前元素不是特殊字符则创建一个新的二叉树节点 root并为其分配内存空间。如果内存分配失败则打印错误信息并返回。接下来将当前元素的值赋给 root 节点的数据域 root-data并将索引 *pi 加一。然后递归调用 BinaryTreeCreate 函数来构建 左子树 和 右子树分别赋值给 root-left 和 root-right。最后返回根节点 root。 七、二叉树的销毁
由于在遍历二叉树时前序和中序都需要保存根节点而后续遍历不用故使用后续遍历递归销毁二叉树最简单。
// 二叉树销毁利用后序遍历销毁前中序遍历都需要保存根节点
void BinaryTreeDestory(BTNode** root)
{assert(root);if (*root NULL)return;BinaryTreeDestory((*root)-left); BinaryTreeDestory((*root)-right); free(*root);*root NULL;
}八、判断二叉树是否是完全二叉树
思路利用队列来进行层序遍历并在遍历过程中检查是否存在未被访问的节点。
初始化队列首先创建一个队列 q并将根节点 root 加入队列如果根节点存在的话。层序遍历然后通过层序遍历的方式访问二叉树的每个节点。遍历过程中如果遇到 NULL 节点就跳出循环。检查空节点完成层序遍历后再次检查队列中的节点。如果队列不为空且队首节点不为 NULL则说明存在非空节点未被访问即该二叉树不是完全二叉树。函数返回 false。清理队列如果上述检查中没有发现非空节点未被访问则说明该二叉树是完全二叉树。在返回 true 之前销毁队列以释放内存。
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);int levelSize 1; //控制层数第一层数据个数为1while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL)break;QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q); QueuePop(q);if (front){QueueDestroy(q); return false;}}QueueDestroy(q);return true;
}
