网站建设技能,搜狗站长工具综合查询,百度seo关键词工具,百度宣传做网站多少钱#x1f6a9;纸上得来终觉浅#xff0c; 绝知此事要躬行。 #x1f31f;主页#xff1a;June-Frost #x1f680;专栏#xff1a;数据结构 #x1f525;该文章主要讲述二叉树的递归结构及分治算法的思想。 目录#xff1a; #x1f30d;前言#xff1a;#x1f30d;… 纸上得来终觉浅 绝知此事要躬行。 主页June-Frost 专栏数据结构 该文章主要讲述二叉树的递归结构及分治算法的思想。 目录 前言 二叉树的遍历 前序遍历 中序遍历 后续遍历 分治 一些例子 ❤️ 结语 前言 为了实现二叉树的基本操作以及更好的了解二叉树的结构先手动创造一个链式二叉树。
#includestdio.h
#includestdlib.htypedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;int val;
}BTNode;BTNode* BuyNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);exit(-1);}node-left NULL;node-right NULL;node-val x;return node;
}
int main()
{//创建节点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 node3;node2-left node4;node3-left node5;node3-right node6;node4-right node7;return 0;
}创建出来的结构 创建出来的这棵二叉树将为后续的遍历和分治做准备. 二叉树的遍历 遍历操作可以快速熟悉二叉树的递归结构二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 如果二叉树不为空树就需要看成三部分即 根节点根节点的左子树、根节点的右子树这样就满足了递归结构 由于二叉树满足递归结构所以按照规则二叉树的遍历有前序/中序/后序的递归结构遍历 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。即顺序为根 、左子树、右子树。 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。即顺序为左子树、右子树、根。 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。即顺序为左子树、右子树、根。
按照创建的二叉树遍历的顺序为 前序遍历 代码实现
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}动图展示
前序遍历递归图解 中序遍历 代码实现
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);
}动图展示 注意对于这个动图的白色箭头为递归调用和结束红色箭头是右子树部分调用结束之后打印节点的时机。 分治 分治思想是一种解决问题的方法本质是一种管理它的核心思想是将一个复杂的问题分解成若干个较小的子问题然后分别解决这些子问题最后将子问题的解合并得到原问题的解。这种思想在计算机科学、数学和工程领域都有广泛应用。 分治思想的优点在于它可以有效地减少问题的复杂度提高算法的效率。同时它还可以提高代码的可读性和可维护性因为可以将问题分解成更小的部分更容易理解和修改。 一些例子
① 二叉树的节点个数 节点情况 如果是空节点返回0。如果不是空节点则返回该节点的左子树的节点数右子树的节点个数1(自己这个节点)。 int BinaryTreeSize(BTNode* root)
{return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
} 这个代码的访问顺序其实就是后序遍历。
② 二叉树叶子节点个数 节点情况 如果是空返回0。如果是叶子返回1。不是叶子也不是空就返回该节点左子树的叶子数 右子树的叶子数。 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);
}③ 二叉树第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);
}❤️ 结语 文章到这里就结束了如果对你有帮助你的点赞将会是我的最大动力如果大家有什么问题或者不同的见解欢迎大家的留言~
