精华内容
下载资源
问答
  • 2021-02-12 06:06:58

    将一棵普通二叉树转换为一棵线索二叉树(查看定义)。

    详细说明:树结点除了包含left, right指针外,还包含isLeftThread和isRightThread,初始时isLeftThread和isRightThread都为false。对于left为null的结点,请将left设置为中序遍历该结点的前驱结点,并将isLeftThread设置为true。对于right为null的结点,请将right设置为中序遍历该结点的后继结点,并将isRightThread设置为true。

    提示:请尝试使用非递归

    第一反应还是中序遍历然后递归,先忽略提示使用非递归吧。

    又是对着错的测试用例然后改了下代码才A过。

    /*树结点的定义(请不要在代码中定义该结构)

    struct TreeNode {

    TreeNode *left, *right;

    bool isLeftThread, isRightThread;

    }*/

    void inorder(TreeNode* root,TreeNode*& pre,int& preNeedSet);

    void convertToThreadedTree(TreeNode *root) {

    if ( !root )

    return;

    TreeNode* pre=NULL;

    int preNeedSet=0;

    inorder(root,pre,preNeedSet);

    if (pre&&preNeedSet )

    pre->isRightThread=true;

    }

    void inorder(TreeNode* root,TreeNode*& pre,int& preNeedSet)

    {

    if (!root )

    return;

    inorder(root->left,pre,preNeedSet);

    if ( !root->left )

    {

    root->isLeftThread=true;

    if ( pre )

    {

    root->left = pre;

    }

    }

    if ( pre&&preNeedSet )

    {

    pre->isRightThread=true;

    pre->right=root;

    }

    pre=root;

    if (!root->right )

    preNeedSet=1;

    else

    preNeedSet=0;

    inorder(root->right,pre,preNeedSet);

    }

    更多相关内容
  • 线索二叉树

    2019-04-10 21:19:27
    通过前序序列创建线索二叉树 1:中序遍历 2:查找节点前驱后继 3:插入节点 4:删除节点 0:退出
  • 目录链式存储线索二叉树中序线索二叉树中序线索化实现实现的代码过程中序线索二叉树的遍历遍历...线索二叉树是二叉树的类,在看线索二叉树之前我们先看一下二叉树的链式存储。 原创文章 8获赞 9访问量 732 关注
  • 本文实例讲述了C语言实现线索二叉树的定义与遍历。分享给大家供大家参考,具体如下: #include #include typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // ...
  • 线索二叉树分为三类:对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化,被线索化了的二叉树称为线索二叉树。为什么需要线索二叉树?知道了“前驱”和“后继”信息,就可以把二叉树看作个...

    d4c58e08d03da5ff80b056f12c1b8204.png

    更新:

    为了让文章篇幅不太长,我将指针的引用部分另外写成了一篇文章。

    如果有需要,还请自行踱步。

    Nice小夫:#图解 轻松看懂指针的引用*&​zhuanlan.zhihu.com
    8f5b221ec9ce097f4c4ed73585358368.png

    什么是线索二叉树?

    线索二叉树分为三类:

    55883eaf06e61824d5fe8c252048cc87.png

    对一棵二叉树中所有节点的空指针域按照某种遍历方式加线索的过程叫作线索化,被线索化了的二叉树称为线索二叉树。

    为什么需要线索二叉树?

    知道了“前驱”和“后继”信息,就可以把二叉树看作一个链表结构,从而可以像遍历链表那样来遍历二叉树,进而提高效率

    如何线索化二叉树

    这里例举了中序线索二叉树的方法

    一个二叉树通过如下的方法“串起来”

    所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继,所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。

    这句话我是借鉴了了另一位知友的总结,可以说是一看就懂了。

    但我并不满足于此,我要让这句话更加直观展现出来。

    fa54562b5051d7516bc5a0a51de603ab.png

    我这个图这样直观展示,是有意为之的。

    让你看到左孩子空,就会想到直接前驱右孩子空,就会想到直接后继

    线索二叉树的结构

    daa5690e90c782bcd4bd8466e536a70b.png
    线索二叉树节点结构

    标识域:

    1. 如果ltag=0,表示指向节点的左孩子。如果ltag=1,则表示lchild为线索,指向节点的直接前驱
    2. 如果rtag=0,表示指向节点的右孩子。如果rtag=1,则表示rchild为线索,指向节点的直接后继

    什么是前驱后继,不需要我解释了吧。

    所以对应的线索二叉树的节点定义如下:

    typedef 

    ebd60057f46d9657a3ad2f938fbcc6ba.png
    中序线索二叉树

    aeb1141e1e1da703af4cbcfbce00e54f.png
    二叉链表表示

    我们心目中的代码就是要将中序线索二叉树用二叉链表来实现。

    我们来一步一步的书写代码:

    约定:

    • 指针p指向当前正在访问的节点
    • pre指向p的前驱节点
    // 通过中序遍历对二叉树线索化的递归算法:
    

    通过中遍历建立中序线索二叉树的主要程序

    // 通过中遍历建立中序线索二叉树的主要程序
    

    遍历中序线索二叉树

    求以p为根的中序线索二叉树中,中序序列下的第一个节点。

    TBNode 

    求在中序线索二叉树中,节点p在中序下的后继节点。

    TBNode 

    中序线索二叉树上执行中序遍历的算法

    void 

    剩下的前序线索二叉树遍历和后序线索二叉树,套路还不是一样一样的?


    我的更多图解教程:

    Nice小夫:#图解 数据结构:树的存储结构​zhuanlan.zhihu.com
    4809bf25f793a6ac00175746e72696e9.png
    Nice小夫:#图解 数据结构:树和森林与二叉树的相互转换​zhuanlan.zhihu.com
    43376731d428f377752dc960d7cea027.png
    Nice小夫:#图解+动画 数据结构-循环链表:约瑟夫环问题(C语言实现)​zhuanlan.zhihu.com
    3d37b474f14a6f06f5a46f3d1b7a6929.png
    Nice小夫:#动画 算法初步:选择排序。过于简单!​zhuanlan.zhihu.com
    4d1ea89dd0b8ce996df3f5f1c02ad44c.png
    Nice小夫:#图解 必胜之策!生活中的博弈论:抓三堆问题。这四张图让你懂得一塌糊涂​zhuanlan.zhihu.com
    081c89d1458d852eaef4db507c0dd0d4.png
    Nice小夫:#图解+动画 不败法则!生活中的博弈论:简简单单躺赢。一张图让你彻彻底底搞明白!​zhuanlan.zhihu.com
    fde9bca0a4d4e217b131a44af7d1fc76.png
    Nice小夫:#图解 考研英语语法:状语从句​zhuanlan.zhihu.com
    60ff3db36066908c4401e96e6beffbde.png
    Nice小夫:#图解 考研英语语法:名词性从句​zhuanlan.zhihu.com
    dd4c2f49107de60b1ffb9819bfee3bee.png

    Nice!Nice!Nice!

    明白啦。

    4ac1c6ac73e4f27d4603d8ace7afdb53.png
    展开全文
  • (耐心看完) 首先你要用先序遍历或者其他遍历方式创建颗普通的二叉树 然后你要对这个普通的二叉树进行线索化 线索化有两种方式 种是带头结点 种是不带头结点的 线索化后 这就是线索二叉树了 然后你就...

    T   m这道题卡了我好几天 真 T   m心情非常烦躁哈 看CSDN上 那些人写的代码 写的不清不楚  你tama能不能写详细点啊 伪代码真的很恶心好吧?

    感谢中序线索化二叉树及遍历 - 百度文库

    带来的部分代码 好不容易看见的好代码

    还有那个严蔚敏的书 写的是什么乱七八糟的东西 细节也不交代清楚 看的我真的恶心死了 cao

    tama最后还不是得自己来写 真tm  zhizhang 连教学用书都写不好 详细点会死吗?Gross!你写不好我看nm的书呢?

    首先给大家讲一下 我写代码关于空指针和野指针的问题

    #include<iostream>
    using namespace std;
    struct student
    {
    student *p;
    student *q;
    }
    
    
    int main()
    {
    
        student* m;
    if(m)
        {
            cout<<"1";
        }
    else if(m==NULL)
        {
            cout<<"2";
        }
    
        student *i=new student
    if(i)
        {
            cout<<"3";
        }
    else if(i==NULL)
        {
            cout<<"4";
        }
    
    return 0;
    
    }

    大家先要明白这个野指针初始化的问题。上述代码 m如果没有new student的话 会报错所以输出不了

    而 i 进行了new student 所以可以 但只能输出3 i指针默认不是NULL所以不会输出4

    最后结果 这段代码 只会输出 :3

    然后我要讲一下线索化二叉树的思路

    线索化二叉树的步骤是什么,像现在给大家归纳一下。(耐心看完)

    1. 首先你要用先序遍历或者其他遍历方式创建一颗普通的二叉树
    2. 然后你要对这个普通的二叉树进行线索化 线索化有两种方式 一种是带头结点 一种是不带头结点的
    3. 线索化后 这就是一颗线索二叉树了 
    4. 然后你就可以用特定的遍历方法----遍历中序线索二叉树  来对这个二叉树进行遍历并同时输出
    5. 注意 对普通二叉树的中序遍历输出结果 和 线索化这颗二叉树后在对其进行遍历中序线索二叉树  二者的输出结果是等效的。 

    总结:

    建立普通二叉树--->带头结点线索化或者直接无头结点线索化----->中序遍历线索二叉树---->结果一

    建立普通二叉树-->中序遍历普通二叉树--->结果二

    结果一和结果二一模一样。

    这次我采用的是不带头节点的建立线索二叉树。

    函数板块主要有 建立树 线索化  遍历输出

    其中线索化 书上写的不清不楚的

     你所谓的全局变量初始化 你能不能写完写详细一点  ?

    你如果直接在全局区域写一个 student*pre;后面运行的时候是会报错的!!!!!!!!!

    有很多博客 就直接给你在全局区域这样写 student*pre错错错错!!!

    你要实体化student *pre=new student(对对对!)才行,这tama才叫初始化!  写得不清不楚的真的口区。

     还有我画五角星那一段 很明显就有问题    !pre->rchild 

    如果pre刚开始是空指针要怎么办?直接就报错了!

    正确的 代码我放在下面 大家自己对比一下

    void clue_tree(student *p)
    {
    	if (p)
    	{
    		clue_tree(p->left);
    
    		if (p->left==NULL)//左孩子为空链接前驱
    		{
    			p->left = pre;
    			p->tagleft = 1;
    		}
    		
    		if (pre!=NULL&&pre->right==NULL)//pre右孩子为空链接后驱
    		{
    			pre->right = p;
    			pre->tagright = 1;
    		}
    	
    		pre = p;
    		if (p->tagright == 0 && p->right == NULL)
    		{
    			p->tagright = 1;
    		}
    
    		clue_tree(p->right);
    	}
    
    
    }

    然后再和大家强调一下,书上这个中序遍历 是带头节点的中序遍历   一定看清楚。

    我接下来写的是不带头节点的遍历   

    如果你线索化的时候用的是不带头结点的线索化 那书上这个遍历方式就会报错

         接下来我们用例题来实验一下  

    23 线索二叉树:中序线索二叉树的遍历

    作者: 冯向阳时间限制: 1S章节: DS:树

    截止日期: 2022-06-30 23:55:00

    问题描述 :

    目的:使用C++模板设计中序线索二叉树的抽象数据类型(ADT)。并在此基础上,使用中序线索二叉树ADT的基本操作,设计并实现简单应用的算法设计。

    内容:(1)请参照二叉树的ADT模板,设计中序线索二叉树的抽象数据类型。(由于该环境目前仅支持单文件的编译,故将所有内容都集中在一个源文件内。在实际的设计中,推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件,以及网盘中的链表ADT原型文件,自行设计二叉树的ADT。)

    (2)ADT的简单应用:使用该ADT设计并实现若干遍历线索二叉树的算法设计。

    应用:要求设计一个算法,对建立的中序线索二叉树进行遍历。

    提示:中序遍历线索二叉树,首先找到第一个访问的结点,即最左下结点,然后通过查找后继结点的方法进行遍历。

    参考函数原型:

    中序线索二叉树的遍历(共有成员函数)

    //中序线索二叉树的遍历  

    template<class ElemType>

    void Thread_BinaryTree<ElemType>::InThreading_Traverse(Thread_BinaryTreeNode<ElemType> *root, bool (*visit)(Thread_BinaryTreeNode<ElemType> *root));

    输入说明 :

    第一行:表示无孩子或指针为空的特殊分隔符

    第二行:二叉树的先序序列(结点元素之间以空格分隔)

    输出说明 :

    第一行:中序线索二叉树的遍历结果

    输入范例 :

    #
    A B # C D # # E # # F # G # H # #

    输出范例 :

    B(1,0),D(1,1),C(0,0),E(1,1),A(0,0),F(1,0),G(1,0),H(1,1)

    student* find_next(student* & p)

    void clue_tree(student *p) 

    两个难点函数 好好理解

    注意看清楚 全局变量pre是怎么初始化的!!!

    #include<iostream>
    #include<stack>
    using namespace std;
    int m = 1;
    
    struct student
    {
    	string data;
    	student* left;
    	student* right;
    	int tagleft=0;
    	int tagright=0;
    };
    
    //先序建立二叉树
    void creat(student*& T, string kk)
    {
    	string ch;
    	cin >> ch;
    	if (ch == kk)
    	{
    		T = NULL;
    	}//但凡输入了#号 该节点下一位停止
    	else
    	{
    		T = new student;
    		T->data = ch;
    		creat(T->left, kk);
    		creat(T->right, kk);
    	}
    }
    
    //二叉树的线索化 重点函数0号
    student* pre = new student;//这才是正确的初始化 严老师你看清楚
    void clue_tree(student *p)
    {
    	if (p)
    	{
    		clue_tree(p->left);
    
    		if (p->left==NULL)//左孩子为空链接前驱
    		{
    			p->left = pre;
    			p->tagleft = 1;
    		}
    		
    		if (pre!=NULL&&pre->right==NULL)//pre右孩子为空链接后驱
    		{
    			pre->right = p;
    			pre->tagright = 1;
    		}
    	
    		pre = p;
    		if (p->tagright == 0 && p->right == NULL)
    		{
    			p->tagright = 1;
    		}//这段是我自己加的 用来保证最后一个元素的tagright为1  否则它会默认是0 不满足该题 要求 
    		//比如ABCD   A的tagleft=1 虽然左边没有元素 但是仍有线索 线索指向NULL
    		//同理 D后面虽然已经没有元素了 但仍有线索 线索指向NULL 如果没有这段代码 d的tagright默认=0;
    		clue_tree(p->right);
    	}
    
    
    }
    
    
    
    
    
    
    
    //重点函数1  找到后面一个应该输出元素 列如输出顺序是 ABCDEF 不管这个二叉树什么样子  B后面就是C  C后面就是D   
    student* find_next(student* & p)
    {
    	student* next=NULL;
    	student* q;
    	if (p->tagright == 1)
    	{
    		next = p->right;//直接利用我们的线索 因为tag=1的时候 right就直接链接我们的后驱
    	}
    	else if (p->tagright == 0)//没有线索
    	{
    		if (p->right == NULL)
    		{
    			next = NULL;
    		}
    	   else if (p->right != NULL)//
    		{
    
    			q = p->right;
    			while (q->tagleft == 0)
    			{
    				q = q->left;
    			}
    			next = q;
    		}
    		
    	}
    	return next;//如果这里的p指的是是C的话 这里返回的next 指的就是D
    }
    
    
    //重点函数2找到 中序遍历应该输出的头一个元素
    student* find_the_first_student(student *& root)
    {
    	student* q = root;
    	if (q)
    	{
    		while (q->left!=NULL)
    		{
    			q = q->left;
    		}
    	}
    	return q;
    	
    }
    
    
    //重点函数3    函数1 2仅在其中被利用
    void display_the_tree(student *&root)
    {
    	student* p;
    	p = find_the_first_student(root);
    	while (p != NULL)
    	{
    		//
    		if (m == 0)
    		{
    			cout << ",";
    		}
    		m = 0;
    		cout << p->data;
    		cout << "(";
    		cout << p->tagleft;
    		cout << ",";
    		cout << p->tagright;
    		cout << ")";
    		//上述代码用来输出 m用来控制逗号
    		
    		p = find_next(p);
    	}
    }
    
    int main()
    {
    
    	pre = NULL;//这tm才叫初始化 书上写些锤    子
    	student* root;
    	string kk;
    	cin >> kk;
    	creat(root, kk);//
    
    	//接下来是不带头节点的线索化
    	clue_tree(root);//正确
    	
    	//接下来两步骤是遍历同时输出
    	display_the_tree(root);
    
    
    	
    
    
    	return 0;
    }

    展开全文
  • 大家好呀!你们的大牛学长又回来了! 大牛学长真的是无处不在 ……线索二叉树是很多学弟学妹一直嚷嚷着学不懂的问题,但是它也不像“AOV”、“AOE”、“BMP”、...走起~01 前言线索二叉树是二叉树的个拓展结构...

    2a0413f27f0e097ecb679034e70c8fb5.png

    大家好呀!

    你们的大牛学长又回来了!

      大牛学长真的是无处不在 ……  

    线索二叉树是很多学弟学妹一直嚷嚷着学不懂的问题,但是它也不像“AOV”、“AOE”、“BMP”、“哲学家进餐”等知识点那样高冷得完全让人摸不着头脑!

    108c12a8dd958da501405706cc282a3e.gif

    线索二叉树这样的知识点就像个磨人的小妖精,既让人捉摸不定,又给人想要征服它的欲望哈哈哈……

    4b7ab16aaee2b507755e0bcde910b4f8.png

    今天学长就带大家一起搞定它!

    走起~

    01

      前言  

    线索二叉树是二叉树的一个拓展结构,是基于二叉树的遍历这一知识点上拓展出来的一种特殊二叉树形式,在保留原有二叉树用两个指针域指向左右孩子结点的结构的同时,使用空指针域对于遍历序列的直接前驱和直接后继进行存储,以此来简化二叉树的遍历过程,但是注意,虽然简化了遍历过程,在线索二叉树上进行遍历操作时间复杂度仍然是O(n),因为仍然是对n个结点进行访问。

    02

      先导知识  

    (敲黑板!咱们先来复习复习一般的二叉树!)

    • 二叉树的概念和数据结构

    二叉树的基本组成:根结点、左子树、右子树。若能依次遍历这三部分,就是遍历了二叉树。

    • 遍历二叉树 traversing binary tree:按某种路径访问且只访问一次结点

     根据这三部分遍历顺序的不同分类

     DLR——先(根)序遍历。

     LDR——中(根)序遍历。

     LRD——后(根)序遍历。

     按层次观察:

     层序遍历:是从根结点开始遍历,按层次次序, “自上而下,从左至右”访问树中的各结点。

    89ee53a8a68542d236502ef61e34cd2d.png

    图中二叉树对应的遍历序列:

    先序遍历:-+a*b-cd/ef

    中序遍历:a+b*c-d-e/f

    后序遍历:abcd-*+ef/-

    层序遍历:-+/a*efb-cd

    在掌握了二叉树的遍历的知识之后我们可以正式开始对于线索二叉树的学习。

    03

      知识背景  

    我们先考虑为什么要创造线索二叉树?

    如果同学们有很好的掌握二叉树的遍历这一部分的知识,我们可以知道对于层序遍历来说我们需要借助队列对二叉树进行非递归实现,而对于先序遍历、中序遍历、后序遍历来说,我们可以递归实现也可以借助栈来非递归实现。

    但是显然对于每一种经典遍历实现来说,对于任意一个结点p的直接前驱或是直接后继,我们都是要经过辅助数据结构比如队列或者栈的操作才能够得到的,并且如果我们要对一个二叉树进行多次遍历,每次单独的遍历过程都是相同的,也就是我们不能“记忆”动态遍历过程。这就像是我们第一次从家里出发上学,我们第一次可能进行了多次尝试才找到了一条路径,那么第二次上学的时候我们应该是根据上一次的记忆走上次的路径,而不是像第一次出发那样尝试所有的路。

    线索二叉树的产生就是为了帮助我们“记忆”遍历序列。

    线索二叉树是基于以下几个前提条件产生的:

    1.已知对于某个二叉树进行某种遍历得到的序列。

    2.以二叉链表作为存储结构的二叉树只能找到左右孩子信息,不能直接得到遍历序列中对应结点的前驱和后继。

    3.二叉链表有n+1个空结点。这是由于在有n个结点的二叉树当中一共存在2n个指针域,而n个结点对应的树度数之和为n-1,也就是非空指针域数量为n-1,由此空结点数量为n+1。

    因此我们考虑使用结点的空指针域来记录结点的前驱和后继

    而由于线索二叉树记录的是不同的遍历序列,线索二叉树按照遍历方式来分类可以分为:先序线索二叉树、中序线索二叉树、后序线索二叉树(层序线索二叉树一般不会提及)

    04

      基本概念  

    线索:指向前驱和后继的指针

    线索二叉树Threaded Binary Tree:加上线索的二叉树

    线索化:以某种次序遍历使二叉树变为线索二叉树的过程

    在线索树上遍历只需要(1)找到第一个结点(2)依次找结点直接后继直到其直接后继为空

    数据结构

    833375ed9967e452961c86663b59ba6b.png

    我们始终用结点p的左空结点指向p的直接前驱,用结点p的右空结点指向p的直接后继,用Tag来区分指向的是孩子还是线索。区分方法如下所示:

    08616d79a96cecce260a9251877abc5b.png

    这里给出了中序线索二叉树的示意图。当我们在画图的时候用虚线表示线索,用实线表示孩子

    b159efd91ecdd192de3f2cc28ed4cf98.png

    对应的中序遍历序列为:a+b*c-d-e/f

    线索化也就是构造过程是:

    • a是中序遍历的第一个结点,并且左孩子为空,使得左指针指向NULL表明是第一个结点。

    • +是中序遍历的第二个结点,是a的直接后继。a的右孩子为空,修改a的右指针为虚线,表明指向的+是a的直接后继;+的左孩子不为空因此不能进行修改。

    • b是中序遍历的第三个结点,是+的直接后继。+的右孩子不为空,不能进行修改;b的左孩子为空,修改b的左指针为虚线,表明指向的+是b的直接前驱。

    • 由此类推就能完成中序线索二叉树的构造过程。

    相对应的,在中序线索二叉树上进行遍历:

    • a的左指针指向NULL表明这是中序遍历的第一个结点

    • a的右指针为虚线,表明指向的是直接后继,表明+是a的直接后继是中序遍历的第二个结点

    • +的右指针为实线,表明指向的是孩子而不是直接后继,需要寻找直接后继,在中序遍历中根结点的直接后继为右子树的最左结点,因此对应的是b,b是中序遍历的第三个结点

    • 由此类推就能借助线索二叉树完成中序遍历过程。

    线索二叉树的两个重点:线索化遍历

    线索化就是构造线索二叉树的过程,遍历则是通过线索二叉树完成遍历的过程。我们这篇文章重点讨论线索化的过程。

    05

      线索化  

    线索化的过程就是遍历中修改空指针的过程

    ——鲁迅(并没有说过这句话)

    fd28fa479f8130fdfbd7425242688ff9.png

    设前驱结点为pre,初始化为NULL,找到从根结点出发的,对应遍历顺序的第一个结点p

    跟上来说就是遵循以下循环:

    1.若p不存在左孩子,则把p的LTag置为1,p的左孩子设为pre;pre若不为空,且pre不存在右孩子,则把pre的RTag置为1,pre的右孩子设为p。(在pre和p之间建立线索)

    2.pre设为p(表示下一个后继对应的前驱为当前的p)

    3.找到p的后继结点,把后继结点设为p

    因此线索化的过程和遍历过程十分相近,只要在掌握遍历算法的基础上,使用pre指针记录上一个被访问的结点,与当前访问的结点p互相建立线索就可以了。

    06

      算法与实现  

    • 首先我们要定义结点类型(是否为线索)

    0449e57916149fe5cef0f94e4b3820fe.png

    • 然后是中序遍历线索化函数

    37bdf86c3823ff34087a7924f52d7cea.png b159efd91ecdd192de3f2cc28ed4cf98.png

     中序线索二叉树

    • 对于先序遍历,先序遍历线索化函数这样写

    33005c667d6f965cd15906908f8b607c.png

    07

      考查形式  

    好了,讲了这么多终于开始讲考题类型了!线索二叉树很少考纯编程,大部分时候出现在选择题和考察逻辑让画图的大题当中。主要考点如下。

    1.要求可以画出线索树,根据遍历序列,在原有二叉树基础上,对于空指针增加虚线,使得第一个结点的左孩子指向NULL,最后一个结点的右孩子指向NULL就可以了(可以参考上文中的图)。

    2.不同线索树的一些特殊性质,例如:

    – 有n个结点的二叉树中有n+1个空指针,可以拥有n+1个线索

    – 掌握一些临界值,例如:

     中序线索树

      有右孩子时,后继结点是什么,是否可达?

      有左孩子时,前驱结点是什么,是否可达?

     先序线索树

      有右孩子时,后继结点是什么,是否可达?

      有左孩子时,前驱结点是什么,是否可达?

     例题:

     若X是二叉中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为(C)

     A. X的双亲  B. X的右子树的最左结点  C. X的左子树中最右结点  B. X的左子树中最右叶节点

     考察的是中序遍历的性质,LDR,对于根结点D来说,直接前驱是左子树L中的最右结点。

    好啦! 我已经把搞定线索二叉树的 种种技能教给大侠你了! 希望大侠好好利用! 一定要把能够抓住的分死死抓到手里哦!

    126d9404c378d645b0cecaaa41ae1a56.png

    ‍ ‍

    今天是2020年8月20日

    距离2021考研还有 120 天

    行动永远比无望的焦虑更有效!  

    大牛学长一直在~

    - END -

    e78ff3302a780632eb55a44ec49439fe.png

    展开全文
  • 线索二叉树应用实验 实验报告 实验目的 1掌握线索二叉树的有关知识 2掌握求解线索二叉树中结点前趋和后继的算法以及以相应次序遍历线索二叉树的算法 3掌握二叉树的线索化算法的设计 实验运行环境 Visual C++ 实验...
  • 前面我们学习树和二叉树的一些基本操作,今天我们学习个新的知识,学习一下线索二叉树线索二叉树是由二叉链存储结构变化而来的(我们先得有个二叉链树,再做处理),就是将原来的空域链改为莫种遍历次序下该结点...
  • C语言数据结构之线索二叉树及其遍历 遍历二叉树就是以一定的规则将二叉树中的节点排列成个线性序列,从而得到二叉树节点的各种遍历序列,其实质是:对个非线性的结构进行线性化。使得在这个访问序列中每个节点...
  • 线索二叉树、中序线索二叉树的创建和遍历

    千次阅读 多人点赞 2020-11-10 20:49:39
    线索二叉树 按照某种遍历次序对二叉树进行遍历,可以把二叉树中的所有结点排成个线性序列。在具体应用中,有时需要访问二叉树中的结点在某种遍历序列中的前驱和后继,此时,在存储结构中应保存结点在某种遍历序列...
  • 二叉树一、树的相关概念●树的定义(递归定义) 树是n(n≥0)个节点的有限集合T,当n=0(T为空)时称为空树;当n(n>0)是树为非空。非空树满足以下两个条件有且仅有一个称为根的节点其余的节点可以分为m(m≥0)个互不...
  • 详解线索二叉树

    2022-02-08 23:58:52
    1.了解线索二叉树之前要知道为什么需要线索二叉树 typedef struct BiTNode{ // Node structure ElemType data; // node data struct BiTNode *lchild; // left child struct BiTNode *rchild; // right child...
  • 1.先序线索二叉树找前驱节点困难,找后继节点简单 后序线索二叉树找后继节点困难,找前驱节点简单 中序线索二叉树找前驱节点,后继节点都很简单 2.遍历中序和先序线索二叉树,不需要栈,直接通过线索就可以实现...
  • 其实线索二叉树相当于把一棵二叉树变成个双向链表,这有利于方便插入删除结点和查找某个结点的操作。 线索化:对二叉树以某种次序遍历使其变为线索二叉树的过程。 线索二叉树的结点结构:lchild - ltag - data -...
  • 中序线索二叉树

    千次阅读 2021-08-01 23:45:38
    线索二叉树线索二叉树的基本概念中序线索二叉树的构造中序线索二叉树的遍历 线索二叉树的基本概念 中序线索二叉树的构造 中序线索二叉树的遍历
  • 图解线索二叉树

    万次阅读 多人点赞 2020-07-07 13:17:56
    今天我们来聊聊线索二叉树 线索二叉树的诞生背景 对于n个结点的二叉树,则在二叉链存储结构中就会有n+1个空链域 当我在查找某个结点的时候,想要知道这个节点的前驱结点或者后继结点,我该怎么做? 1.我是不是可以...
  • 二叉树与线索二叉树

    2020-08-19 19:00:05
    它是同一棵树中除本身外所有结点的祖先,没有父结点。按上图的树结构来看,根节点就是 1。 父结点 也叫双亲结点,个结点如果有上级,则称这个上级是它的父结点,如果没有上级,则该结点无父结点。按上图的...
  • 文章目录线索二叉树的结构及数据类型定义根据输入结点初始化二叉树中序遍历二叉树并线索化遍历中序线索二叉树项目完整代码运行实现截图 线索二叉树的结构及数据类型定义 //定义数据类型 typedef char ElemType; //...
  • 提示:文章写完后,目录...我已此为契机,了解一下查找二叉树、完全二叉树、线索二叉树、最优二叉树的一些相关定义(此题结尾会给出答案详解) 、查找二叉树(二叉排序树) 二叉排序树的定义: 1、若根结点的左子树.
  • 后序线索二叉树怎么画 线索二叉树基本操作详解发布时间:2017-05-23来源:服务器之家遍历二叉树是以一定规则将二叉树中结点排列成个线性序列,得到二叉树中结点的先序,中序或后序序列。这实际上是对个非线性...
  • 基于二叉链表的二叉树,实现了二叉树的多种操作:添加、删除、拷贝、清空、树深度计算、父节点...使用模板偏特化继承并实现了线索二叉树,实现了中序线索建立、遍历算法和迭代器。程序编码风格良好,关键算法注释详细。
  • NULL 博文链接:https://128kj.iteye.com/blog/1634367
  • 文章目录线索二叉树的概念线索二叉树的结构二叉树的线索化使用线索二叉树进行遍历双向线索二叉树的概念双向线索二叉树的实现过程双向线索二叉树的遍历 线索二叉树的概念 当我们对普通的二叉树进行遍历时需要使用栈...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,529
精华内容 5,811
关键字:

一棵线索二叉树