网站开发与客户沟通,wordpress 作者调用,免费w网站建设,集成电路行业人才上一篇文章我们结束了二叉树的顺序存储#xff0c;本届内容我们来到二叉树的链式存储#xff01; 链式二叉树 1.链式二叉树的遍历1.1二叉树的前序#xff0c;中序#xff0c;后序遍历1.2 三种遍历方法代码实现 2. 获取相关个数2.1获取节点个数2.2获取叶节点个数2.3 获取树的… 上一篇文章我们结束了二叉树的顺序存储本届内容我们来到二叉树的链式存储 链式二叉树 1.链式二叉树的遍历1.1二叉树的前序中序后序遍历1.2 三种遍历方法代码实现 2. 获取相关个数2.1获取节点个数2.2获取叶节点个数2.3 获取树的高度2.4 计算第K层节点个数 3.寻找某个节点4.用前序遍历建造一个二叉树5.二叉树的销毁6.链式二叉树的层序遍历7.判断是否为完全二叉树 1.链式二叉树的遍历
首先我们定义二叉树节点内容
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinartTreeNode* left;struct BinartTreeNode* right;
}TreeNode;每个节点包含两个指针指向左子树和右子树 左右子树的节点又可以细分为根左子树右子树
1.1二叉树的前序中序后序遍历
前序遍历、中序遍历和后序遍历。这些遍历方式指的是节点访问的顺序。
前序遍历在前序遍历中我们首先访问根节点然后递归地进行左子树的前序遍历接着递归地进行右子树的前序遍历。中序遍历中序遍历中我们首先递归地进行左子树的中序遍历然后访问根节点最后递归地进行右子树的中序遍历。后序遍历后序遍历中我们首先递归地进行左子树的后序遍历然后递归地进行右子树的后序遍历最后访问根节点。
我们以一颗树为例来展开讨论 首先讨论前序遍历
在前序遍历中我们首先访问根节点然后是左子树最后是右子树。 对于上述树的前序遍历遍历顺序将是
访问根节点 1访问左子节点 2访问左子节点 2 的左子节点 3左子节点3的左子树为空返回到3访问完3的左子树访问3的右子树为空返回到32的左子树访问完访问2的右子树为空返回到21的左子树访问完成回到1访问右子树4访问4的左子树5再访问5的左5的左为空则返回访问5的右再返回到54的左子树遍历完成访问右子树66的左右都为空访问结束
如果用N来代表空我们可以表示出访问顺序
1 2 3 N N N 4 5 N N 6 N N接下来讨论中序遍历
在中序遍历中我们首先遍历左子树然后访问根节点最后遍历右子树
遍历顺序
首先访问左子树1的左子树2再到2的左子树33的左子树为NULL访问空返回到三再访问节点3根访问后到右子树NULL所以开始访问顺序为
N 3 N访问完2的左子树再按照顺序访问根节点2再访问2的右子树N
N 3 N 2 N访问完1的左子树访问节点1再访问1的右子树而右子树4部分优先访问左子树所以先访问到5的左子树NULL再访问5节点和5的右子树NULL
N 3 N 2 N 1 N 5 N访问完4的左子树访问根节点4再访问4的右子树右子树优先访问左子树部分即6的左子树NULL再到6节点最后访问6的右子树NULL
N 3 N 2 N 1 N 5 N 4 N 6 N最后我们来看后序遍历
首先访问1的左子树在子树中首先访问 2 的左子树3的左子树为空NULL访问后访问3的右子树NULL再访问根节点3
N N 3访问完2的左子树后访问2的右子树NULL再访问节点2
N N 3 N 2访问完1的左子树再访问1的右子树子树中先访问4的左子树5组成的子树部分先访问5的左子树NULL再访问5的右子树NULL最后访问根节点5
N N 3 N 2 N N 54的左子树访问完成后访问4的右子树子树部分6先访问6的左右NULL再访问根节点6
N N 3 N 2 N N 5 N N 64的左右子树访问完成访问根节点41的左右子树访问完成访问根节点1
N N 3 N 2 N N 5 N N 6 4 11.2 三种遍历方法代码实现
接下来我们硬代码构造一个上图的树来完成我们三种遍历方式的代码
TreeNode* CreatTreeNode(int x)
{TreeNode* node (TreeNode*)malloc(sizeof(TreeNode));node-data x;node-left NULL;node-right NULL;return node;
}
TreeNode* FCreatTree()
{TreeNode* node1 CreatTreeNode(1);TreeNode* node2 CreatTreeNode(2);TreeNode* node3 CreatTreeNode(3);TreeNode* node4 CreatTreeNode(4);TreeNode* node5 CreatTreeNode(5);TreeNode* node6 CreatTreeNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}在上述三种方法的讨论中我们可以知道三种遍历是用递归方法来完成的
前序遍历首先访问当前节点根节点然后递归地进行左子树的前序遍历最后递归地进行右子树的前序遍历
代码如下
void PrevOrder(TreeNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}如果遇到节点为空则打印N 并返回注意这里是递归进行的返回是指返回到上一层函数printf(%d , root-data);首先访问根节点PrevOrder(root-left);访问左子树进入左子树里面又分为先访问根节点再访问左子树PrevOrder(root-right);访问完左子树后访问右子树
我们可以画出递归展开图来加深理解 由1先访问根节点1再到左子树22访问完根节点到左子树3 3访问左子树为空返回到上一层函数接着访问3的右子树 3函数结束返回到上一层函数来对2的右子树进行访问以此类推 递归展开图可以更好的帮我们理解递归的过程
有了上述的讲解中序遍历和后续遍历则变得很简单了
中序遍历代码
void InOrder(TreeNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}InOrder(root-left);先访问左子树printf(%d , root-data);左子树访问完后访问根节点InOrder(root-right);最后访问右子树
后序遍历代码
void PostOrder(TreeNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}代码测试如下 与刚刚讨论结果一致
2. 获取相关个数
2.1获取节点个数
获取二叉树节点个数的核心思想是基于递归遍历整个树并计数。基于二叉树的性质我们可以采用分治法二叉树的节点总数是其左子树的节点数加上右子树的节点数再加上根节点本身
基本步骤
递归的基准情况如果当前节点为NULL意味着到达了叶子节点的外部空树返回0。递归分解问题递归地计算左子树的节点个数和右子树的节点个数。合并结果将左子树的节点数和右子树的节点数相加然后加1代表当前节点得到的总和就是整个二叉树的节点个数。
int TreeSize(TreeNode* root)
{if (root NULL){return 0;}return 1 TreeSize(root-left) TreeSize(root-right);
}在上面的代码中TreeSize函数会递归地遍历整棵树每遇到一个非空节点就通过递归计算它的左右子树的节点数然后将这两个数加起来并加上1当前节点。通过这种方式当递归遍历完整棵树后我们就可以得到二叉树的节点总数。
我们还可以用三目运算符简化上述代码
int TreeSize(TreeNode* root)
{
return rootNULL?0:TreeSize(root-left)1TreeSize(root-right);
}测试代码以上树为例 1/ \2 4/ / \
3 5 62.2获取叶节点个数
获取二叉树中叶节点叶子节点个数的思路与获取节点总数相似但关注的是那些没有子节点的节点。叶子节点定义为没有左右子树的节点。基于递归的方法我们可以遍历整棵树并在遇到叶子节点时对计数器进行增加。
递归的基准情况如果当前节点为NULL意味着到达叶子节点的外部空树直接返回0。识别叶子节点如果当前节点既没有左子树也没有右子树意味着它是一个叶子节点因此返回1。递归分解问题如果当前节点不是叶子节点递归地计算左子树的叶子节点个数和右子树的叶子节点个数。合并结果将左子树的叶子节点数和右子树的叶子节点数相加得到的和就是整个二叉树的叶子节点个数
int TreeleafSize(TreeNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}else{return TreeleafSize(root-left) TreeleafSize(root-right);}
}对于每一个节点算法检查是否它是一个叶子节点如果是返回1否则继续在它的左右子树中寻找叶子节点并计数。最终通过对所有找到的叶子节点进行计数我们可以得到整个二叉树的叶子节点数。
测试
2.3 获取树的高度
获取二叉树的高度或深度的基本思路是遵循分治法原则即递归地计算二叉树每个节点的左右子树的高度并从中选择最大的一个然后加1当前节点在路径上增加的高度来得到以该节点为根的子树的总高度。树的总高度即是从根节点到最远叶子节点的最长路径上的节点数。
递归基准如果当前的节点为NULL意味着到达了叶子节点的外部空树其高度为0。递归地检查递归地计算左子树的高度和右子树的高度。选择最大的子树高度并加上当前节点从左子树和右子树的高度中选择更大的一个然后加1当前节点本身来得到整个子树的高度。
首先我们来看这串代码
int TreeHeight(TreeNode* root) {if (root NULL){return 0;}TreeHeight(root-left);TreeHeight(root-right);return (TreeHeight(root-left) TreeHeight(root-right) ? TreeHeight(root-left) : TreeHeight(root-right)) 1;
}这串代码有很大的缺陷
三目运算符对 TreeHeight(root-left) 和 TreeHeight(root-right) 各调用了两次。对于每一个非叶子节点它的左右子树高度都被计算了两遍。这种重复计算对于简单的树结构可能不明显但对于较大的二叉树来说就会导致大量不必要的计算进而降低程序的运行效率。
改进
int TreeHeight(TreeNode* root) {if (root NULL){return 0;}int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return (leftHeight rightHeight ? leftHeight : rightHeight) 1;
}2.4 计算第K层节点个数
计算二叉树第 (k) 层的节点个数同样可以采用递归的方法来解决。这个问题可以拆分为计算某节点左子树的第 (k-1) 层节点个数和右子树的第 (k-1) 层节点个数的和因为从当前节点的视角看它的子树的层数都少了一层。
int TreeKcount(TreeNode* root, int k)
{if (root NULL||k1){return 0;}if (k 1){return 1;}return TreeKcount(root-left, k - 1) TreeKcount(root-right, k - 1);
}当达到第 1 层时若二叉树非空则第1层的节点数肯定是1即当前节点因为每次递归减少1层直到递归到目标层级
当我们要求的是第1层的节点数量时即树的根节点且树非空那么节点数量为1。当 k 值大于1时我们通过递归调用来求解左右子树在第 (k-1) 层的节点数量然后将它们相加得到答案。通过递归减少 k 的值我们逐渐深入到树中更深的层次直到 k 减至1这时我们就到达了目标层并可以直接计算节点数量。
测试代码 1/ \2 4/ / \
3 5 63.寻找某个节点 在二叉树中寻找值为 x 的节点可以通过递归方法来实现。本质上这是一种深度优先搜索DFS策略。思路是从根节点开始先检查根节点的值是否等于 x如果是就返回当前节点。如果不是就先在左子树中递归查找如果左子树中找到了就直接返回结果如果左子树中没有找到再在右子树中查找。如果整棵树都没找到最终返回 NULL 表示不存在值为 x 的节点。 TreeNode* TreeFind(TreeNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;TreeNode* tmp1 TreeFind(root-left, x);TreeNode* tmp2 TreeFind(root-right, x);if (tmp1){return tmp1;}if (tmp2){return tmp2;}return NULL;
}假设我们寻找3 1/ \2 4/ / \3 5 6开始于根节点值为1首先检查根节点的值它是1不等于我们要找的值3。 递归搜索左子树值为2的节点进入下一层移至节点值2检查这个节点它也不是我们要找的值。 递归搜索左子树的左子树值为3的节点继续递归进入下一层移至节点值3这个节点是我们要找的因为它的值等于3。函数返回这个节点的地址
这里简单解释一下这段代码的含义
if (tmp1) {return tmp1;
}
if (tmp2) {return tmp2;
}
return NULL;tmp1和tmp2分别是对当前节点的左子树和右子树递归执行TreeFind函数后得到的结果。tmp1是左子树中查找的结果而tmp2是右子树中查找的结果。 if (tmp1)检查左子树递归查找的结果。如果tmp1不为NULL这意味着在左子树中找到了值为x的节点因此直接返回该节点。这里的if (tmp1)、 如果tmp1为NULL表明左子树中没有找到目标节点程序将继续检查tmp2即右子树递归查找的结果。同理如果tmp2不为NULLif (tmp2)意味着在右子树中找到了值为x的节点函数则返回该节点。 如果两个条件判断if (tmp1)和if (tmp2)都不成立即tmp1和tmp2都为NULL表示在当前节点的左右子树中都没有找到值为x的节点那么函数最终返回NULL表示查找失败。
4.用前序遍历建造一个二叉树
在上述铺垫后我们来做一个题 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 这里的#可以当做前面讲的NULL
首先我们定义函数;
TreeNode* CreatTree(BTDataType* a, int *pi);字符串ABD##E#H##CF##G##按照前序遍历构建二叉树其中’A’是根节点继续按照根-左-右的顺序解析字符串。A的左子节点是BB的左子节点是D。D的左右子节点都是空##, 这表示’D’是叶子节点。回到B’B的右子节点是E。E的左子节点为空由#表示右子节点是’H’。H’的左右子节点也都是空。回到根节点A它的右子节点是C。C的左子节点为空右子节点是F。F’的左右子节点都是空。最后C的右子节点是G同样G’的左右子节点都是空
得到的树结构如下 A/ \B C/ \ \
D E F\ \H G代码如下
TreeNode* CreatTree(char* a, int* pi)
{if (a[*pi] #){*pi;return NULL;}TreeNode* root (TreeNode*)malloc(sizeof(TreeNode));if (root NULL){perror(malloc fail);exit(-1);}root-data a[(*pi)];root-left CreatTree(a, pi);root-right CreatTree(a, pi);return root;
}这里TreeNode的数据类型需要从int 改为char我们将typedef后面的int修改即可
typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinartTreeNode* left;struct BinartTreeNode* right;
}TreeNode;5.二叉树的销毁
void DestroyTree(TreeNode* root) {if (root NULL) {return;}DestroyTree(root-left); // 销毁左子树DestroyTree(root-right); // 销毁右子树free(root); // 释放当前节点
}当你调用DestroyTree并传入树的根节点时函数首先检查是否给定的节点在最初的调用中这是根节点为NULL。如果不是它会递归地调用自身来销毁左子树和右子树。完成这些递归调用之后返回到最初的调用层次时它会释放根节点本身占用的内存。
检查root是否为NULL。如果是说明已经处理到了空子树函数返回。递归调用DestroyTree(root-left);销毁左子树。这将遍历到最左侧的叶子节点沿途经过的每个节点的左子树都将被先递归调用DestroyTree处理。递归调用DestroyTree(root-right);销毁右子树。每个节点的右子树同样会经历相同的递归处理。最后经过左子树和右子树的递归处理后回到当前的节点并使用free(root);释放掉该节点占用的内存。 尽管根节点被销毁但原始root变量本身在函数返回后仍然存在只是它现在成为了一个悬空指针。为了安全起见调用完DestroyTree之后应该手动将root设置为NULL 例如
int main() {TreeNode* root FCreatTree()DestroyTree(root);root NULL; return 0;
}如果不想手动设置为NULL只用一个DestroyTree函数来解决这里意味着我们需要在函数里面实现置空过程意味着我们要修改指针则需要传参二级指针
void DestroyTree(TreeNode** root) {if (*root NULL) {return;}DestroyTree(((*root)-left));DestroyTree(((*root)-right));free(*root);*root NULL; // 将调用方的根节点指针置为NULL
}6.链式二叉树的层序遍历 层序遍历Level Order Traversal是指按照从上到下、从左到右的顺序访问二叉树的每个节点。这种遍历方式可以保证二叉树中每个节点的访问顺序正好对应其在树中的层次和位置。层序遍历通常借助于队列这一数据结构来实现。 所以要想实现层序遍历首先得有队列的函数在前几节内容中我们已经对其讲解这里直接引用其代码
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size0;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;if (pq-ptail NULL){pq-ptail pq-phead newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}
void QueuePop(Queue* pq) {assert(pq); // 确保 pq 不是 NULLif (pq-phead NULL) return; // 如果队列为空则没有元素可以弹出QNode* temp pq-phead; // 临时保存队列头部节点的地址以便后续释放内存pq-phead pq-phead-next; // 更新头指针指向下一个节点free(temp); // 释放原头节点占据的内存temp NULL;if (pq-phead NULL) { // 如果弹出之后队列变为空则尾指针也要更新为 NULLpq-ptail NULL;}pq-size--; // 更新队列大小
}
QDataType QueueFront(Queue* pq)
{assert(pq); // 确保 pq 不是 NULLassert(pq-phead ! NULL);return pq-phead-val; }
QDataType QueueBack(Queue* pq) {assert(pq ! NULL); // 确保队列指针不为NULLassert(pq-ptail ! NULL); // 确保队列不为空即队尾指针不为NULL// 返回队列尾部元素的值return pq-ptail-val;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL;
}
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead pq-ptail NULL;pq-size 0;
}队列在层序遍历中的使用是由于其先进先出First In First Out, FIFO的特性这保证了树的节点能够按照从上到下、从左到右的顺序进行访问这里解释为什么要用队列进行层序遍历
在层序遍历过程中我们首先访问根节点然后是根节点的子节点从左到右接着是子节点的子节点以此类推。队列能够保证节点的访问顺序正好符合这一层级结构因为我们总是先将左子节点加入队列然后是右子节点。当从队列中取出一个节点时它的子节点已经按照正确的顺序排在后面
实现步骤
初始化创建一个队列将根节点入队循环执行以下操作直到队列为空将队头的节点出队并访问该节点 如果该节点有左子节点则将左子节点入队如果该节点有右子节点则将右子节点入队
我们思考一下这里队列里面放的是什么节点还是节点的值
这里放入的是节点如果只放入节点的值则找不到下一个节点所以这里我们需要修改队列的typedef类型
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;接下来实现代码
void LevelOrder(TreeNode* root)
{Queue q;QueueInit(q);if (root ! NULL){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);}QueueDestroy(q);
}我们来进行分析 以最开始的那棵树为例子 1/ \2 4/ / \3 5 6让我们展开遍历的过程
开始时队列状态1取出1打印1加入1的左子节点2和右子节点4队列状态2, 4取出2打印2加入2的左子节点3队列状态4, 3取出4打印4加入4的左子节点5和右子节点6队列状态3, 5, 6取出3打印3队列状态5, 6取出5打印5队列状态6取出6打印6队列空
打印顺序1, 2, 4, 3, 5, 6。
7.判断是否为完全二叉树
判断一棵树是否为完全二叉树可以利用层序遍历的思想。完全二叉树的特点是除了最后一层外每一层都是完全填满的且最后一层的所有节点都集中在左侧。在层序遍历过程中如果遇到了一个节点其有右子节点而无左子节点那么这棵树肯定不是完全二叉树另外如果遇到了一个节点并非左右子节点都有那么所有接下来遍历到的节点都必须是叶子节点。
我们再原有层序遍历代码上修改即可
bool BinaryTreeComplete(TreeNode* root)
{Queue q;QueueInit(q);if (root ! NULL){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){QueuePop(q);return false;}}QueueDestroy(q);return true;
}第一部分将所有节点包括空节点按层序添加到队列中
首先初始化一个队列 q。如果根节点不为空则将根节点添加到队列中。接下来进入一个循环直到队列为空。在这个循环中 从队列中弹出一个节点记为 front。如果 front 是 NULL即遇到了第一个空节点则退出循环。这是因为在完全二叉树中一旦按层序遍历遇到空节点其后的所有节点也应该是空的。如果 front 非空将其左右子节点即使是空的添加到队列中。这样做是为了保证即使是空节点也按照层序顺序排列。
第二部分检查队列中剩余的所有节点是否都是空的
退出第一部分的循环后理论上队列中剩下的所有节点应该都是空节点如果是完全二叉树的话。因此接下来的循环会遍历队列中剩余的所有节点
从队列中弹出一个节点记为 front。 如果 front 是非空的说明在遇到第一个空节点之后还有非空节点这违反了完全二叉树的性质。因此函数返回 false。 如果循环顺利结束没有遇到任何非空节点说明这棵树是一棵完全二叉树函数返回 true。
本节内容到此结束感谢大家阅读
