职场文秘网

首页 > 总结汇报 > 思想汇报 / 正文

线索二叉树算法的设计与实现

2020-11-24 20:10:44

线索二叉树算法的设计与实现 摘 要 随着时代的不断进步,计算机技术也随之得到发展。数据结构在计算机技术的发展中起到巨大的作用。数据结构为构建出高效的计算机算法打下了坚实的基础。良好的数据结构能够提高算法效率的同时也能减少对系统资源的占用[1]。

本文所研究的线索二叉树就是一种很常用的计算机算法。线索二叉树在计算机技术中的应用非常广泛,不管是在计算机系统构建上还是在智能化设计的搜索上都能看到这种算法的身影[2]。因此本文主要对传统的线索二叉树展开介绍然后对其进行一定的优化,希望这个优化之后的线索二叉树能够为之后的计算机算法的发展提供一定的帮助。

关键字:数据结构; 线索二叉树; 计算机算法 ABSTRACT With the continuous advancement of the times, computer technology has also developed. Data structures play a huge role in the development of computer technology. The data structure lays a solid foundation for building efficient computer algorithms. A good data structure can improve the efficiency of the algorithm while reducing the occupation of system resources. The clue binary tree studied in this paper is a very common computer algorithm. The clue binary tree is widely used in computer technology, and it can be seen in both computer system construction and intelligent design search. Therefore, this paper mainly introduces the traditional clue binary tree and then optimizes it. It is hoped that the clue binary tree after optimization can provide some help for the development of computer algorithms. Keywords: data structure clue; binary tree computer; algorithm 目 录 第1章 绪论 1 第2章 数据结构介绍 2 2.1数据结构 2 2.2树的结构定义 2 第3章 传统线索二叉树和新线索二叉树的区别 3 3.1传统二叉树 3 3.2优化的线索二叉树 5 3.3分析与比较 6 3.4线索二叉树的实用性 8 第4章 线索二叉树设计 9 4.1数据结构设计 9 4.2线索二叉树的创建模块 10 4.2.1 线索二叉树代码实现 10 4.3线索二叉树的三种遍历 10 4.4遍历结果显示 17 4.5线索二叉树的插入模块 17 4.5.1线索二叉树的插入模块的设计思想 17 4.5.2线索二叉树的插入模块的代码实现 18 4.5.3线索二叉树的插入模块的结果 18 4.6线索二叉树的删除模块 18 4.6.1线索二叉树删除模块的设计思想 18 4.6.2线索二叉树删除模块的代码实现 19 4.6.3线索二叉树的插入模块的结果 19 结 论 20 参考文献 21 致 谢 22 第1章 绪论 二叉树这种数据结构在计算机技术中的应用范围非常广泛,在程序设计中为了提高搜索算法的效率会大量的使用这种数据结构。二叉树在工厂领域应用的非常广泛,它不仅在游戏开发中,在当前比较火的人工智能上也得到了广泛的应用。其因为有着较强的扩展性,因此研究中运用的研究课题也比较多。二叉树在运用方面对于设计者的基础要求比较高,为了降低二叉树的难度,在其中加入了新的变量——线索,让原本的二叉树结构转变为线索二叉树结构从而减低二叉树结构的使用难度。但是传统的线索二叉树存在线索不连续的现象,也就是说在一些节点处需要重新对二叉树执行遍历操作才能找出当前线索的后序,但是执行遍历操作时所需时间较长并且占用的系统资源较多。本文提出了一种全新的线索二叉树,方便简化遍历的过程。

第2章 数据结构中的非线性结构—树型结构及其应用 2.1数据结构 数据结构的出现是为了让程序设计更加方便,大量使用在数据的存储方式和数据的处理方式上。检验程序效率最好的方式就是看设计的数据结构是否合理。结构图是描述计算机逻辑的主要方式,将每一个数据结构当做算法中的一个节点,因此只是设计合理的数据结构不能让算法的效率达到最高,还需要对算法进行优化。衡量算法效率的最为重要的标准就是看算法的执行时间,因此算法的每一步所需的时间越短,算法的效率也就越高。树形结构是描述具有层次关系的最好方式之一,能够帮助设计者理清算法逻辑帮助查找问题。线索二叉树是建立在遍历二叉树程序的基础上构建的,才有单独函数封装的方式将线索二叉树的功能分解为插入、删除等功能。能够提高获取后继、前驱节点的效率,减少算法的执行时间,提高算法的效率[3]。

