线索二叉树的应用（如何实现二叉树的线索化）

本文目录

• 如何实现二叉树的线索化
• 线索二叉树的应用
• 数据结构线索二叉树的应用（急！）求大神帮忙！！！
• 介绍下二叉树
• 线索二叉树有什么用它的目的是为了节省空间，方便遍历，可是我觉得不会啊、求指教
• 为什么要建立线索二叉树
• 线索二叉树的应用特别是线索的输出结点的插入和删除
• 什么是线索二叉树,为什么要使用线索二叉树

如何实现二叉树的线索化

1. 先把二叉树给标记化：既设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。

2. 先序遍历线索二叉树：

3. 首先进行先序遍历，然后把得到的节点依次入队；

4. 然后把队列里除了根节点以外的节点依次根据标记，队里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。

5. 中序遍历线索二叉树：

6. 首先进行中序遍历，然后把得到的节点依次入队

7. 然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。

8. 后序遍历线索二叉树：

9. 首先进行后序遍历，然后把得到的节点依次入队

10. 然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1。

11. 树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。

12. 树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树。

线索二叉树的应用

#include《stdio.h》
#include《stdlib.h》
typedef struct Btreenode
{
struct Btreenode *lchild,*rchild;
char data;
}Bitreenode,*Bitree;
//初始化
Bitree Initree()
{
Bitree p;
p=(Bitreenode *)malloc(sizeof(Bitreenode));
p-》lchild=p-》rchild=NULL;
return p;
}
//创建二叉树 ABD#GJ##K##E##C#FH##IL### ABCD##E###F#GH##I#J#K##
void Creat(Bitree *p) //指向指针的指针
{
char ch=getchar();
if(ch==’#’)
(*p)=NULL;
else
{
//Bitree k;
*p=(Bitreenode *)malloc(sizeof(Bitreenode));
(*p)-》data=ch;
Creat(&(*p)-》lchild);
Creat(&(*p)-》rchild);
}
//return 1;
}
//先序遍历
void First(Bitree p)
{
if(p)
{
printf(“%2c“,p-》data);
First(p-》lchild);
First(p-》rchild);
}
}
//中序遍历
void Middle(Bitree p)
{
if(p)
{
Middle(p-》lchild);
printf(“%2c“,p-》data);
Middle(p-》rchild);
}
}
//后序遍历
void Last(Bitree p)
{
if(p)
{
Last(p-》lchild);
Last(p-》rchild);
printf(“%2c“,p-》data);
}
}
//求二叉树的深度
//若一棵二叉树为空,则其深度为0;
//否则其深度等于左子树和右子树的最大深度加1
int DeepBitree(Bitree p)
{
int deep1,deep2;
if(p==NULL)return(0);
else
{ deep1=DeepBitree(p-》lchild);
deep2=DeepBitree(p-》rchild);
if(deep1》deep2)return(deep1+1);
else return(deep2+1);
}

}
//在二叉树中查找值为x的结点
void search(Bitree *q,char x,Bitree *p)
{
if((*q)-》data==x) *p=*q;
else
{
if((*q)-》lchild) search(&(*q)-》lchild,x,&(*p));
if((*q)-》rchild) search(&(*q)-》rchild,x,&(*p));
}
//return NULL;
}
//求叶子结点数目
int k=0;
void leaf(Bitree p)
{
if(p)
{
leaf(p-》lchild);
if(!p-》lchild && !p-》rchild) k++;
leaf(p-》rchild);
}
//return k;
}
//删除左子树
void Search_lchild(Bitree *p,char parents,Bitree *k)
{

if ((*p)-》data==parents)
{
if((*p)-》lchild)
{
*k= (*p)-》lchild ; //查找左子树
//Deletel(*k);
}
}
else
{
if((*p)-》lchild) Search_lchild(&(*p)-》lchild,parents,&(*k));
if((*p)-》rchild) Search_lchild(&(*p)-》rchild,parents,&(*k));
}
}
void Deletel(Bitree *p)
{
Bitree *t;
t=p;
if((*t))
{
Deletel(&(*t)-》lchild);
Deletel(&(*t)-》rchild);
free(*t);
//(*p)=NULL;
}
//(*p)=NULL;
}
//插入左结点
void Insert_lchild(Bitree *p,char childl,char child)
{
Bitree q,k;
if(*p)
{
if((*p)-》data==childl) //找到结点
{
q=(Bitree)malloc(sizeof(Bitree));
q-》data=child;
if(!(*p)-》lchild) //左结点不存在
{
(*p)-》lchild=q;
(*p)-》lchild-》lchild=NULL;
(*p)-》lchild-》rchild=NULL;
}
else //左结点存在
{
k=(*p)-》lchild;
(*p)-》lchild=q;
q-》lchild=k;
}
}
else
{
Insert_lchild(&(*p)-》lchild,childl,child);
Insert_lchild(&(*p)-》rchild,childl,child);
}
}
}
void main()
{
printf(“请输入二叉树（例如:AB##C##）:“);
Bitree p=Initree(); //ABCE##F##D##G##
//Bitree p=NULL;
Creat(&p);

//先、中、后序遍历
printf(“先序遍历为：“);
First(p);
printf(“\n“);
printf(“中序遍历为：“);
Middle(p);
printf(“\n“);
printf(“后序遍历为：“);
Last(p);
printf(“\n“);
//求二叉树的深度
int deep=DeepBitree(p);
printf(“二叉树的深度为:%d\n“,deep);
//输出二叉树
//print(p);
//查找数据元素
char s;
Bitree q=NULL;
printf(“输入要查找的元素:“);
getchar();
scanf(“%c“,&s);
/*Bitree T=search(&p,s);
if(T)
printf(“要查找的元素为：%c\n“,T-》data);
else
printf(“要查找的元素不存在\n“);*/
search(&p,s,&q); //******
if(q)
printf(“要查找的元素为：%c\n“,q-》data);
else
printf(“要查找的元素不存在\n“);
//求叶子结点的数目
leaf(p);
printf(“二叉树叶子结点的个数为：%d\n“,k);
//删除操作
//删除左子树
getchar();
char parents;
scanf(“%c“,&parents);
Bitree T=NULL;
search(&p,parents,&q);
Search_lchild(&p,parents,&T);
if(T) printf(“左子树为:%c\n“,T-》data); else printf(“不符合要求\n“);
printf(“删除左子树后为: “);
Deletel(&T);
q-》lchild=NULL;
First(p);
printf(“\n“);
//删除右子树与左子树相似
//插入左结点
char childl,child;
printf(“输入要插入的结点:“);
getchar();
scanf(“%c %c“,&childl,&child);
Insert_lchild(&p,childl,child);
First(p);
printf(“\n“);
}

数据结构线索二叉树的应用（急！）求大神帮忙！！！

你好！
嗯。。。你看看。。。
你应该输入：
ab##c#d##
就是说当某一个节点的左右子树为
空，
那么就应该输入一个#
，叶子的左右节点也不例外。。。
祝：事事顺心。。。
希望对你有所帮助，望采纳。

介绍下二叉树

基本定义：
二叉树是每个结点最多有两个子树的有序树。
度就是结点的分支数，二叉树结点的度可能是0、1、2。
度为0的结点，称为叶结点。
以组成该树各结点中最大的度作为该树的度
树高也就是树的深度，指组成该树各结点的最大层次
完全二叉树就是指只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
满二叉树就是指除了叶结点外每一个结点都有左右子叶，且叶结点都处在最底层的二叉树
二叉树的应用：包括二叉树的建立、遍历、叶结点数、高度、左右子结点互换、等价性判断、复制、二叉搜索树的创建、线索二叉树的创建、搜索已知结点的层数、前中序确定二叉树等等
C语言的实现：
二叉树的链式存储
typedef struct node *tree_pointer;
struct node{
char ch;
tree_pointer left_child,right_child;
};
二叉树的建立
tree_pointer create(tree_pointer ptr)
{
char ch;
scanf(“%c“,&ch);
if(ch==’ ’)
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr-》ch=ch;
ptr-》left_child=create(ptr-》left_child);
ptr-》right_child=create(ptr-》right_child);
}
return ptr;
}
二叉树的前序遍历
void preorder(tree_pointer ptr)
{
if(ptr){
printf(“%c“,ptr-》ch);
preorder(ptr-》left_child);
preorder(ptr-》right_child);
}
}
二叉树的中序遍历
void inorder(tree_pointer ptr)
{
if(ptr){
inorder(ptr-》left_child);
printf(“%c“,ptr-》ch);
inorder(ptr-》right_child);
}
}
二叉树的后序遍历
void postorder(tree_pointer ptr)
{
if(ptr){
postorder(ptr-》left_child);
postorder(ptr-》right_child);
printf(“%c“,ptr-》ch);
}
}
二叉树的层序遍历
void level_order(tree_pointer ptr)
{
if(!ptr)
printf(“The tree is null\n“);
else{
pushq(&rear,ptr);
for(;;){
ptr=popq(&front,rear);
if(ptr){
printf(“%c“,ptr-》ch);
if(ptr-》left_child)
pushq(&rear,ptr-》left_child);
if(ptr-》right_child)
pushq(&rear,ptr-》right_child);
}
else break;
}
}
}
二叉树的叶结点数求解
int leaf(tree_pointer ptr)
{
if(!ptr)
return 0;
else{
if(!ptr-》left_child&&!ptr-》right_child)
return 1;
return leaf(ptr-》left_child)+leaf(ptr-》right_child);
}
}
二叉树的高度求解
int height(tree_pointer ptr)
{
if(!ptr)
return 0;
return 1+max(height(ptr-》left_child),height(ptr-》right_child));//构造max函数，返回较大值
}
二叉树的左右子结点互换
void exchange(tree_pointer ptr)
{
tree_pointer temp;
if(ptr){
temp=ptr-》left_child;
ptr-》left_child=ptr-》right_child;
ptr-》right_child=temp;
exchange(ptr-》right_child);
exchange(ptr-》left_child);
}
}
二叉树的等价性判断
int equal(tree_pointer first,tree_pointer second)
{
return((!first&&!second)
||(first&&second&&(first-》ch==second-》ch)
&&equal(first-》left_child,second-》left_child)
&&equal(first-》right_child,second-》right_child)));
}
二叉树的复制
tree_pointer copy(tree_pointer original)
{
tree_pointer temp;
if(original){
temp=(tree_pointer)malloc(sizeof(node));
temp-》left_child=copy(original-》left_child);
temp-》right_child=copy(original-》right_child);
temp-》ch=original-》ch;
return temp;
}
return NULL;
}
后面的应用程序相对比较大，不一一C语言实现了，值得一提的是二叉树的C语言实现一般采用递归的方式。

线索二叉树有什么用它的目的是为了节省空间，方便遍历，可是我觉得不会啊、求指教

可以看看这篇博客网页链接

简单的说，新增的两个变量都是布尔类型，占用的空间要远小于指针变量。

另外任何二叉树都有空指针域，并且空指针域总是多于非空指针域，也就是说，有一半多的内存是浪费的。

为什么要建立线索二叉树

摘要
您好，线索二叉树减少了的空指针域的同时又对每个节点增加了两个标志位。

如果要遍历树可以用栈或者队列或者递归，那线索二叉树的意义是什么？莫不是学者们强迫症犯了就为了减少空指针域的个数。

书上写着引入线索二叉树是为了加快查找节点前驱和后继的速度，而个人觉得线索二叉树在建立的时候使得树的建立变得复杂了一点点，从逻辑上去想也变得复杂，觉得有点吃力不讨好。

除了考试时可能会考到线索二叉树，其他的用处暂时没发现，有缘再见线索二叉树吧。

咨询记录 · 回答于2021-12-20

为什么要建立线索二叉树

您好，您的问题我已经看到了，正在整理答案，请稍等一会儿哦

您好，线索二叉树减少了的空指针域的同时又对每个节点增加了两个标志位。

如果要遍历树可以用栈或者队列或者递归，那线索二叉树的意义是什么？莫不是学者们强迫症犯了就为了减少空指针域的个数。

书上写着引入线索二叉树是为了加快查找节点前驱和后继的速度，而个人觉得线索二叉树在建立的时候使得树的建立变得复杂了一点点，从逻辑上去想也变得复杂，觉得有点吃力不讨好。

除了考试时可能会考到线索二叉树，其他的用处暂时没发现，有缘再见线索二叉树吧。

Hanoi问题递归算法的时间复杂度怎么算出来的

算法如下：

        解释：size表示汉诺塔的规模，startStack表示汉诺塔起始，endStack 表示完成，midStack表示辅助      

        def Towers(size,startStack,endStack,midStack):

                if size == 1:

                    print ’Move disk from ’, firstStack, ’to ’, endStack

                else:

                    Towers(size-1,firstStack,midStack,endStack)

                    Towers(1,firstStack,endStack,midStack)

                    Towers(size-1,midStack,endStack,firstStack)

分析：问题规模设置为n，T（n）为问题规模所需步骤，

      T（n）=1+T(1)+2T（n-1）//规模为n-1时要经过两次，所以为2T（n-1）

            =1+2+2T(n-1)     //当规模为1时需要两步，因此为T（1）=2

            =3+2[3+2T（n-2)] //规模为n-2时，重复上述操作

            =9+4T（n-2）   

            =9+4[3+2T(n-3)]

            =21+8T(n-3)

            ......    

            =C+2^kT(n-k)

