在网站建设论文的基本分析,小程序和公众号的关系,网站从服务器上下载文件,wordpress 主题 星球又见面了#xff0c;小伙伴们。今天我们继续来学习二叉树#xff0c;今天的内容相对来说比较容易理解#xff0c;前提是需要你们自己动手画图才会好理解。眼过千遍不如手过一遍。所以小伙伴们要多动手哦。直接开始今天的学习吧
1.二叉树链式结构的实现
1.1 前置说明 在学习…
又见面了小伙伴们。今天我们继续来学习二叉树今天的内容相对来说比较容易理解前提是需要你们自己动手画图才会好理解。眼过千遍不如手过一遍。所以小伙伴们要多动手哦。直接开始今天的学习吧
1.二叉树链式结构的实现
1.1 前置说明 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在我们对二叉树结构掌握还不够深入为了降低学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);return NULL;}node-data x;node-left NULL;node-right NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(7);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;node5-left node7;return node1;
}注意上述代码并不是创建二叉树的方式真正创建二叉树方式后序详解重点讲解。 我们前面学过二叉树的概念是 1. 空树 2. 非空根节点根节点的左子树、根节点的右子树组成的 从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。 任何一个二叉树都可以看成有3个部分组成根左子树右子树。每个子树又可以分成上述3个部分一直分到它们的左右子树都为空时停止。 1.2 二叉树的遍历 1.2.1前序、中序以及后序遍历 学习二叉树结构最简单的方式就是遍历。所谓 二叉树遍历 (Traversal) 是按照某种特定的规则依次对二叉 树中的节点进行相应的操作并且每个节点只操作一次 。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有 前序 / 中序 / 后序的递归结构遍历 1. 前序遍历 (Preorder Traversal 亦称先序遍历 )—— 访问根结点的操作发生在遍历其左右子树之前。 2. 中序遍历 (Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中间。 3. 后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。 由于被访问的结点必是某子树的根 所以 N(Node 、 L(Left subtree 和 R(Right subtree 又可解释为 根、根的左子树和根的右子树 。 NLR 、 LNR 和 LRN 分别又称为先根遍历、中根遍历和后根遍历。 下面来看一个二叉树小伙伴们可以先试试它的前序中序后序都是什么。 第一次写这个的时候小伙伴们可能还搞不懂就是直到左右子树都是空的时候才会停止只要还能继续往下走就要一直继续走。记住这句话应该就没有问题了。建议一定要自己画图才能理解其中的意思。 来看代码吧如果自己想在电脑上试一下的话要把开头给的代码补上才完整 //前序
void PrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}//中序
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}//后序
void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}int main()
{BTNode* root CreatBinaryTree();PrevOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);
} 前序遍历结果 1 2 3 4 5 6 中序遍历结果 3 2 1 5 4 6 后序遍历结果 3 2 5 6 4 1 总体的思想就是递归思想我会画一个前序的递归图帮助小伙伴们更好的理解其它的遍历小伙伴们可以自己试一下哦。 1.2.2 层序遍历 层序遍历 除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1 层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第 2 层 上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。不能用递归来表示 代码实现 void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%d , front-data);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);}printf(\n);QueueDestroy(q);
} 如果想添加以前写的队列的代码的话可以把队列文件的.c和.h 文件复制然后添加到二叉树文件的里面如图所示 添加完之后需要对头文件做一些修改 2.求二叉树的各种节点问题 2.1计算节点个数 计算节点个数有2个方法 方法1把size定义成全局变量然后遍历整棵数如果不空的话size int size 0;
void BTreeSize(BTNode* root)
{if (root NULL)return 0;size;BTreeSize(root-left);BTreeSize(root-right);
} BTreeSize(root);//方法1
printf(BTreeSize:%d\n, size); 方法2分治法。左子树右子树11代指的是根 举个例子假如学校校长想要统计学生个数那么是不是校长先给院长下达命令然后院长在给辅导员下达命令最后辅导员再给各班班长下达命令让班长统计人数然后依次上报最后校长就知道学生有多少人了。递归思想就是这样 int BTreeSize(BTNode* root)
{/*if (root NULL){return 0;}return BTreeSize(root-left) BTreeSize(root-right) 1;*/return rootNULL?0: BTreeSize(root-left) BTreeSize(root-right) 1;
}printf(BTreeLeafSize:%d\n, BTreeLeafSize(root)); 2.2 计算叶子节点个数 这个我们应该很好想到就是当左子树和右子树为空的时候就是到叶子节点了。递归的终止条件有2个。当树为空时返回0当左子树和右子树都为空的时候返回1 int BTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return BTreeLeafSize(root-left) BTreeLeafSize(root-right);
} printf(BTreeLeafSize:%d\n, BTreeLeafSize(root)); 2.3 计算二叉树高度 二叉树的高度由最长路径决定的哪个路线最长树的高度就是多少 先定义2个变量分别计算左右子树的长度哪个树长树的高度就是它。 int BTreeHight(BTNode* root)
{if (root NULL)return 0;int leftHight BTreeHight(root-left);int rightHight BTreeHight(root-right);return leftHight rightHight ? BTreeHight(root-left) 1: BTreeHight(root-right)1;} 当然也可以这样写不过这种写法的效率非常低当数据量非常大的时候就会浪费很大的时间 int BTreeHight(BTNode* root)
{if (root NULL)return 0;return BTreeHight(root-left) BTreeHight(root-right) ? BTreeHight(root-left) 1 : BTreeHight(root-right) 1;
} 2.4 计算第K层节点个数 可以转换成左子树的第k-1层和右子树的第k-1层。递归的结束条件是k1且节点不为空。 int BTreeLevelKSize(BTNode* root, int k)
{assert(k);if (root NULL)return 0;if (k 1)return 1;return BTreeLevelKSize(root-left, k - 1) BTreeLevelKSize(root-right, k - 1);
} printf(BTreeLevelKSize:%d\n, BTreeLevelKSize(root,3));2.5 查找值为x的节点
我先展示一下经典的错位写法当然我开始也是这样想的
BTNode* BTreeFind(BTNode* root, BTDataType x)//错误写法找到还要返回上一层
{if (root NULL)return NULL;if (root-data x)return root;BTreeFind(root-left, x);BTreeFind(root-right, x);}
错误的原因就是找到值的话不是直接退出递归而是要返回上一层一直到开头的地方。其实只要自己画一个递归展开图就知道是怎么回事了。讲递归的时候我们就知道是有去有回不是直接结束
正确思路就是定义变量要记录找到的值然后直接返回就行。
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BTreeFind(root-left, x);if (ret1)return ret1;BTNode* ret2 BTreeFind(root-right, x);if (ret2)return ret2;return NULL;
}
2.6 判断是否为完全二叉树
这时候就会有人想可不可以用节点个数来判断是不是完全二叉树只要在范围之内就是完全二叉树那么这种想法是错误的这个想法只能用来判断是不是满二叉树。我们已经知道完全二叉树的特征是最后一层可以不满但叶子节点必须是连续的所以说用节点个数来判断是行不通的。 具体实现如下我们可以通过层序遍历来判断只要队列不为空时就继续往下走 代码如下
bool BTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!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;} 好了小伙伴们今天的学习就到这里下一节我们来练习一些二叉树有关的习题关于二叉树的初级部分就学完了。高级部分要等到我们学完C后才能更好的理解。感谢大家的阅读。