2.2树的结构定义 树形结构是常用于表示信息的方式之一,属于一种信息嵌套的表达方式。树形结构具有多层结构,但是不管是内层还是外层他们的结构都是相同的[4]。因此遍历树形结构时可以采用递归这种高效的遍历方式。树结构的基本形式如图2.2所示。

A B C D E F G H I J 图2.2 经典的树形结构 图2.2 classic tree structure 其中A是整个树形结构的根节点,B,C,D节点是节点A的子节点,B节点是A节点的左子节点,C节点是A节点的中子节点,D节点是A节点的右子节点。并且B,C,D节点下也可以有多个子节点。

树形结构具有如下属性:
结点:结点是树形结构组成的最基本的数据元素,图1中的A、B、C节点都可以看做是树形结构的结点。

树的度:整个树结构中拥有最大的节点数,在图1中,A节点拥有的节点数为3,B节点、C节点、D节点拥有的节点数分别为3,1,2,因此整个树结构拥有最有的节点数为3,所以树的度是3。

叶子节点:在整个树结构中最底层的节点称为叶子节点,树形结构和现实中的树表示是相反的,树形结构中将最上层的节点成为根节点,最底层的节点称为叶子节点,连接根节点和叶子节点的其他节点成为中间节点。图一中,A节点就是树形结构的根节点,E、F、G、H、J、I节点就是树形结构的叶子节点,B、C、D节点就是连接根节点和叶子节点的中间节点也被称为中间节点。

父节点和子节点:在树形结构中,认为一个节点的前驱节点认为是该节点的父节点,节点的后继认为是该节点的子节点。图1:以B节点为例,B节点的前驱节点是A节点,因此认为A节点是B节点的父节点,B节点的后继节点有E、F、G节点,因此E、F、G节点是B节点的子节点。

堂兄弟:不同的节点有着同一个父节点那么这些节点就被成为是堂兄弟。图1中,B,C,D节点共有一个父节点,因此B,C,D节点之间的关系被称为堂兄弟[5]。

树的层次和深度:树的层次在一般情况下和树的深度是相等的,将只有根节点的树形结构的层次和深度认为是1,如果根节点拥有一个或者多个子节点,这些子节点都没有后继节点,那么此时树形结构的层次和深度就是2。每一个子节点的层次都是其父节点的层次加1。计算树的层次和深度时就是从根节点到叶子节点所有的节点数。图1所示的树形结构,树的层次和深度就是3[6]。

第3章 传统线索二叉树和新线索二叉树的区别 3.1传统二叉树 二叉树的树形结构和经典的树形结构有所区别,经典的树形结构同一个节点可以有多个子节点,但是二叉树的树形结构中,一个节点最多只有两个字节点,并且这些子节点的叫法为左子节点、右子节点,如果字节只有一个子节点时,子节点被默认为左子节点。二叉树的树形结构如图3.1.1:
图3.1.1 二叉树的树形结构 图3.1.1 the tree structure of a binary tree 先序遍历、中序遍历、后序遍历这种三种遍历方式是二叉树的主要遍历方式。

先序遍历的遍历思想:先序遍历首选访问的是树形结构的根节点,然后访问根节点的左子节点,继续访问根节点的左子节点的左子节点,当全部的左子节点访问完毕之后,然后访问最后一个左子节点的堂兄弟右子节点,依次访问直到所有的节点访问完成。

中序遍历法:找到根节点的最底层的左子节点,从最底层的左子节点开始访问,然后访问这个左子节点的父节点,再访问父节点的右节点,再访问父节点的父节点,再访问父节点的父节点的右子节点,依次访问,直到树形结构的所有节点访问完毕。

