关键词挖掘机爱站网,重庆网络推广网站,杭州 网站开发,做零食网站的原因我之前的文章C语言实现树#xff0c;你一定看得懂树的概念什么是树#xff1f;树属于非线性数据结构的一种#xff0c;概念也极多#xff0c;是由结点或顶点和边组成的且不存在着任何环的一种数据结构。没有结点的树称为空树。一棵非空的树包括一个根结点#xff0c;还很可… 我之前的文章C语言实现树你一定看得懂树的概念什么是树树属于非线性数据结构的一种概念也极多是由结点或顶点和边组成的且不存在着任何环的一种数据结构。没有结点的树称为空树。一棵非空的树包括一个根结点还很可能有多个附加结点并且所有结点构成一个多级分层结构。树的定义n个节点组成的有限集合。n0空树n0,1个根节点m个互不相交的有限集每个子集为根的子树如图所示为一颗树树树的基本术语节点的度树中某个节点的子树的个数。树的度树中各节点的度的最大值。分支节点度不为零的节点。叶子节点度为零的节点。路径i-j路径长度路径经过节点数目减1。孩子节点某节点的后继节点双亲节点该节点为其孩子节点的双亲节点父母节点兄弟节点同一双亲的孩子节点子孙节点某节点所有子树中的节点祖先节点从树节点到该节点的路径上的节点节点的层次根节点为第一层以此类推树的高度树中节点的最大层次有序树树中节点子树按次序从左向右安排次序不能改变无序树与有序树相反森林互不相交的树的集合。树的性质树的节点树为所有节点度数加1加根节点。度为m的树中第i层最多有m^(i-1)个节点。高度为h的m次树至多(m^h-1)/(m-1)个节点。具有n个节点的m次树的最小高度为logm( n(m-1) 1 )向上取整。二叉树二叉树简介二叉树是n(n0)个结点的有限集合每一个结点中最多拥有一个左结点和一个右结点并且没有多余的结点如图所示二叉树二叉树的特点根据二叉树的定义以及图示分析得出二叉树有以下特点每个结点最多有两颗子树不存在度大于2的结点。左子树和右子树的次序不能任意颠倒。即使树中某结点只有一棵子树也要区分它是左子树还是右子树。二叉树的性质二叉树具有以下几种特征二叉树第i层上的结点数目最多为2{i-1} (i≥1)。深度为k的二叉树至多有(2{k}-1)(k≥1)个结点。包含n个结点的二叉树的高度至少为log2 (n1)。在任意一棵二叉树中若终端结点的个数为n0度为2的结点数为n2则n0n21。几种特殊的二叉树斜树所有的结点都只有左(右)子树的二叉树叫左(右)斜树统称为斜树如图所示斜树满二叉树在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子都在同一层上这样的二叉树称为满二叉树其有以下特点叶子只能出现在最下一层否则就不可能达成平衡。非叶子结点的度一定是2。在同样深度的二叉树中满二叉树的结点个数最多叶子数最多。满二叉树完全二叉树一棵深度为k的有n个结点的二叉树对树中的结点按从上至下、从左到右的顺序进行编号如果编号为i1≤i≤n的结点与满二叉树中编号为i的结点在二叉树中的位置相同则这棵二叉树称为完全二叉树。完全二叉树二叉树的存储简介以创建一颗二叉树并实现通过特定的插入顺序和读取顺序达成读取为顺序为例子进行简介。结点设计一颗二叉树的结点设计一定要有如下内容结点元素data域用来存储数据左孩子结点left指针用来指向当前结点的下一层的左边结点右孩子结点right指针用来指向当前结点的下一层的右边结点除此之外我们使用一棵树的时候需要建立一颗树根由这个根来进行逐步的向下构建其代码如下//树的结点
typedef struct node{int data;struct node* left;struct node* right;
} Node;//树根
typedef struct {Node* root;
} Tree;
树的创建首先创建一个空的结点进行连接将这个空的结点中的date域赋予数据再判断tree中是否是一个空树如果为空只需要将整个根指向这一个结点即可如果不为空再进行两个判断判断输入的数据是否大于或者小于当前比对的结点数据根据其大小进行相应的排列这样存储进入的数据总是有一定规律的在输出的时候根据这个规律进行输出即可其代码可以显示为//创建树--插入数据
void insert(Tree* tree, int value){//创建一个节点让左右指针全部指向空数据为valueNode* node(Node*)malloc(sizeof(Node));node-data value;node-left NULL;node-right NULL;//判断树是不是空树如果是直接让树根指向这一个结点即可if (tree-root NULL){tree-root node;} else {//不是空树Node* temp tree-root;//从树根开始while (temp ! NULL){if (value temp-data){ //小于就进左儿子if (temp-left NULL){temp-left node;return;} else {//继续往下搜寻temp temp-left;}} else { //否则进右儿子if (temp-right NULL){temp-right node;return;}else {//继续往下搜寻temp temp-right;}}}}return;
}
遍历显示树代码如下//树的中序遍历 In-order traversal
void inorder(Node* node){if (node ! NULL){inorder(node-left);printf(%d ,node-data);inorder(node-right);}
}
树的遍历之先序遍历二叉树遍历简介遍历是按照一定的规则性将数据结构中的所有数据全部依次访问而二叉树需要通过在各节点与其孩子之间约定某种局部次序间接地定义某种全局次序。先序遍历根左右先序遍历先序遍历就是在访问二叉树的结点的时候采用先根再左再右的方式对于一个最简单的访问而言如下图先序遍历的访问顺序就是ABC多个结点相互嵌套构成的二叉树如图所示在访问遍历一开始的时候先访问根结点A次访问左节点B由于左结点中嵌套了一组结点因此左节点又作为下一个结点的根结点。继续沿着B访问到了D同样由于D中包含了一组新的结点D又作为根节点继续访问就又访问到了E由于E没有后面的结点了作为D为根的左结点E访问结束后访问到F这一组访问结束之后再回退访问G那么这一个二叉树的先序遍历访问顺序就是ABDEFGCH代码实现//树的先序遍历 Preorder traversal
void preorder(Node* node){if (node ! NULL){printf(%d ,node-data);inorder(node-left);inorder(node-right);}
}
扩展-前缀表达式我们日常的运算表达式通常是如下形式这种成为中缀表达式也就是运算符在运算数的中间如图为常规表达式(ab)*c其二叉树的表现形式为而前缀表达式的表达方式就是 *cab 它的一个特征就是符号迁移常规的表达式是需要大量的括号表达先后顺序的而这样的表达式表达形式不需要更容易让计算机处理。我们常规的表达式的计算是中序的而计算机更方便对前缀表达式这样的方式进行理解进行这样的转换首先思路要进行转换。在代码中我们实现这样的转换一般可以利用栈熟练书些这样的转换就需要STL的掌握。树的遍历之中序遍历二叉树简介中序遍历左根右如下图就一个最简单的二叉树遍历而言中序遍历的遍历访问过程是先B再A再C。多个结点构成的如图所示进行第一次访问的时候我们在ABC中进行遍历由左根右的顺序我们遍历访问到BB同时又作为BDG的根结点因此需要继续向下进行遍历。此时我们遍历到DEF这时E属于这一组之中的左结点因此我们根据根左右的先后顺序得到了最先的遍历效果EDF。这EDF同时作为BDG中的左节点把EDF看作一个整体进行回溯此时的访问的结点顺序为EDFBG。同理EDFBG作为ABC的左结点根据左根右的顺序EDFBGAC左半部分访问完毕接着访问右半部分我们将^CH^表示空看作一组左中右而C就是由EDFBGAC组合而成因此最终的遍历顺序为EDFBGACH代码实现//树的中序遍历 In-order traversal
void inorder(Node* node){if (node ! NULL){inorder(node-left);printf(%d ,node-data);inorder(node-right);}
}
中缀表达式常规算式中缀表达式是一个通用的算术或逻辑公式表示方法。中缀表达式就是我们最常用的表达式形式也是人最容易理解的表达式形式。如图为常规表达式(ab)*c其二叉树的表现形式为由前文可知前缀表达式的表达方式就是 *cab 我们常规的表达式的计算是中序的其表达式就是(ab)*c。我们可以理解为将表达式利用二叉树化然后通过中序遍历的方式进行提取如果需要发生组合时需要我们借助括号的形式表示优先级这样也有一个弊端就是当多个嵌套的时候需要的括号较多。树的遍历之后序遍历二叉树简介后序遍历左右根后序遍历就是在访问二叉树的结点的时候采用先左再右再根的方式对于一个最简单的访问而言如图先访问左节点B之后访问右结点C最后访问根节点A后序遍历的访问顺序就是BCA多个结点相互嵌套构成的二叉树如下图所示在访问遍历一开始的时候先访问左节点B再访问右结点C最后访问A由于B结点其中也包含了新的结点在面对处理的结点后还存在有与之相联的结点的时候需要优先处理其的子结点这也是“递归”的基本思路因此由于B属于DG的根结点相较于B应该先访问D结点而又由于D结点属于EF的根结点就又变成先访问E结点E属于最末端了根据后序遍历左右根的访问顺序依次生成EFDGB作为一个整体接着我们需要访问C由于C又是^HC之中的根结点我们先访问这个空结点又因为其是一个空的结点我们会跳过就变成了HC的访问顺序最后在汇总的时候EFDGB作为左节点HC作为右结点A作为根结点完成我们最终的遍历顺序EFDGBHCA。代码实现//树的后序遍历 Post-order traversal
void postorder(Node* node){if (node ! NULL){inorder(node-left);inorder(node-right);printf(%d ,node-data);}
}
后缀表达式后缀表达式与前缀表达式不同前缀表达式采用先序遍历的方式遍历访问我们的公式顺序常规式则就是中序方式而后缀表达式采用后续遍历的方式进行访问。如图为常规表达式(ab)*c其二叉树的表现形式为而后缀表达式的表达方式就是abc* 相较于前缀表达式后缀表达式则就是将符号进行后移其在计算机中的读取运算概念也符合栈的思路因此没有什么特殊的不同。总结树的概念还有很多比如DFS深度优先搜索森林与树哈夫曼树等等这里小编讲一些树的基础帮助大家入门了解。我们下一期再见#推荐阅读 专辑|Linux文章汇总 专辑|程序人生 专辑|C语言
嵌入式Linux微信扫描二维码关注我的公众号
