数据结构实验十一 线索二叉树的中序遍历

简介: 数据结构实验十一 线索二叉树的中序遍历

一、实验目的

1.理解线索二叉树的存储结构;

2.熟练掌握线索二叉树的生成、遍历等常见操作

二、实验内容及步骤

(一)实验内容

1. 练习线索二叉树的建立与存储

2. 练习线索二叉树的遍历

(二)实验步骤

建立线索二叉树,并通过调用函数,输出中序遍历的结果。

1. #include<iostream>
2. using namespace std;
3. 
4. //二叉树的二叉线索类型存储表示
5. typedef struct BiThrNode
6. {        
7.  char data;
8.  struct BiThrNode *lchild,*rchild;
9.  int LTag,RTag;  
10.   }BiThrNode,*BiThrTree;
11. 
12. //全局变量pre
13. BiThrNode *pre=new BiThrNode;
14. 
15. //用算法5.3建立二叉链表
16. void CreateBiTree(BiThrTree &T)
17. { 
18.   //按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T
19.   char ch;
20.   cin >> ch;
21.   if(ch=='#')  T=NULL;      //递归结束,建空树
22.   else
23.   {             
24.     T=new BiThrNode;
25.     T->data=ch;         //生成根结点
26.     CreateBiTree(T->lchild);  //递归创建左子树
27.     CreateBiTree(T->rchild);  //递归创建右子树
28.   }               //else
29. }                 //CreateBiTree
30. 
31. //用算法5.7以结点P为根的子树中序线索化
32. void InThreading(BiThrTree p)
33. {
34.   //pre是全局变量,初始化时其右孩子指针为空,便于在树的最左点开始建线索
35.   if(p)
36.   {
37.     InThreading(p->lchild);                   //左子树递归线索化
38.     if(!p->lchild)
39.     {                                 //p的左孩子为空
40.       p->LTag=1;                                  //给p加上左线索
41.       p->lchild=pre;                //p的左孩子指针指向pre(前驱)
42.     } 
43.     else
44.       p->LTag=0;
45.     if(!pre->rchild)
46.     {                       //pre的右孩子为空
47.       pre->RTag=1;                          //给pre加上右线索
48.       pre->rchild=p;                          //pre的右孩子指针指向p(后继)
49.     }
50.     else
51.       pre->RTag=0;
52.     pre=p;                                //保持pre指向p的前驱
53.     InThreading(p->rchild);                     //右子树递归线索化
54.     }
55. }//InThreading
56. 
57. //用算法5.8带头结点的中序线索化
58. void InOrderThreading (BiThrTree &Thrt,BiThrTree T)
59. {
60.   //中序遍历二叉树T,并将其中序线索化,Thrt指向头结点
61.   Thrt=new BiThrNode;             //建头结点
62.   Thrt->LTag=0;                     //头结点有左孩子,若树非空,则其左孩子为树根
63.   Thrt->RTag=1;                   //头结点的右孩子指针为右线索
64.   Thrt->rchild=Thrt;                //初始化时右指针指向自己
65.   if(!T)  Thrt->lchild=Thrt;        //若树为空,则左指针也指向自己
66.   else
67.   {
68.     Thrt->lchild=T;  pre=Thrt;    //头结点的左孩子指向根,pre初值指向头结点
69.     InThreading(T);                 //调用算法5.7,对以T为根的二叉树进行中序线索化
70.     pre->rchild=Thrt;               //算法5.7结束后,pre为最右结点,pre的右线索指向头结点
71.     pre->RTag=1;                 
72.     Thrt->rchild=pre;               //头结点的右线索指向pre
73.   }
74. }                     //InOrderThreading
75. 
76. void InOrderTraverse_Thr(BiThrTree T)
77. { BiThrNode *p;
78. //T指向头结点,头结点的左链lchild指向根结点,可参见线索化算法5.8。
79. //中序遍历二叉线索树T的非递归算法,对每个数据元素直接输出
80.   p=T->lchild;
81.   while(p!=T)
82. {
83.   while(p->LTag==0) p=p->lchild;
84.   cout<<p->data;
85.   while(p->RTag==1&&p->rchild!=T)
86.   {
87.     p=p->rchild;cout<<p->data;  
88.   }
89.   p=p->rchild; 
90. }}                          
91. int main()
92. {
93.   pre->RTag=1;
94.   pre->rchild=NULL;
95.   BiThrTree tree,Thrt;
96.   cout<<"请输入建立二叉链表的序列:\n";
97.   CreateBiTree(tree);
98.   InOrderThreading(Thrt,tree);
99.   cout<<"中序遍历线索二叉树的结果为:\n";
100.  InOrderTraverse_Thr(Thrt);
101.  cout<<endl;
102.  return 0;
103. }
目录
相关文章
|
18天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
18天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
15 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
19天前
|
Java
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
【用Java学习数据结构系列】震惊,二叉树原来是要这么学习的(二)
24 1
|
17天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
18天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
16 0
|
18天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
18天前
初步认识栈和队列
初步认识栈和队列
44 10
|
12天前
数据结构(栈与列队)
数据结构(栈与列队)
13 1
|
18天前
|
算法
数据结构与算法二:栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式
这篇文章讲解了栈的基本概念及其应用,并详细介绍了中缀表达式转换为后缀表达式的算法和实现步骤。
33 3
|
16天前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
为什么基础数据类型存放在栈中,而引用数据类型存放在堆中?
53 1