线索二叉树算法设计实现
摘
着时代断进步计算机技术发展数结构计算机技术发展中起巨作数结构构建出高效计算机算法坚实基础良数结构够提高算法效率时减少系统资源占[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
21数结构 2
22树结构定义 2
第3章 传统线索二叉树新线索二叉树区 3
31传统二叉树 3
32优化线索二叉树 5
33分析较 6
34线索二叉树实性 8
第4章 线索二叉树设计 9
41数结构设计 9
42线索二叉树创建模块 10
421 线索二叉树代码实现 10
43线索二叉树三种遍历 10
44遍历结果显示 17
45线索二叉树插入模块 17
451线索二叉树插入模块设计思想 17
452线索二叉树插入模块代码实现 18
453线索二叉树插入模块结果 18
46线索二叉树删模块 18
461线索二叉树删模块设计思想 18
462线索二叉树删模块代码实现 19
463线索二叉树插入模块结果 19
结 20
参考文献 21
致 谢 22
第1章 绪
二叉树种数结构计算机技术中应范围非常广泛程序设计中提高搜索算法效率会量种数结构二叉树工厂领域应非常广泛仅游戏开发中前较火工智广泛应着较强扩展性研究中运研究课题较二叉树运方面设计者基础求较高降低二叉树难度中加入新变量——线索原二叉树结构转变线索二叉树结构减低二叉树结构难度传统线索二叉树存线索连续现象说节点处需重新二叉树执行遍历操作找出前线索序执行遍历操作时需时间较长占系统资源较文提出种全新线索二叉树方便简化遍历程
第2章 数结构中非线性结构—树型结构应
21数结构
数结构出现程序设计更加方便量数存储方式数处理方式检验程序效率方式设计数结构否合理结构图描述计算机逻辑方式数结构做算法中节点设计合理数结构算法效率达高需算法进行优化衡量算法效率重标准算法执行时间算法步需时间越短算法效率越高树形结构描述具层次关系方式够帮助设计者理清算法逻辑帮助查找问题线索二叉树建立遍历二叉树程序基础构建单独函数封装方式线索二叉树功分解插入删等功够提高获取继前驱节点效率减少算法执行时间提高算法效率[3]
22树结构定义
树形结构常表示信息方式属种信息嵌套表达方式树形结构具层结构层外层结构相[4]遍历树形结构时采递种高效遍历方式树结构基形式图22示
A
B
C
D
E
F
G
H
I
J
图22 典树形结构
图22 classic tree structure
中A整树形结构根节点BCD节点节点A子节点B节点A节点左子节点C节点A节点中子节点D节点A节点右子节点BCD节点子节点
树形结构具属性：
结点：结点树形结构组成基数元素图1中ABC节点做树形结构结点
树度：整树结构中拥节点数图1中A节点拥节点数3B节点C节点D节点拥节点数分312整树结构拥节点数3树度3
叶子节点：整树结构中底层节点称叶子节点树形结构现实中树表示相反树形结构中层节点成根节点底层节点称叶子节点连接根节点叶子节点节点成中间节点图中A节点树形结构根节点EFGHJI节点树形结构叶子节点BCD节点连接根节点叶子节点中间节点称中间节点
父节点子节点：树形结构中认节点前驱节点认该节点父节点节点继认该节点子节点图1：B节点例B节点前驱节点A节点认A节点B节点父节点B节点继节点EFG节点EFG节点B节点子节点
堂兄弟：节点着父节点节点成堂兄弟图1中BCD节点父节点BCD节点间关系称堂兄弟[5]
树层次深度：树层次般情况树深度相等根节点树形结构层次深度认1果根节点拥者子节点子节点没继节点时树形结构层次深度2子节点层次父节点层次加1计算树层次深度时根节点叶子节点节点数图1示树形结构树层次深度3[6]
第3章 传统线索二叉树新线索二叉树区
31传统二叉树
二叉树树形结构典树形结构区典树形结构节点子节点二叉树树形结构中节点两字节点子节点法左子节点右子节点果字节子节点时子节点默认左子节点二叉树树形结构图311：
图311 二叉树树形结构
图311 the tree structure of a binary tree
先序遍历中序遍历序遍历种三种遍历方式二叉树遍历方式
先序遍历遍历思想：先序遍历首选访问树形结构根节点然访问根节点左子节点继续访问根节点左子节点左子节点全部左子节点访问完毕然访问左子节点堂兄弟右子节点次访问直节点访问完成
中序遍历法：找根节点底层左子节点底层左子节点开始访问然访问左子节点父节点访问父节点右节点访问父节点父节点访问父节点父节点右子节点次访问直树形结构节点访问完毕
续遍历法：先找根节点根根节点找左子叶节点访问根节点左子叶节点然访问左子叶节点堂兄弟右子叶节点访问左子叶节点右子叶节点父节点根规律二叉树存节点访问完毕
32优化线索二叉树
通传统二叉树数结构发现节点处没办法准确找出节点前驱继线索果找前节点线索时需次遍历整二叉树找出该节点线索传统二叉树数结构中存放线索连续方存断开情况[7]更处理种现象文重新定义二叉树数结构数结构：
Lchild
LTag
Data
RTag
rchild
文设计数结构致传统二叉树结构相数结构中新添加栈数变量存储该节点线索说指存储节点前驱继种数结构遍历时够确保线索连贯性寻找出前节点前驱继重新遍历整二叉树
种改进基思想：
先序遍历：栈引入前节点赋值根节点节点空时该节点入栈然指左子入栈直左子空前栈顶出栈找右子右子空继续出栈右子时右子入栈找右子左子直空[8] 图32
开始
前节点赋值根节点
节点否空？
结束
指左子树
指右子树
印入栈
否
找左子树取栈顶
取出左子树
否空？
否
图32 线索二叉树先序遍历流程图
图32 a preorder traversal flowchart of a clue binary tree
然实际运中构造线索二叉树定完全采种数结构定缺陷种数结构函数中较繁琐必须理清节点节点间关系防止出现意外访问导致算法出现预知错误
文设计线索二叉树数结构传统线索二叉树数结构时运衡二叉树时文设计线索二叉树数结构占定优势文设计线索二叉树数结构遍历时需判断前节点否右子节点果右子节点栈中需存放继数线索果前节点左子节点时需判断否存兄弟右子节点果存右子节点出栈果前节点存兄弟右子节点栈中需存放右子节点线索然文设计数结构二叉树构建时需判断情况较采遍历法遍历线索二叉树效率传统线索二叉树结构效率高[9]
33分析较
文设计二叉树结构传统二叉树结构相传统二叉树数结构访问序图331
图331 传统二叉树结构先序线索指
图331 preorder clues of traditional binary tree structure
图331中实线箭头部分代表线索二叉树中继线索虚线箭头部分代表线索二叉树中前趋线索采文设计容线索间联系图312
图312 优化二叉树数结构线索指
图312 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）两种算法空间复杂度文设计二叉树结构传统二叉树空间复杂度略差
通两种算法时间复杂度空间复杂度两种算法差文设计线索二叉树弥补传统线索二叉树线索连续现象建立线索二叉树目遍历二叉树时递算法变迭代算法降低算法运行程中系统资源占
34线索二叉树实性
文中优化线索二叉树利栈进行线索二叉树调简略算法复杂性线索二叉树变方便快捷然节省系统资源没达目线索二叉树方传统二叉树效率高路器CIDR选择消息转发者跳时需进行信息匹配时采线索二叉树够极提高效率
第4章 线索二叉树设计
41数结构设计
文设计线索二叉树设计：
传统线索二叉树数结构设计：
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]弥补缺点文设计数结构新增兄弟数变量节点线索连续
结构体中变量取值范围定义：
LchildRchild部分区域存放数容受LTagRTag取值决定：
LTag取值0时Lchild存储数容前节点左孩子果LTag取值1时Lchild存储数容前节点前趋RTag取值0时rchild存储类型该节点右子节点果RTag取值等1时Rchild存贮数容该节点继Top指针指栈中栈顶位置
42线索二叉树创建模块
421 线索二叉树代码实现
Bitree *crt_bt_pre(bitree *bt){
Char ch
Chgetchar( )
If(ch＃’)
Btnull
Else{
Bt(bitree *)malloc(sizeof(bitree))
Bt>datac
Bt>lchildcrt_bt_pre(bt>lchild)
Bt>rchildcrt_bt_pre(bt>rchild)
}
Return(bt)
}
43线索二叉树三种遍历
#include
#include
typedef struct TreeNode
{
int data
struct TreeNode * LeftChild
struct TreeNode * RightChild
} TreeNode
void initTreeNode(TreeNode * tint valTreeNode * leftNodeTreeNode * rightNode)
{
t>dataval
t>LeftChildleftNode
t>RightChildrightNode
}
typedef struct MyStack
{
TreeNode *a[100]
int top
}MyStack
void initMyStack(MyStack *ms)
{
ms>top0
}
void push(MyStack *ms TreeNode *n)
{
ms>a[ms>top]n
ms>top++
}
int isEmpty(MyStack *ms)
{
if(ms>top0)
{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>top1]
}
void PreOrder(TreeNode *root)*非递前序遍历*
{
TreeNode * temp
MyStack * s (MyStack*)malloc(sizeof(MyStack))
initMyStack(s)
temp root*前节点赋值根节点*
while(tempNULL || isEmpty(s))
{
while(tempNULL)
{
printf(d |temp>data)*前节点空说明面节点直接印*
push(stemp)*该节点入栈*
temptemp>LeftChild*指左子*
}*直接印左子入栈指左子子直空*
if(isEmpty(s))*没左子栈顶印出左子*
{
temp pop(s)*取出该左子*
temptemp>RightChild*找右子没空进入面while继续操作直指右子*
}*印右子右子入栈找右子没左子没次进入if判断继续取出栈顶*
}
}
void InOrder(TreeNode *root)*非递中序遍历*
{
TreeNode * temp root
MyStack * s (MyStack*)malloc(sizeof(MyStack))
initMyStack(s)
push(stemp)
temproot>LeftChild*先序类似先指左子*
while(temp NULL || isEmpty(s))
{
while(tempNULL)
{
push(stemp)*左子空入栈继续找左子直没左子*
temptemp>LeftChild
}
temppop(s)*时印栈顶层左子*
printf(d |temp>data)
temptemp>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(tempNULL)
{
push(stemp)
Tag[s>top]0*前栈顶标记没印做入栈*
temptemp>LeftChild*指左子继续入栈直没左子*
}
while (isEmpty(s)&&Tag[s>top]1)*果发现栈顶标记1取出栈顶印*
{
temppop(s)
printf(d |temp>data)
}
if (isEmpty(s))*没左子光标定位栈顶栈顶没右子栈顶标记1准备印*
{
Tag[s>top]1
temptop(s)
temptemp>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(rootNode0node1node2)
initTreeNode(node11node3node4)
initTreeNode(node22node5node6)
initTreeNode(node33node7node8)
initTreeNode(node44node9node10)
initTreeNode(node55NULLNULL)
initTreeNode(node66NULLNULL)
initTreeNode(node77NULLNULL)
initTreeNode(node88NULLNULL)
initTreeNode(node99NULLNULL)
initTreeNode(node1010NULLNULL)
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()
}
44遍历结果显示
图441 构建线索二叉树
图441 construct the binary tree
构造图441线索二叉树遍历结果图442示：
图442 遍历结果
图442 iterate through the result
45线索二叉树插入模块
451线索二叉树插入模块设计思想
线索二叉树插入模块中假设需插入节点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]
452线索二叉树插入模块代码实现
void initTreeNode(TreeNode * tint valTreeNode * leftNodeTreeNode * rightNode)
{
t>dataval
t>LeftChildleftNode
t>RightChildrightNode
}
453线索二叉树插入模块结果
图453 插入模块结果
图453 the result of inserting a module
46线索二叉树删模块
461线索二叉树删模块设计思想
删线索二叉树时需考虑种情况分删节点叶节点中间节点者根节点
删节点叶节点时需判断删节点否右节点果前节点右节点需该父节点右孩子节点变量置空余线索需进行更改节点删[18]删叶节点左节点时该父节点左孩子置空然直接节点删
462线索二叉树删模块代码实现
void RemoveTreeNode(TreeNode * tint flag)
{
if (1 flag) {
t>LeftChild NULL
}
else {
t>RightChild NULL
}
463线索二叉树删模块结果
图463 删模块结果
图463 the result of deleting a module
结
文设计新线索二叉树遍历时访问速度明显传统线索二叉树更快然文设计线索二叉树传统二叉树数类型栈变量相层次二叉树时占定数空间占数空间计算机拥庞数空间言新线索二叉树运行时需数空间微足道遍历法时节点指前驱者继指针必出现线索断裂情况遍历线索二叉树结构时基线索二叉树做常规线性栈访问逻辑传统二叉树理解
数结构计算机技术中非常基础门知识高校计算机专业必修课程数结构课程讲授数组织方法现实生活中问题描述出门课程理知识较难需量实践算学生理知识学扎实运知识处理实际问题时会问题需学生量反复实践知识着更加深刻理解
参考文献
[1]薛晓亚浅谈学数结构[J]电脑知识技术201814(16)127+144
[2]杨晓波陈邦泽数结构演示实验类交互式微课设计实践[J]实验技术理201734(08)153157+171
[3]王军基道二叉树题教学案例辨析[J]福建电脑201733(05)7375
[4]沈华数结构课实践教学方案[J]实验室研究探索201332(10)396400
[5]杨晓波陈邦泽线索二叉树视化实现[J]西北师范学学报(然科学版)201349(01)4649
[6]郭春王红线索二叉树算法实验实现[J]泰山学院学报201133(06)4045
[7]徐翀徐建数结构象化教学方式探讨实践[J]中国现代教育装备2011(09)104106
[8]胡慧数结构线索二叉树应[J]煤炭技术201029(06)174176
[9]胡树杰喻红婕线索二叉树算法改进[J]沈阳理工学学报200827(06)1820
[10]汪心刘斯远数结构中干遍历知识点贯通式教学[J]江西广播电视学学报2008(04)102103
[11]马变芳张丽种优化线索二叉树方法[J]福建电脑2008(11)87
[12]索红军二叉树静态二叉链表存储[J]渭南师范学院学报2008(02)6667
[13]葛建梅数结构课程教学方法改革思考[J]中国成教育2008(01)147148
[14]崔永赵良基相似线索二叉树汽车零部件拆卸序列生成回收模糊评价[J]现代制造工程2007(02)6670
[15]谷立东C语言实现二叉树遍历应[J]牡丹江教育学院学报2006(06)142143
[16]周敏瀛军浅谈二叉树线索化利线索进行遍历[J]农业网络信息2006(08)3335
[17]王振蔡金锭基线索二叉树辐射状配电网潮流计算[J]高电压技术2006(06)113115+118
[18]宋玲吕强数结构中二叉树教学方法探讨[J]山东电力高等专科学校学报2006(02)69
致 谢
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
摘
着时代断进步计算机技术发展数结构计算机技术发展中起巨作数结构构建出高效计算机算法坚实基础良数结构够提高算法效率时减少系统资源占[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
21数结构 2
22树结构定义 2
第3章 传统线索二叉树新线索二叉树区 3
31传统二叉树 3
32优化线索二叉树 5
33分析较 6
34线索二叉树实性 8
第4章 线索二叉树设计 9
41数结构设计 9
42线索二叉树创建模块 10
421 线索二叉树代码实现 10
43线索二叉树三种遍历 10
44遍历结果显示 17
45线索二叉树插入模块 17
451线索二叉树插入模块设计思想 17
452线索二叉树插入模块代码实现 18
453线索二叉树插入模块结果 18
46线索二叉树删模块 18
461线索二叉树删模块设计思想 18
462线索二叉树删模块代码实现 19
463线索二叉树插入模块结果 19
结 20
参考文献 21
致 谢 22
第1章 绪
二叉树种数结构计算机技术中应范围非常广泛程序设计中提高搜索算法效率会量种数结构二叉树工厂领域应非常广泛仅游戏开发中前较火工智广泛应着较强扩展性研究中运研究课题较二叉树运方面设计者基础求较高降低二叉树难度中加入新变量——线索原二叉树结构转变线索二叉树结构减低二叉树结构难度传统线索二叉树存线索连续现象说节点处需重新二叉树执行遍历操作找出前线索序执行遍历操作时需时间较长占系统资源较文提出种全新线索二叉树方便简化遍历程
第2章 数结构中非线性结构—树型结构应
21数结构
数结构出现程序设计更加方便量数存储方式数处理方式检验程序效率方式设计数结构否合理结构图描述计算机逻辑方式数结构做算法中节点设计合理数结构算法效率达高需算法进行优化衡量算法效率重标准算法执行时间算法步需时间越短算法效率越高树形结构描述具层次关系方式够帮助设计者理清算法逻辑帮助查找问题线索二叉树建立遍历二叉树程序基础构建单独函数封装方式线索二叉树功分解插入删等功够提高获取继前驱节点效率减少算法执行时间提高算法效率[3]
22树结构定义
树形结构常表示信息方式属种信息嵌套表达方式树形结构具层结构层外层结构相[4]遍历树形结构时采递种高效遍历方式树结构基形式图22示
A
B
C
D
E
F
G
H
I
J
图22 典树形结构
图22 classic tree structure
中A整树形结构根节点BCD节点节点A子节点B节点A节点左子节点C节点A节点中子节点D节点A节点右子节点BCD节点子节点
树形结构具属性：
结点：结点树形结构组成基数元素图1中ABC节点做树形结构结点
树度：整树结构中拥节点数图1中A节点拥节点数3B节点C节点D节点拥节点数分312整树结构拥节点数3树度3
叶子节点：整树结构中底层节点称叶子节点树形结构现实中树表示相反树形结构中层节点成根节点底层节点称叶子节点连接根节点叶子节点节点成中间节点图中A节点树形结构根节点EFGHJI节点树形结构叶子节点BCD节点连接根节点叶子节点中间节点称中间节点
父节点子节点：树形结构中认节点前驱节点认该节点父节点节点继认该节点子节点图1：B节点例B节点前驱节点A节点认A节点B节点父节点B节点继节点EFG节点EFG节点B节点子节点
堂兄弟：节点着父节点节点成堂兄弟图1中BCD节点父节点BCD节点间关系称堂兄弟[5]
树层次深度：树层次般情况树深度相等根节点树形结构层次深度认1果根节点拥者子节点子节点没继节点时树形结构层次深度2子节点层次父节点层次加1计算树层次深度时根节点叶子节点节点数图1示树形结构树层次深度3[6]
第3章 传统线索二叉树新线索二叉树区
31传统二叉树
二叉树树形结构典树形结构区典树形结构节点子节点二叉树树形结构中节点两字节点子节点法左子节点右子节点果字节子节点时子节点默认左子节点二叉树树形结构图311：
图311 二叉树树形结构
图311 the tree structure of a binary tree
先序遍历中序遍历序遍历种三种遍历方式二叉树遍历方式
先序遍历遍历思想：先序遍历首选访问树形结构根节点然访问根节点左子节点继续访问根节点左子节点左子节点全部左子节点访问完毕然访问左子节点堂兄弟右子节点次访问直节点访问完成
中序遍历法：找根节点底层左子节点底层左子节点开始访问然访问左子节点父节点访问父节点右节点访问父节点父节点访问父节点父节点右子节点次访问直树形结构节点访问完毕
续遍历法：先找根节点根根节点找左子叶节点访问根节点左子叶节点然访问左子叶节点堂兄弟右子叶节点访问左子叶节点右子叶节点父节点根规律二叉树存节点访问完毕
32优化线索二叉树
通传统二叉树数结构发现节点处没办法准确找出节点前驱继线索果找前节点线索时需次遍历整二叉树找出该节点线索传统二叉树数结构中存放线索连续方存断开情况[7]更处理种现象文重新定义二叉树数结构数结构：
Lchild
LTag
Data
RTag
rchild
文设计数结构致传统二叉树结构相数结构中新添加栈数变量存储该节点线索说指存储节点前驱继种数结构遍历时够确保线索连贯性寻找出前节点前驱继重新遍历整二叉树
种改进基思想：
先序遍历：栈引入前节点赋值根节点节点空时该节点入栈然指左子入栈直左子空前栈顶出栈找右子右子空继续出栈右子时右子入栈找右子左子直空[8] 图32
开始
前节点赋值根节点
节点否空？
结束
指左子树
指右子树
印入栈
否
找左子树取栈顶
取出左子树
否空？
否
图32 线索二叉树先序遍历流程图
图32 a preorder traversal flowchart of a clue binary tree
然实际运中构造线索二叉树定完全采种数结构定缺陷种数结构函数中较繁琐必须理清节点节点间关系防止出现意外访问导致算法出现预知错误
文设计线索二叉树数结构传统线索二叉树数结构时运衡二叉树时文设计线索二叉树数结构占定优势文设计线索二叉树数结构遍历时需判断前节点否右子节点果右子节点栈中需存放继数线索果前节点左子节点时需判断否存兄弟右子节点果存右子节点出栈果前节点存兄弟右子节点栈中需存放右子节点线索然文设计数结构二叉树构建时需判断情况较采遍历法遍历线索二叉树效率传统线索二叉树结构效率高[9]
33分析较
文设计二叉树结构传统二叉树结构相传统二叉树数结构访问序图331
图331 传统二叉树结构先序线索指
图331 preorder clues of traditional binary tree structure
图331中实线箭头部分代表线索二叉树中继线索虚线箭头部分代表线索二叉树中前趋线索采文设计容线索间联系图312
图312 优化二叉树数结构线索指
图312 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）两种算法空间复杂度文设计二叉树结构传统二叉树空间复杂度略差
通两种算法时间复杂度空间复杂度两种算法差文设计线索二叉树弥补传统线索二叉树线索连续现象建立线索二叉树目遍历二叉树时递算法变迭代算法降低算法运行程中系统资源占
34线索二叉树实性
文中优化线索二叉树利栈进行线索二叉树调简略算法复杂性线索二叉树变方便快捷然节省系统资源没达目线索二叉树方传统二叉树效率高路器CIDR选择消息转发者跳时需进行信息匹配时采线索二叉树够极提高效率
第4章 线索二叉树设计
41数结构设计
文设计线索二叉树设计：
传统线索二叉树数结构设计：
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]弥补缺点文设计数结构新增兄弟数变量节点线索连续
结构体中变量取值范围定义：
LchildRchild部分区域存放数容受LTagRTag取值决定：
LTag取值0时Lchild存储数容前节点左孩子果LTag取值1时Lchild存储数容前节点前趋RTag取值0时rchild存储类型该节点右子节点果RTag取值等1时Rchild存贮数容该节点继Top指针指栈中栈顶位置
42线索二叉树创建模块
421 线索二叉树代码实现
Bitree *crt_bt_pre(bitree *bt){
Char ch
Chgetchar( )
If(ch＃’)
Btnull
Else{
Bt(bitree *)malloc(sizeof(bitree))
Bt>datac
Bt>lchildcrt_bt_pre(bt>lchild)
Bt>rchildcrt_bt_pre(bt>rchild)
}
Return(bt)
}
43线索二叉树三种遍历
#include
#include
typedef struct TreeNode
{
int data
struct TreeNode * LeftChild
struct TreeNode * RightChild
} TreeNode
void initTreeNode(TreeNode * tint valTreeNode * leftNodeTreeNode * rightNode)
{
t>dataval
t>LeftChildleftNode
t>RightChildrightNode
}
typedef struct MyStack
{
TreeNode *a[100]
int top
}MyStack
void initMyStack(MyStack *ms)
{
ms>top0
}
void push(MyStack *ms TreeNode *n)
{
ms>a[ms>top]n
ms>top++
}
int isEmpty(MyStack *ms)
{
if(ms>top0)
{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>top1]
}
void PreOrder(TreeNode *root)*非递前序遍历*
{
TreeNode * temp
MyStack * s (MyStack*)malloc(sizeof(MyStack))
initMyStack(s)
temp root*前节点赋值根节点*
while(tempNULL || isEmpty(s))
{
while(tempNULL)
{
printf(d |temp>data)*前节点空说明面节点直接印*
push(stemp)*该节点入栈*
temptemp>LeftChild*指左子*
}*直接印左子入栈指左子子直空*
if(isEmpty(s))*没左子栈顶印出左子*
{
temp pop(s)*取出该左子*
temptemp>RightChild*找右子没空进入面while继续操作直指右子*
}*印右子右子入栈找右子没左子没次进入if判断继续取出栈顶*
}
}
void InOrder(TreeNode *root)*非递中序遍历*
{
TreeNode * temp root
MyStack * s (MyStack*)malloc(sizeof(MyStack))
initMyStack(s)
push(stemp)
temproot>LeftChild*先序类似先指左子*
while(temp NULL || isEmpty(s))
{
while(tempNULL)
{
push(stemp)*左子空入栈继续找左子直没左子*
temptemp>LeftChild
}
temppop(s)*时印栈顶层左子*
printf(d |temp>data)
temptemp>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(tempNULL)
{
push(stemp)
Tag[s>top]0*前栈顶标记没印做入栈*
temptemp>LeftChild*指左子继续入栈直没左子*
}
while (isEmpty(s)&&Tag[s>top]1)*果发现栈顶标记1取出栈顶印*
{
temppop(s)
printf(d |temp>data)
}
if (isEmpty(s))*没左子光标定位栈顶栈顶没右子栈顶标记1准备印*
{
Tag[s>top]1
temptop(s)
temptemp>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(rootNode0node1node2)
initTreeNode(node11node3node4)
initTreeNode(node22node5node6)
initTreeNode(node33node7node8)
initTreeNode(node44node9node10)
initTreeNode(node55NULLNULL)
initTreeNode(node66NULLNULL)
initTreeNode(node77NULLNULL)
initTreeNode(node88NULLNULL)
initTreeNode(node99NULLNULL)
initTreeNode(node1010NULLNULL)
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()
}
44遍历结果显示
图441 构建线索二叉树
图441 construct the binary tree
构造图441线索二叉树遍历结果图442示：
图442 遍历结果
图442 iterate through the result
45线索二叉树插入模块
451线索二叉树插入模块设计思想
线索二叉树插入模块中假设需插入节点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]
452线索二叉树插入模块代码实现
void initTreeNode(TreeNode * tint valTreeNode * leftNodeTreeNode * rightNode)
{
t>dataval
t>LeftChildleftNode
t>RightChildrightNode
}
453线索二叉树插入模块结果
图453 插入模块结果
图453 the result of inserting a module
46线索二叉树删模块
461线索二叉树删模块设计思想
删线索二叉树时需考虑种情况分删节点叶节点中间节点者根节点
删节点叶节点时需判断删节点否右节点果前节点右节点需该父节点右孩子节点变量置空余线索需进行更改节点删[18]删叶节点左节点时该父节点左孩子置空然直接节点删
462线索二叉树删模块代码实现
void RemoveTreeNode(TreeNode * tint flag)
{
if (1 flag) {
t>LeftChild NULL
}
else {
t>RightChild NULL
}
463线索二叉树删模块结果
图463 删模块结果
图463 the result of deleting a module
结
文设计新线索二叉树遍历时访问速度明显传统线索二叉树更快然文设计线索二叉树传统二叉树数类型栈变量相层次二叉树时占定数空间占数空间计算机拥庞数空间言新线索二叉树运行时需数空间微足道遍历法时节点指前驱者继指针必出现线索断裂情况遍历线索二叉树结构时基线索二叉树做常规线性栈访问逻辑传统二叉树理解
数结构计算机技术中非常基础门知识高校计算机专业必修课程数结构课程讲授数组织方法现实生活中问题描述出门课程理知识较难需量实践算学生理知识学扎实运知识处理实际问题时会问题需学生量反复实践知识着更加深刻理解
参考文献
[1]薛晓亚浅谈学数结构[J]电脑知识技术201814(16)127+144
[2]杨晓波陈邦泽数结构演示实验类交互式微课设计实践[J]实验技术理201734(08)153157+171
[3]王军基道二叉树题教学案例辨析[J]福建电脑201733(05)7375
[4]沈华数结构课实践教学方案[J]实验室研究探索201332(10)396400
[5]杨晓波陈邦泽线索二叉树视化实现[J]西北师范学学报(然科学版)201349(01)4649
[6]郭春王红线索二叉树算法实验实现[J]泰山学院学报201133(06)4045
[7]徐翀徐建数结构象化教学方式探讨实践[J]中国现代教育装备2011(09)104106
[8]胡慧数结构线索二叉树应[J]煤炭技术201029(06)174176
[9]胡树杰喻红婕线索二叉树算法改进[J]沈阳理工学学报200827(06)1820
[10]汪心刘斯远数结构中干遍历知识点贯通式教学[J]江西广播电视学学报2008(04)102103
[11]马变芳张丽种优化线索二叉树方法[J]福建电脑2008(11)87
[12]索红军二叉树静态二叉链表存储[J]渭南师范学院学报2008(02)6667
[13]葛建梅数结构课程教学方法改革思考[J]中国成教育2008(01)147148
[14]崔永赵良基相似线索二叉树汽车零部件拆卸序列生成回收模糊评价[J]现代制造工程2007(02)6670
[15]谷立东C语言实现二叉树遍历应[J]牡丹江教育学院学报2006(06)142143
[16]周敏瀛军浅谈二叉树线索化利线索进行遍历[J]农业网络信息2006(08)3335
[17]王振蔡金锭基线索二叉树辐射状配电网潮流计算[J]高电压技术2006(06)113115+118
[18]宋玲吕强数结构中二叉树教学方法探讨[J]山东电力高等专科学校学报2006(02)69
致 谢
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档