后续遍历法:先找到根节点,根据根节点找到左子叶节点,访问根节点的左子叶节点。然后访问左子叶节点的堂兄弟右子叶节点,最后访问左子叶节点和右子叶节点的父节点。根据这个规律二叉树存在的所有节点都访问完毕。

3.2优化的线索二叉树 通过传统二叉树数据结构可以发现,在一些节点处没有办法准确找出每一个节点的前驱和后继线索。如果找不到当前节点的线索时,需要再次遍历整个二叉树才能找出该节点的线索,因为传统二叉树的数据结构中存放的线索不连续,很多地方存在断开的情况[7]。为了更好地处理这种现象,本文重新定义了二叉树的数据结构。其数据结构如下:
Lchild LTag Data RTag rchild 本文设计的数据结构大致和传统的二叉树结构相同,只是在数据结构中新添加了一个栈,这个数据变量用来存储该节点的线索,也就是说用来指向和存储节点的前驱和后继。这种数据结构在遍历时能够确保线索的连贯性,不比为了寻找出当前节点的前驱和后继而重新遍历整个二叉树。

这种改进的基本思想为:
先序遍历:将栈引入,当前节点赋值为根节点,当节点不为空时,将该节点入栈,然后指向左子,入栈。直到左子为空,当前栈顶出栈,找他的右子,右子为空则继续出栈,当有右子时,右子入栈,找右子的左子,一直到为空[8]。

如图3.2 开始 当前节点赋值为根节点 节点是否为空? 结束 指向左子树 指向它的右子树 打印并入栈 否 找左子树,取栈顶 取出左子树 是否为空? 是 是 否 图3.2 线索二叉树的先序遍历流程图 图3.2 a preorder traversal flowchart of a clue binary tree 当然在实际运用中,构造的线索二叉树并不一定完全是好的,因此采用这种数据结构还有一定的缺陷,这种数据结构在主函数中较为繁琐,必须理清节点与节点之间的关系,防止出现意外的访问导致算法出现不可预知的错误。

本文所设计的线索二叉树数据结构和传统的线索二叉树数据结构同时运用到平衡二叉树时,本文设计的线索二叉树数据结构还是占有一定的优势,即使本文所设计的线索二叉树数据结构遍历时需要判断当前节点是否为右子节点,如果是右子节点,栈中则不需要存放后继的数据线索,如果当前节点为左子节点时,则需要判断是否存在兄弟右子节点,如果不存在右子节点则出栈,如果当前节点存在兄弟右子节点,栈中则需要存放右子节点的线索,虽然本文设计的数据结构在二叉树构建时需要判断的情况较多,但是在采用遍历法遍历线索二叉树的效率却比传统的线索二叉树结构效率要高[9]。

3.3分析与比较 本文所设计的二叉树结构和传统的二叉树结构相比,传统二叉树的数据结构的访问顺序如图3.3.1: 图3.3.1 传统二叉树结构的先序线索指向 图3.3.1 preorder clues of traditional binary tree structure 图3.3.1中实线箭头部分代表线索二叉树中的后继线索,虚线箭头部分代表线索二叉树中的前趋线索。采用本文所设计内容线索之间的联系为图3.1.2: 图3.1.2 优化二叉树数据结构线索指向 图3.1.2 optimization of binary tree data structure clues 图中的实线箭头部分代表的是线索二叉树的后继线索,虚线箭头部分代表的线索的前驱线索。

判断一个算法的两个标准是时间复杂度和空间复杂度,这里将两种算法在平衡的线索二叉树进行两种标准的比较,非平衡二叉树不可控因素较多,并且不好计算其两种算法格子所需的时间复杂度[10]。

时间复杂度的定义 时间复杂度是衡量算法效率的重要指标。时间复杂度本质是指算法完成所需的时间。但是因为计算机硬件设计有所差异,因此会造成同一算法在不同的计算机硬件上所需的时间不一致。这样就无法直接通过算法完成所需的时间判断算法的时间复杂度。为了统一标准,规定算法的相同单元所需的时间认为是一样的,只需要计算该单元被调用的次数,从而计算出算法的时间复杂度[11]。

