asp网站模板下载,国内外知名建设设计网站,wordpress 礼物说模板,设计网络网站有哪些功能写在前面
书接上文#xff1a;【数据结构】树——顺序存储二叉树
本篇笔记主要讲解链式存储二叉树的主要思想、如何访问每个结点、结点之间的关联、如何递归查找每个结点#xff0c;为后续更高级的树形结构打下基础。不了解树的小伙伴可以查看上文 文章目录 写在前面 一、链…写在前面
书接上文【数据结构】树——顺序存储二叉树
本篇笔记主要讲解链式存储二叉树的主要思想、如何访问每个结点、结点之间的关联、如何递归查找每个结点为后续更高级的树形结构打下基础。不了解树的小伙伴可以查看上文 文章目录 写在前面 一、链式二叉树的定义 二、链式二叉树的遍历2.1、前序、中序以及后序遍历前序遍历的代码实现中序遍历的代码实现后序遍历的代码实现 三、链式二叉树的元素个数代码实现 四、链式二叉树的高度代码实现 五、二叉树第k层节点个数代码实现 六、二叉树查找值为x的节点代码实现 七、链式存储二叉树的OJ 7.1、单值二叉树代码实现 八、二叉树的创建和销毁代码实现 一、链式二叉树的定义 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。(二叉树有二叉链和三叉链两种表示方式本文主要讲解二叉链。二叉链一般指孩子表示法三叉连指孩子双亲表示法这两种方式是二叉树最常见的表示方式虽然还有孩子兄弟表示法该中表示方式本质也是二叉链) 链式存储的结构体
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* _pLeft;// 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* _pParent; // 指向当前节点的双亲struct BinTreeNode* _pLeft;// 指向当前节点左孩子struct BinTreeNode* _pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点值域
};上面的结构体就成功创建出链式存储的二叉树 二、链式二叉树的遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。( 不才默认左子树先运行后再运行右子树再每次遍历先都需要规定一下左右子树的先后顺序。) 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
2.1、前序、中序以及后序遍历
前序、中序以及后序遍历的思想都是相同的只是根节点访问的先后顺序不同我们这里以前序遍历为例子 1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 程序由上到下运行应当先访问当前值后访问左右结点。 输出下图中的二叉树使用前序遍历的结果(结果需要包含NULL) 结果为123NULLNULLNULL45NULLNULL6NULLNULL
我们画图分析使用微元法把每一个结点都逻辑细分为一棵小树根结点与左右结点)在开始根节点1时对应的左结点2和右结点4。
之后先输出根结点的值1后访问左结点
使用微元法把2结点微元成一棵小树
之后先输出根结点的值2此时结果为1,2。后访问左结点
使用微元法循环上述操作
之后先输出根结点的值3此时结果为1,2,3。后访问左结点
此时3的左节点使用微元法循环上述操作后可得下图
之后先输出根结点的值NULL此时结果为1,2,3,NULL。之后因为结点为NULL所以结束访问返回到结点3。
此时结点3中已经完成完成了左结点的范围写在就需要范围右结点了 我们依旧使用微元法细分结点3的右结点可得下图
之后先输出根结点的值NULL此时结果为1,2,3,NULL,NULL。之后因为结点为NULL所以结束访问返回到结点3。
此时结点3的所以结点已经完成遍历返回到结点2中结点2已经完成当前结点与左结点值的遍历接下来进入右结点值遍历中 使用微元法循环上述操作直到整棵树的值遍历一便即可得到结果123NULLNULLNULL45NULLNULL6NULLNULL
上面我们手搓的思想与递归简直一毛一样那么我们在代码实现中就可以使用递归来解决前序遍历。
根据我们手搓的画图最终我们可以得出下图 前序遍历的代码实现
递归的思想就是大事化小对于递归方面有问题的小伙伴可以看不才写的递归笔记【C语言】函数递归
代码实现
void PreOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}根据上面手搓推理的逻辑继续使用微元法来创建递归实现前序遍历 在上图这颗微元树中
首先需要判断这个树是否是空树判断是否空树就是判断这个结点是否为NULL如果结点是NULL就打印NULL并且返回。判断这个结点不为空后因为是前序遍历这时候就先打印根结点的值root-val。打印完成后就访问左孩子结点之后再访问右孩子结点完成。在判断是否空树的条件中恰好判断了结点为空的情况这样也完成了我们访问左孩子或右孩子遇到结点为NULL需要返回的情况。
内存中的栈增情况
中序遍历的代码实现
与前序遍历的实现逻辑一模一样只是执行根结点值打印时机不同。
void InOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}后序遍历的代码实现
与前序遍历的实现逻辑一模一样只是执行根结点值打印时机不同。
void PostOrder(BTNode* root) {if (root NULL) {printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}三、链式二叉树的元素个数
求链式二叉树的元素个数我们还是先使用微元法来手搓计算。 计算下面二叉树有多少个元素 我们使用微元法先拆分一颗小树来分析如何计算 首先根节点不为NULL说明该根结点是有效结点但是在这个结点中不能得到左孩子与右孩子右多少个元素个数。让左右孩子返回它有多少个元素结点。这样在这个小树中我们才能返回这棵树有多少个结点。 所以又需要进入左右孩子中去判断它是否是有多少个结点(如下图) 此时我们还是不知道左右孩子各有多少个结点我们再进入到左右孩子中(如下图)。 此时我们还是不知道左右孩子各有多少个结点我们再进入到左右孩子中。此时3的左节点使用微元法循环上述操作后可得下图 这时结点为NULL说明该结点不是有效结点返回0。 此时3结点就得到了左孩子结点的值为0这时就需要进入右孩子中让右孩子返回元素个数
同理右孩子还是空返回0此时3结点得知左右孩子节点个数。
在3节点中左孩子返回结果 右孩子返回结果 再加上自身是有效结点1就得到该结点的元素个数左右元素个数为03节点是有效节点所以返回1 节点2中就得到了左节点的元素个数此时在按照上面的逻辑得到右节点个数为0(如下图) 在2节点中左元素个数为1右元素个数为02节点是有效节点所以返回2(如下图)
根据上面的逻辑我们可以轻松算出1结点的右子树元素个树为3个。
此时1结点中左孩子返回结果为2 右孩子返回结果为3 再加上自身是有效结点1就得到该结点的元素个数为6。
虽然也是遍历求解但是我们这里是让每个底层结点自己统计完成后逐步向上层返回结点个数 。
代码实现
int BinaryTreeSize(BTNode* root) {if (root NULL) {return 0;}return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}如果是空结点就返回0使用微元法让左右结点自己返回有多少结点再加上自身结点就是该小树的元素个数 四、链式二叉树的高度
求链式二叉树的高度还是使用微元法逻辑与求个数相似。 手搓下面二叉树的高度 我们使用微元法先拆分一颗小树来分析如何计算 在上图小树中我们知道根节点不是空结点这时候需要判断我们需要判断左右结点哪个孩子的高度高之后我们在最高的子结点高度加上根结点的高度(1)即可得到这个小树的高度我们直接微元到原二叉树左子树的最底层中(如下图) 在上图中左右孩子的高度是0但次结点时有效结点所以返回结果是01。(最高的子结点高度加上根结点)
此时上层结点2就接收到左结点的高度是1易得右结点的高度是0。 之后最高的子结点高度(1)加上根结点的高度(1)返回2(如下图) 根据上述逻辑我们易的。1结点的右孩子返回高度是2(如下图) 这时两个孩子的高度都为2所以该二叉树的高度为2 1 3。
代码实现
int TreeHeight(BTNode* root) {if (root NULL) {return 0;}int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}
在递归中返回的数据需要进行处理的返回值都必须进行保存这样可以避免大量重复的递归。每一次都需要保存左右结点的高度这样就不需要多次重复递归即可判断出左孩子与右孩子哪个高度高。 五、二叉树第k层节点个数
同样使用微元法求出第K层中的节点个数。 手搓下面二叉树中第3层的高度 首先我们需要有一个变量i来记录我们当前所在的层次是否在所对于的K层中我们使用微元法先拆分一颗小树来分析如何计算 每进入一层i变量就--直到i变量为1时说明当前的层次是正确的。但此时i 3这时候就需要进入根节点的左右孩子中让左右孩子告诉根节点i1是有多少个节点 首先进入到左孩子中此时i2还是没进入到对于的节点再次进入左右孩子中此时发现i1这时候左孩子为3是有效节点返回1右孩子NULL不是有效节点。 这时候节点2就需要把左右孩子返回的数据相加后返回。 同理可得出右子树返回结果为:2。 即的出第3层的元素个数为:3。
代码实现
int TreeKLeve(BTNode* root,int k) {if (root NULL) {//节点为空时返回0return 0;}if (k 1) { //节点不为空且层次为1时返回1return 1;}int lnum TreeKLeve(root-left, k - 1);//记录左孩子在K层时有多少个节点int rnum TreeKLeve(root-right, k - 1);//记录右孩子在K层时有多少个节点return lnum rnum;//返回左孩子在K层中节点 右孩子在K层中节点。即为当前根下K层中所有节点个数
} 在递归中返回的数据需要进行处理的返回值都必须进行保存这样可以避免大量重复的递归。 六、二叉树查找值为x的节点
相对简单但是代码逻辑中会有坑 在下面二叉树中找到值为5的节点并且返回该节点 只需要遍历找到值为5的节点之后返回即可逻辑与求元素个数大差不差。
代码实现
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (root NULL) {return NULL;}if (root-val x) {return root;}BTNode* lren BinaryTreeFind(root-left,x);if (lren)return lren;BTNode* rren BinaryTreeFind(root-right,x);if (rren)return rren;return NULL;
}代码实现逻辑不断的遍历往下走直到为空返回空或者找到对应的值返回该节点。如果既不为空也不是相对应的值则接着往左右孩子中寻找X值。如果左右孩子中都没有找到所对应的X值则返回空值。若找到了所对应的X值。则返回对应的节点。因为递归是函数的栈增return不能直接返回到函数调用的阶段需要一步步返回。为了确保每次返回都是所对应的节点我们需要进行判断每次返回的节点是否为空。如果不为空则返回所找到的节点。一旦涉及到需要对递归值进行判断的都需要进行储存。
如果不进行判断返回则在下一次函数递归返回中就直接返回空。(错误案例)
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {if (root NULL) {return NULL;}if (root-val x) {return root;}return NULL;
}七、链式存储二叉树的OJ 7.1、单值二叉树
如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时才返回 true否则返回 false。 输入[1,1,1,1,1,null,1] 输出true 本题不可使用遍历。这里我们使用微元法判断一下我们这么确认每个节点都是相同的 使用根节点val与左右孩子的val值分别比较即可判断出这个节点是否与左右孩子的值相同。 但是我们也不知道左右孩子的全部节点是否相同但是如果此时不满住条件我们直接可以判断为假所以我们先对该节点的左右孩子进行判断。 左节点判断结果不为假继续判断右结点 此时右结点也不为假所以我们需要递归往下判断左右孩子的节点是否为假。如此递归当遇到节点为NULL时返回true则说明到叶子节点都不为假一旦为假直接返回。
代码实现
bool isUnivalTree(struct TreeNode* root) {if (root NULL) { // 基本情况如果当前节点为空返回 true空树被认为是单值树return true;}// 检查左子节点是否存在且值不同if (root-left ! NULL root-val ! root-left-val) {return false;}// 检查右子节点是否存在且值不同if (root-right ! NULL root-val ! root-right-val) {return false;}// 递归检查左子树和右子树return isUnivalTree(root-left) isUnivalTree(root-right);
}相似的逻辑我们试试下面的题目
100. 相同的树101. 对称二叉树572. 另一棵树的子树 八、二叉树的创建和销毁 通过前序遍历的数组123NULLNULLNULL45NULLNULL6NULLNULL。构建二叉树 首先我们需要把前序遍历的数组还原为二叉树还原过程 由上图可知前序遍历的数组的还原过程在数组下标1我们就进行左孩子的赋值当左孩子赋值NULL后程序就返回节点之后进行右结点的赋值当右节点也赋值完成后返回节点地址。
代码实现
typedef char BTDataType;
typedef struct BinaryTreeNode
{struct BinTreeNode* left;// 指向当前节点左孩子struct BinTreeNode* right; // 指向当前节点右孩子BTDataType val; // 当前节点值域}BTNode;
//前序递归创建二叉树
BTNode* CreateTree(char* arr, int* pi) {if (arr[*pi] #) {(*pi);return NULL;}BTNode* node (BTNode*)malloc(sizeof(BTNode));node-val arr[(*pi)];node-left CreateTree(arr, pi);node-right CreateTree(arr, pi);return node;
}void test2() {char arr[] { 1,2,3,#,#,#,4,5,#,#,6,#,# };//#代表NULLint i 0;BTNode* node CreateTree(arr, i);
}我们画部分的递归展开图以便理解 以上就是本章所有内容。若有勘误请私信不才。万分感激 如果对大家有帮助的话就请多多为我点赞收藏吧~~~
ps:表情包来自网络侵删
