淘宝客没有网站怎么做,wordpress 分类 别名,网站一般字体,开发公司网站公司专栏引入 哈喽大家好#xff0c;我是野生的编程萌新#xff0c;首先感谢大家的观看。数据结构的学习者大多有这样的想法#xff1a;数据结构很重要#xff0c;一定要学好#xff0c;但数据结构比较抽象#xff0c;有些算法理解起来很困难#xff0c;学的很累。我想让大家…专栏引入 哈喽大家好我是野生的编程萌新首先感谢大家的观看。数据结构的学习者大多有这样的想法数据结构很重要一定要学好但数据结构比较抽象有些算法理解起来很困难学的很累。我想让大家知道的是数据结构非常有趣很多算法是智慧的结晶我希望大家在学习数据结构的过程是一种愉悦的心情感受。因此我开创了《数据结构》专栏在这里我将把数据结构内容以有趣易懂的方式展现给大家。 1.二叉树的链式存储结构
前面我们说过顺序存储结构一般只适用于完全二叉树既然顺序存储适应性不强我们既要考虑链式存储结构了。二叉树每个节点最多有两个孩子所以为它设计一个数据域和两个指针域是比较自然的想法 我们称这样的链表为二叉链表。节点结构图如下所示 其中data是数据域leftchild和rightchild都是指针域分别存放指向左孩子和右孩子的指针下面是二叉链表的节点结构定义代码
typedef struct BinaryTreeNode
{TDataType data;struct TreeNode* leftchild;struct TreeNode* rightchild;
}BTNode; 结构示意图如下 就如同我们在树的存储结构中讨论的一样如果有需要还可以增加一个指针指向其双亲的指针域那样就称之为三叉链表后续在红黑树时会提到这里就不细讲了。
2.二叉树的遍历 二叉树的遍历是指从根节点出发按照某种次序依次访问二叉树中的所有节点使得每一个节点被访问一次且仅被访问一次。这里有两个关键词访问和次序。访问其实是根据实际需要来确定具体做什么比如对某个节点进行相关计算、输出打印等。二叉树的遍历次序不同于线性结构最多也就是从头到尾、循环、双向等简单的遍历方式。树的节点之间不存在唯一的前驱和后继关系在访问一个节点后下一个访问的节点面临着不同的选择。就像我们高考填报志愿要面临着去哪个城市、哪所大学、具体专业等选择由于选择的方式不同遍历的次序就完全不同了。
二叉树的遍历方式可以有很多种如果我们限制了从左到右的习惯方式那么主要就分为四种前序遍历、中序遍历、后序遍历、层序遍历。
2.1前序遍历
二叉树的前序遍历规则是若二叉树为空则空操作返回否则先访问根节点然后前序遍历左子树再前序遍历右子树。即按照“根节点-左子树-右子树”的顺序遍历二叉树。像下面这张图中的二叉树遍历顺序是ABDECFG: 二叉树的定义是用递归的方式所以实现遍历也可以采用递归而且极其简洁明了我们先来看看二叉树的前序遍历具体代码如下
void PreOrderTraverse(BiTree T)
{if(Tnull)return;printf(%c,T-data);PreOrderTraverse(T-lchild);preOrderTraverse(T-rchild);
}
假设我们有如下图这样的一棵二叉树T这棵树已经用二叉链表结构存储在内存当中: 当我们调用PreOrderTraverse(T)函数时我们来看看程序是怎么运行的
1当调用PreOrderTraverse(T)时根节点不为NULL所以执行printf打印字母A就像下面这样 2接着我们调用PreOrderTraverse(T-lchild)函数访问根节点A的左孩子不为NULL执行printf打印字母B如下图所示 3此时再次递归调用PreOrderTraverse(T-lchild)函数来访问B节点的左孩子执行printf函数打印字母D如下图所示 4再次递归调用PreOrderTraverse(T-rchild)访问D节点的左孩子此时因为D节点没有左孩子所以TNULL返回此函数此时递归调用PreOrderTraverse(T-rchild)访问D节点的右孩子执行printf打印H如下图所示 5 再次递归调用PreOrderTraverse(T-lchild)访问H节点的左孩子H节点没有左孩子返回调用PreOrderTraverse(T-rchild)访问H节点的右孩子也是NULL返回。于是此函数执行完毕返回到上一级递归的函数即打印D节点的函数也执行完毕返回打印D节点时的函数调用PreOrderTraverse(T-rchild)找到E节点打印字母E如下图所示 6由于节点E没有左右孩子返回打印B节点的递归函数递归执行完毕返回到最初的PreOrderTraverse调用PreOrderTraverse(T-rchild)访问A节点的右孩子如图所示 7之后类似前面的递归调用一依次打印F、I、G、J这里步骤就省略喽。 综上所述前序遍历这棵二叉树的节点的顺序是ABDHECFIGJ。
2.2中序遍历
规则是若树为空则空操作返回否则从根节点开始注意不是先访问根节点中序遍历是遍历根节点的左子树然后是访问根节点最后中序遍历右子树即按照“左子树-根节点-右子树”的顺序遍历二叉树。如下图所示的二叉树遍历的顺序为DBEAFCG 二叉树的中序遍历如何实现呢别以为很复杂它和前序遍历其实就是代码顺序上的差异
void InOrderPraverse(BiTree T)
{if(TNULL)return;InOrderPraverse(T-lchild);printf(%c,T-data);InOrderPraverse(T-rchild);
} 换句话说它等于把调用左孩子的递归函数提前了就这么简单我们来看看调用InOrderPraverse(T)函数时程序是如何运行的呢
1调用PreOrderTraverse(T)T的根节点不为NULL于是调用PreOrderTraverse(T-lchild)访问B节点当前指针仍不为NULL继续调用PreOrderTraverse(T-lchild)访问节点D继续调用PreOrderTraverse(T-lchild)访问D节点的左孩子发现当前指针为NULL于是返回打印当前节点D如下图所示 2然后调用PreOrderTraverse(T-rchild)访问节点D的右孩子H因为H也没有左孩子所i打印H如下图所示 3 因为H节点没有右孩子所以返回打印节点D函数执行完毕返回打印字母B如下图所示 4调用PreOrderTraverse(T-rchild)访问B节点的右孩子因为E节点没有左孩子所以打印字母E如下图所示 5E节点没有右孩子返回节点B的递归函数执行完毕返回到我们最初调用InOrderPraverse的地方打印字母A如下图所示 6再调用PreOrderTraverse(T-rchild)访问A节点的右孩子C再递归访问C节点的左孩子F接着访问节点F的左孩子I因为I没有左孩子打印I之后分别打印F、C、G、J。这里具体步骤也就省略了。
综上所述中序遍历这棵二叉树的节点顺序为D、H、B、E、S、A、I、F、C、G、J。
2.3后序遍历
规则是若树为空则空操作返回否则从左到右先叶子后节点地方式遍历访问左右子树最后访问根节点即按照“左子树-右子树-根节点”的顺序遍历二叉树。如下图所展示的二叉树遍历的顺序为DEBFCGA 同样地后序遍历也就很容易想到应该如何写代码了
void PostOrderPraverse(BiTree T)
{if(TNULL)return;PostOrderPraverse(T-lchild);PostOrderPraverse(T-rchild);printf(%c,T-data);
} 如下图所示后序遍历是先递归左子树由根节点A-B-D节点D没有左孩子再查看节点H因为节点H没有左右孩子所以打印字母H返回 最终后序遍历地节点的顺序为H、D、E、B、I、F、J、G、C、A可以完全参考前面的两个遍历方法来得到这个结果。
2.4层序遍历
规则是若树为空则空操作返回否则从树的第一层也就是从根节点开始访问从上而下逐层遍历在同一层中按从左到右地顺序对节点逐个访问。如下图所示遍历地顺序为ABCDEFG。 2.5推到遍历的结果 有一种题目为了考察我们对二叉树遍历的掌握程度是这样出题的已知一棵二叉树的前序遍历序列为ABCDEF中序遍历序列为CBAEDF请问这棵二叉树的后序遍历结果是多少
对于这样的题目如果真的完全了解了前中后序地原理是不难滴。三种遍历都是从根节点开始的前序遍历是先打印再递归左和右。所以前序遍历序列为ABCDEFG第一个字母是A被打印出来就说明A是根节点的数据再由中序遍历序列是CBAEDF可以知道C和B是A左子树的节点E、D、F是A右子树的节点如下图所示 然后我们看前序中的C和B他的顺序是ABCDEF是先打印B后打印C所以B应该是B地左孩子而C就只能是B地孩子此时是左孩子还是右孩子还不确定再看中序序列是CBAEDF而C是在B地前面打印这就说明C是B地左孩子否则就是右孩子了如下图所示 再看前序中的E、D、F它的顺序是ABCDEF那就意味着D是A节点的右孩子E和F是D地子孙注意他们中其中一个不一定是孩子有可能是孙子再来看中序序列是CBAEDF由E在D地左侧而F在右侧所以可以确定E是D的左孩子F是D的右孩子。因此最终得到的为叉树如下图所示 为了避免推到中的失误最好在心中递归遍历检查一下这棵树的前序和中序遍历序列是否与题目中的相同已经恢复了二叉树要获得他的后序遍历结果就是易如反掌结果就是CBEFDA。
反过来如果我们的题目是这样二叉树的中序序列是ABCDEFG后序序列是BDCAFGE求前序序列。
这次简单由后序的BDCAFGE得到E是根节点因此前序首字母是E。于是根据中序序列分为两棵树ABCD和FG由后序序列的BDCAFGE知道A是E的左孩子前序序列目前分析为EA。再由中序序列的ABCDEFG知道BCD是A节点的右子孙再由后序序列的BDCAFGE知道C节点是A节点的右孩子前序序列目前分析得到EAC。由中序序列ABCDEFG得到B是C的右孩子所以前序序列目前分析为EACBD由后序序列BDCAFGE得到G是E的右孩子于是F就是G的孩子而且还是左孩子前序遍历序列的最终结果就是EACBDGF。
从这里我们也得到了两个二叉树遍历的性质
已知前序遍历序列和中序遍历序列可以唯一确定一棵二叉树。已知后序遍历序列和中序遍历序列可以唯一确定一棵二叉树。
但是要注意了已知前序和后序遍历是不能确定一棵二叉树的原因也很简单比如前序序列是ABC后序序列是CBA我们可以确定A一定是根节点但接下来我们无法知道哪个节点是左子树哪个节点是右子树这棵树可能有如下图所示的四种可能 3.二叉树的建立
说了半天我们该如何在内存中生成一棵二叉链表的二叉树呢如果我们要在内存中建立一个左下角这样的树为了能让每个节点确认是否存在有左右孩子我们对它进行了拓展变成右下角的样子也就是将二叉树中的每个结点的空指针引出一个虚结点其值为一特定值比如“#”。我们称这种处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树比如左下角的前序遍历序列为AB#D##C##。 有了这样的准备我们就可以把刚才前序遍历的序列AB#D##C##用键盘挨个输入实现代码如下
void CreateBiTree(BiTree* T)
{TDataType ch;scanf(%c,ch);chstr[index];if(ch#)*TNULL;else{*T(BiTree)malloc(sizeof(BiTree));if(!*T)exit(-1);(*T)-datach;CreateBiTree((*T)-lchild);CreateBiTree((*T)-rchild);}
}