时间复杂度 本文研究的线索二叉树是平衡二叉树,因此不管使用传统二叉树的数据结果或者本文设计的二叉树在执行遍历、插入或者删除等操作时,所需的时间复杂度都是相同的。而且其时间复杂度和平衡二叉树的时间复杂度相等。二叉树处于平衡状态时,一般只有两种情况,一种是二叉树是空树,一种是二叉树由根节点下的左右子节点为基础构建的子树为平衡二叉树。而且二叉树的左右子树的高度差的绝对值一般都保持在1以下,因此平衡二叉树的时间复杂度为O(log2n),而本文设计的线索二叉树数据结构和传统二叉树数据结构的数据类型都是在平衡二叉树的基础上,因此他们的时间复杂度和平衡二叉树的时间复杂度一致都为O(long2n)[12]。

空间复杂度的定义 空间复杂度是衡量一个算法在执行过程中所需的临时空间的大小的量度,记做S(n)=O(f(n))。一个算法所需要占用的存储空间主要分为三个部分:1、程序本身所需要的存储空间;
2、算法输入输出变量所需要的存储空间;
3、运行代码时所需的存储空间。算法的输入输出变量所需要的存储空间是由要解决的问题所决定的,跟算法几乎没有关系。算法所需的存储空间是有算法的实现所决定的,因此要想减少存储代码所需的空间,在编码代码时需要注意代码的长度,使用简洁的代码可以有效的减少存储算法所需的空间[13]。

空间复杂度的计算 计算算法所需的空间复杂度时,通常只需要计算算法运行时占用的空间,如采用递归调用,算法运行时所需的存储空间为算法的调用次数*算法第一次所需要的存储空间[14]。当采用非递归调用时,则需要根据算法的实际情况计算。线索二叉树的所有操作能使用递归的方式调用,因此我们在计算本文设计的线索二叉树数据结构和传统的线索二叉树数据结构时,只需要对比第一次所需要开辟的数据空间。假设传统的二叉树数据结构所需的数据空间为n,因为本文设计的二叉树数据结构在传统的二叉树数据结构上新增了一个数据空间,因此其所需的数据空间为(n+1)。对比两种算法的空间复杂度,本文设计的二叉树结构要比传统的二叉树在空间复杂度要略差一下。

通过对比两种算法的时间复杂度和空间复杂度,两种算法的差别并不大,但是本文设计的线索二叉树弥补了传统线索二叉树在线索上不连续的现象。建立线索二叉树的主要目的是为了将遍历二叉树时的递归算法变为迭代算法,从而降低算法在运行过程中对系统资源的占用。

3.4线索二叉树的实用性 本文中的优化线索二叉树利用了栈来进行线索二叉树的调用,大大简略了算法的复杂性,使线索二叉树的使用变的方便快捷。虽然节省系统资源上没有达到目的,但是线索二叉树却在一些地方比使用传统的二叉树的效率要高。比如路由器使用CIDR选择消息转发或者下一跳时,需要进行信息匹配时,采用线索二叉树能够极大的提高效率。

第4章 线索二叉树设计 4.1数据结构设计 本文设计的线索二叉树设计如下:
传统的线索二叉树数据结构设计如下:
typedef struct oldlist { int LTag; char *data; int RTag; struct oldlist *Lchild; struct oldlist *Rchild; }; typedef struct TreeNode { int data; struct TreeNode * LeftChild; struct TreeNode * RightChild; } TreeNode; typedef struct MyStack { TreeNode *a[100]; int top; }MyStack; 设计思想,二叉树在构建上和线性列表不同,因此本文用结构的形式代表一个二叉树节点,根据结构体数据空间的算法占用的数据空间大小为24字节,比传统二叉树占用的空间多4个字节。传统二叉树使用后序遍历方式时,左子节点中没有直接存储当前节点的后序,之后先返回该节点的父节点然后再找出左子叶节点的后继线索[15]。为了弥补这一缺点,本文所设计的数据结构新增了一个兄弟的数据变量,从而让每一个节点的线索都是连续的。

