品牌网站设计制作服务公司,烟台海阳市专业做网站,17网站一起做网店优势与劣势,企业网站轮播图怎么做文章目录 一、前置说明二、二叉树的遍历 1. 前序、中序以及后序遍历 1.1 前序遍历 1.2 中序遍历 1.3 后序遍历 2. 层序遍历 三、常见接口实现 0. 递归中的分治思想 1. 查找与节点个数 1.1 节点个数 1.2 叶子节点个数 1.3 第k层节… 文章目录 一、前置说明二、二叉树的遍历 1. 前序、中序以及后序遍历 1.1 前序遍历 1.2 中序遍历 1.3 后序遍历 2. 层序遍历 三、常见接口实现 0. 递归中的分治思想 1. 查找与节点个数 1.1 节点个数 1.2 叶子节点个数 1.3 第k层节点个数 1.4 查找值为x的节点 2. 二叉树的创建与销毁 2.1 创建 2.2 销毁 总结 一、前置说明 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。 注意下述代码并不是创建二叉树的方式真正创建二叉树方式文章末尾处会进行讲解。 typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;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);node1-_left node2;node1-_right node4;node2-_left node3;node4-_left node5;node4-_right node6;return node1;
}二、二叉树的遍历 1. 前序、中序以及后序遍历 学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的所有节点进行访问。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历区别为访问根的顺序不同。 前序遍历 访问顺序为根左子树右子树中序遍历访问顺序为左子树根右子树后序遍历访问顺序为左子树右子树根 1.1 前序遍历
void BinaryTreePrevOrder(BTNode* root)
{//为空if (root NULL){printf(N );return ;}//不为空打印节点值继续找左子树找完后找右子树printf(%d , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}1.2 中序遍历
void BinaryTreeInOrder(BTNode* root)
{//为空if (root NULL){printf(N );return;}//左BinaryTreeInOrder(root-left);//根printf(%d , root-data);//右BinaryTreeInOrder(root-right);
}1.3 后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(N );return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%d , root-data);
}2. 层序遍历 除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 三、常见接口实现 0. 递归中的分治思想 在下面的接口实现中我们使用递归实现分治思想将大问题拆分成多个子问题处理我们要注意如何拆分子问题 和 表达递归的结束条件。 递归分为递推和回归。我们可以画递推展开图假想递推到底的情况思考分析回归条件可代入回归检验是否符合。分治将问题抽象分为多个子问题分别解决用递归实现分治 一路递推到底处理完第一个子问题回归在回归过程中处理之前未处理的子问题。子问题可能会被处理多次但每个子问题的处理次数总和一定是相同的只是处理先后的不同本质是将问题的核心基础步骤抽象出来使用递归方式重复处理最终达成目的。 1. 查找与节点个数 1.1 节点个数 子问题分治节点个数 左子树节点个数 右子树节点个数 递归结束返回条件 空 返回 0不为空 返回1 int BinaryTreeSize(BTNode* root)
{//如果根为空就返回0否则返回左子树与右子树节点数和return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}1.2 叶子节点个数 子问题分治节点个数 左子树叶子节点个数 右子树叶子节点个数 递归结束返回条件 空 返回 0叶子 返回1 int BinaryTreeLeafSize(BTNode* root)
{//单独判断空树if (root NULL){return 0;}//如果左子树和右子树都不为空说明为叶子if (!root-left !root-right){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}1.3 第k层节点个数 子问题分治第k层节点个数 第k-1层的左子树节点个数 第k-1层的右子树节点个数 递归结束返回条件 空 返回 0不为空且为k层 返回1 int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;//不为空且为k层返回1if (k 1)return 1;//k 1 说明为k层不为则继续向下递推return BinaryTreeLevelKSize(root-left, k-1) BinaryTreeLevelKSize(root-right, k-1);
}1.4 查找值为x的节点 子问题分治查找 查找左子树 查找右子树 递归结束返回条件 空 返回 0找到 返回节点地址 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;
}2. 二叉树的创建与销毁 2.1 创建 子问题分治创建 创建左子树 创建右子树 递归结束返回条件 空‘#’ 返回NULL非空 创建节点并初始化 // 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
// a为数组pi为 外部中标识数组下标变量的 指针
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (a[*pi] #){*pi; //下标后移return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL){perror(malloc fail);exit(-1);}root-data a[*pi];root-left BinaryTreeCreate(a, n, *pi);root-right BinaryTreeCreate(a, n, * pi);
}2.2 销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory((*root)-left);free(*root);BinaryTreeDestory((*root)-right);free(*root);free(*root);*root NULL;
}总结 知识框架可看文章目录。 本文讲解了二叉树的链式存储结构的相关知识递归和分治思想十分抽象需要读者自行画递归展开图理解多练习培养出自己的抽象能力。 文章中有什么不对的丶可改正的丶可优化的地方欢迎各位来评论区指点交流博主看到后会一一回复。