当n-k=1时，得到k=n-1，

      T（n）=C+2^(n-1)T(1)//其中T（1）=2

      T（n）=C+2^n

综上：汉诺塔时间复杂度为O(2^n)    

注：算法采用Python语言编写

可以麻烦换成C++语言的吗

上面就是C语言哦

希望我的回答对您有所帮助，如果觉得有用的话，记得给个赞哦 太感谢您了，您的支持是我最大的动力。祝您生活愉快，平安健康每一天

线索二叉树的应用特别是线索的输出结点的插入和删除

先把二叉树给标记化（把二叉树遍历一遍）：既设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。
建一个队列，根据你的遍历方式进行入队，
比如先序遍历，就把visit到的元素依次入队，特别注意，中序遍历或后序遍历visit是从左下角开始的，不是根节点，如果还是不懂，就把输出元素那行改成入队的代码就ok了
然后如果Ltag=1，此时把左孩子指针回指队里前一个元素，这个元素就是前驱节点，然后往队尾依次进行线索化，同理，后继的话为Rtag=1时，你也应该知道怎么弄了吧。
如果lz觉得回答还不错的话，注意给分哦
刚才少说了一个，队里的第一个元素的的标记Ltag=0，因为没有前驱

什么是线索二叉树,为什么要使用线索二叉树

在有n个结点的二叉链表中必定存在n+1个空指针域，因此可以利用这些空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针，这种指向前趋和后继结点的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树被称为线索二叉树，相当于一个双向链表
相比二叉树而言可以更好的找到某个节点的前驱和后继