结构体中每个变量的取值范围和定义:
Lchild和Rchild这部分区域内所存放的数据内容是受到LTag和RTag的取值所决定的:
当LTag的取值为0时,Lchild内存储的数据内容为当前节点的左孩子;
如果LTag的取值为1时,Lchild内存储的数据内容为当前节点的前趋,当RTag的取值为0时,rchild内所存储的类型为该节点的右子节点,如果RTag的取值等于1时,Rchild内所存贮的数据内容为该节点的后继。Top指针用来指向栈中栈顶的位置。

4.2线索二叉树的创建模块 4.2.1 线索二叉树代码实现 Bitree *crt_bt_pre(bitree *bt){ Char ch; Ch=getchar( ); If(ch==‘#’) Bt=null; Else{ Bt=(bitree *)malloc(sizeof(bitree)); Bt->data=c; Bt->lchild=crt_bt_pre(bt->lchild); Bt->rchild=crt_bt_pre(bt->rchild); } Return(bt); } 4.3线索二叉树的三种遍历 #include <stdio.h> #include <malloc.h> typedef struct TreeNode { int data; struct TreeNode * LeftChild; struct TreeNode * RightChild; } TreeNode; void initTreeNode(TreeNode * t,int val,TreeNode * leftNode,TreeNode * rightNode) { t->data=val; t->LeftChild=leftNode; t->RightChild=rightNode; } typedef struct MyStack { TreeNode *a[100]; int top; }MyStack; void initMyStack(MyStack *ms) { ms->top=0; } void push(MyStack *ms, TreeNode *n) { ms->a[ms->top]=n; ms->top++; } int isEmpty(MyStack *ms) { if(ms->top==0) {return 1;} else {return 0;} } TreeNode * pop(MyStack *ms) { if(isEmpty(ms)) return NULL; else {ms->top--; return ms->a[ms->top];} } TreeNode * top(MyStack *ms) { if(isEmpty(ms)) return NULL; return ms->a[ms->top-1]; } void PreOrder(TreeNode *root)/*非递归前序遍历*/ { TreeNode * temp; MyStack * s = (MyStack*)malloc(sizeof(MyStack)); initMyStack(s); temp = root;/*当前节点赋值为根节点*/ while(temp!=NULL || !isEmpty(s)) { while(temp!=NULL) { printf(“%d |“,temp->data);/*当前节点不为空,说明是最上面的节点,那直接打印。*/ push(s,temp);/*将该节点入栈*/ temp=temp->LeftChild;/*指向左子*/ }/*直接打印了左子后,入栈,又指向左子的子,直到为空*/ if(!isEmpty(s))/*当没有左子后,栈顶为最后打印出来的左子*/ { temp = pop(s);/*取出该左子*/ temp=temp->RightChild;/*找它的右子,没有则还为空,那么不进入上面的while,将继续本操作,直到指向了右子。*/ }/*打印右子,右子入栈,找右子有没有左子,没有,那么再次进入if判断,并继续取出栈顶。*/ } } void InOrder(TreeNode *root)/*非递归中序遍历*/ { TreeNode * temp = root; MyStack * s = (MyStack*)malloc(sizeof(MyStack)); initMyStack(s); push(s,temp); temp=root->LeftChild;/*和先序类似,他先指向左子*/ while(temp != NULL || !isEmpty(s)) { while(temp!=NULL) { push(s,temp);/*左子不为空那么入栈,继续找左子,直到没有左子*/ temp=temp->LeftChild; } temp=pop(s);/*这时打印栈顶,即为最下层的左子*/ printf(“%d |“,temp->data); temp=temp->RightChild;/*找右子,没有右子还将继续取栈顶,直到有了右子,那么在进行入栈操作。*/ } } void PostOrder(TreeNode *root)//非递归后序遍历 { TreeNode * temp = root; int Tag[20];/*栈操作依然类似,但是要比先序和中序多一步,要有标记*/ MyStack * s = (MyStack*)malloc(sizeof(MyStack)); initMyStack(s); while(temp != NULL || !isEmpty(s)) { while(temp!=NULL) { push(s,temp); Tag[s->top]=0;/*当前栈顶标记为没有打印,只做了入栈*/ temp=temp->LeftChild;/*指向左子,继续入栈,直到没有左子*/ } while (!isEmpty(s)&&Tag[s->top]==1)/*如果发现栈顶的标记为1了,那么就取出栈顶,并打印。*/ { temp=pop(s); printf(“%d |“,temp->data); } if (!isEmpty(s))/*没有左子后,光标定位到栈顶,看栈顶有没有右子,并将栈顶的标记为1,准备打印*/ { Tag[s->top]=1; temp=top(s); temp=temp->RightChild; } else { break; } } } int main() { struct TreeNode *rootNode=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node1=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node2=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node3=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node4=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node5=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node6=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node7=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node8=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node9=(TreeNode*)malloc(sizeof(TreeNode)); struct TreeNode *node10=(TreeNode*)malloc(sizeof(TreeNode)); initTreeNode(rootNode,0,node1,node2); initTreeNode(node1,1,node3,node4); initTreeNode(node2,2,node5,node6); initTreeNode(node3,3,node7,node8); initTreeNode(node4,4,node9,node10); initTreeNode(node5,5,NULL,NULL); initTreeNode(node6,6,NULL,NULL); initTreeNode(node7,7,NULL,NULL); initTreeNode(node8,8,NULL,NULL); initTreeNode(node9,9,NULL,NULL); initTreeNode(node10,10,NULL,NULL); printf(“原始数据:
0| 1| 2| 3| 4| 5| 6| 7| 8| 9| 10|\n“); printf(“\n先序输出:“); PreOrder(rootNode); printf(“\n中序输出:“); InOrder(rootNode); printf(“\n后序输出:“); PostOrder(rootNode); getchar(); } 4.4遍历结果显示 图4.4.1 构建的线索二叉树 图4.4.1 construct the binary tree 对于构造的如图4.4.1的线索二叉树的遍历结果如下图4.4.2所示:
图4.4.2 遍历结果 图4.4.2 iterate through the result 4.5线索二叉树的插入模块 4.5.1线索二叉树的插入模块的设计思想 线索二叉树的插入模块中,假设需要插入的节点为P,需要插入在节点s下面:
节点P要成为节点S的右孩子 首先需要判断节点S的右孩子是否为空,如果为空则可以将节点P插入到节点S下面,将S的右孩子节点置位P,其余线索不会发生变化,此时右子节点的插入完成[16]。

如果节点S的右孩子不为空,表示节点P不在成为节点S的右孩子。只能一次遍历节点S的右孩子,直到有节点的右孩子为空,才能完成插入动作。

节点P要成为节点S的左孩子 需要先判断节点S的左孩子是否为空,如果为空,则可以将节点P插入到节点S的左孩子中。此时节点S还没有右孩子,所以节点P的后继线索为节点S,节点P是节点S的前驱线索,只需要将节点P的线索添加到节点S的左孩子中,其余线索不变,此时左子节点的插入完成[17]。

4.5.2线索二叉树的插入模块的代码实现 void initTreeNode(TreeNode * t,int val,TreeNode * leftNode,TreeNode * rightNode) { t->data=val; t->LeftChild=leftNode; t->RightChild=rightNode; } 4.5.3线索二叉树的插入模块的结果 图4.5.3 插入模块的结果 图4.5.3 the result of inserting a module 4.6线索二叉树的删除模块 4.6.1线索二叉树删除模块的设计思想 删除线索二叉树时,需要考虑一下几种情况,分别为删除的节点为叶节点还是中间节点亦或者是根节点。

当删除的节点为叶节点时,需要判断删除的节点是否为右节点,如果当前的节点为右节点需要将该父节点的右孩子节点的变量置为空,其余线索不需要进行更改将节点删除[18]。当删除的叶节点为左节点时,可以将该父节点的左孩子置为空,然后直接将节点删除。

4.6.2线索二叉树删除模块的代码实现 void RemoveTreeNode(TreeNode * t,int flag) { if (1 == flag) { t->LeftChild = NULL; } else { t->RightChild = NULL; } 4.6.3线索二叉树的删除模块的结果 图4.6.3 删除模块的结果 图4.6.3 the result of deleting a module 结 论 本文设计的新线索二叉树在遍历时的访问速度明显要比传统线索二叉树更快。虽然本文所设计的线索二叉树要比传统二叉树的数据类型要多一个栈,在变量相同层次的二叉树时要多占用一定的数据空间,但是所占用的数据空间对于计算机拥有的庞大的数据空间而言新线索二叉树运行时所需的数据空间微不足道。使用遍历法时,每一个节点都有指向自己前驱或者后继的指针,不必出现线索断裂的情况,使用遍历线索二叉树结构时,基本可以将线索二叉树当做是常规的线性栈访问,逻辑上也比传统的二叉树好理解。

“数据结构”是计算机技术中非常基础的一门知识,并且也是高校计算机专业必修课程。数据结构课程主要是讲授如何用数据组织的方法将现实生活中的问题描述出来。而且这门课程的理论知识较难并且需要大量的实践,就算学生将理论知识学的很扎实,但是运用知识处理实际问题时可能会有问题。因此需要学生大量和反复的实践,对知识有着更加深刻的理解。

参考文献 [1]薛晓亚.浅谈如何学好数据结构[J].电脑知识与技术,2018,14(16):127+144. [2]杨晓波,陈邦泽.“数据结构”演示实验类交互式微课设计与实践[J].实验技术与管理,2017,34(08):153-157+171. [3]王军.基于一道二叉树习题的教学案例辨析[J].福建电脑,2017,33(05):73-75. [4]沈华.数据结构课内实践教学方案[J].实验室研究与探索,2013,32(10):396-400. [5]杨晓波,陈邦泽.线索二叉树的可视化实现[J].西北师范大学学报(自然科学版),2013,49(01):46-49. [6]郭小春,王红.线索二叉树算法的实验与实现[J].泰山学院学报,2011,33(06):40-45. [7]徐翀,徐建.数据结构的对象化教学方式探讨与实践[J].中国现代教育装备,2011(09):104-106. [8]胡慧.数据结构线索二叉树的应用[J].煤炭技术,2010,29(06):174-176. [9]胡树杰,喻红婕.线索二叉树算法的改进[J].沈阳理工大学学报,2008,27(06):18-20. [10]汪一心,刘斯远.数据结构中若干遍历知识点的贯通式教学[J].江西广播电视大学学报,2008(04):102-103. [11]马变芳,张丽平.一种优化的线索二叉树方法[J].福建电脑,2008(11):87. [12]索红军.二叉树的静态二叉链表存储[J].渭南师范学院学报,2008(02):66-67. [13]葛建梅.“数据结构”课程教学方法改革的思考[J].中国成人教育,2008(01):147-148. [14]崔永,赵良才.基于相似线索二叉树的汽车零部件拆卸序列生成及其回收模糊评价[J].现代制造工程,2007(02):66-70. [15]谷立东.用C语言实现二叉树的遍历及其应用[J].牡丹江教育学院学报,2006(06):142-143. [16]周敏,于瀛军.浅谈二叉树线索化及利用线索进行遍历[J].农业网络信息,2006(08):33-35. [17]王振,蔡金锭.基于线索二叉树的辐射状配电网潮流计算[J].高电压技术,2006(06):113-115+118. [18]宋玲,吕强.《数据结构》中二叉树的教学方法探讨[J].山东电力高等专科学校学报,2006(02):6-9. 致 谢

Tags: 算法   线索   二叉树  

搜索
网站分类
标签列表