首页 > 其他分享 > 王道-考研-数据结构-线索二叉树

王道-考研-数据结构-线索二叉树

时间:2022-09-22 21:22:44浏览次数:64  
标签:pre 结点 NULL ThreadNode 二叉树 数据结构 线索 考研

线索二叉树的构造

常用的是中序线索二叉树

寻找前驱结点:

  • 若左指针为线索,则其指向结点为前驱结点。
  • 若左指针为左孩子,则其左子树的最右侧结点为前驱结点。

寻找后继结点:

  • 若右指针为线索,则其指向结点为后继结点。
  • 若右指针为右孩子,则其右子树的最左侧结点为后继结点。

中序线索二叉树线索化

// p 为线索二叉树的根结点
// pre 为对应结点的前驱结点
void InThread(ThreadTree &p, ThreadTree &pre)
{
if (p != NULL)
{
InThread(p->lchild, pre);
if (p->lchild == NULL)
{
p->lchild = pre;
p->ltag = 1;
}
if (pre != NULL && pre->lchild == NULL)
{
p->rchild = p;
p->rtag = 1;
}
InThread(p->rchild, pre);
}
}
void CreateInThread(ThreadTree T)
{
ThreadTree pre = NULL;
if (T != NULL)
{
InThread(T, pre);
pre->rchild = NULL;
pre->rtag = 1;
}
}

image

image

// p 为线索二叉树的根结点
ThreadNode *FirstNode(ThreadNode *p)
{
while (p->ltag == 0)
{
p = p->lchild;
}
return p;
}
// p 为结点
ThreadNode *NextNode(ThreadNode *p)
{
if (p->rtag == 0)
{
return FirstNode(p.rchild); // 如果有孩子结点,则后继结点就是右子树最左侧的结点
}
else
{
return p.rchild;
}
}
// 遍历
void InOrder(ThreadNode *T)
{
for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p))
{
visit(p);
}
}

标签:pre,结点,NULL,ThreadNode,二叉树,数据结构,线索,考研
From: https://www.cnblogs.com/bi-hu/p/16720896.html

相关文章

  • 数据结构:线性表
    线性表线性表(List):零个或多个数据元素的有限序列。首先它是一个序列。也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都......
  • BM31对称二叉树(判断二叉树是否symmetric?)(递归)
    描述给定一棵二叉树,判断其是否是自身的镜像(即:是否对称)例如:                 下面这棵二叉树是对称的下面这棵二叉树不对称。数据范围......
  • leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 从前序与
    一、题目大意给定两个整数数组preorder和inorder,其中preorder是二叉树的先序遍历,inorder是同一棵树的中序遍历,请构造二叉树并返回其根节点。示例1:输入:pre......
  • 算法 玩转数据结构 2-2 二次封装属于我们自己的数组
    1重点关注1.1索引使用数组最大的优点:快速查询。scores[2]·数组最好应用于“索引有语意”的情况。·但并非所有有语意的索引都适用于数组(例如,以身份......
  • 算法 玩转数据结构 2-1 使用java中的数组
    1重点关注1.1idea新建Java项目newproject--》java--》选择jdk--》next--》createprojectfromtemplate--》Commandlineapp--》next--》输入工程名......
  • 对称二叉树
    对称二叉树一、题目描述给一个二叉树的根节点root,检查它是否为轴对称。实例输入:root=[1,2,2,3,4,4,3]输出:true输入:root=[1,2,2,null,3,null,3]输出:false二......
  • 考研?不如摆烂!
    自我介绍唐翔,ComeformWenzhouZhejiang,现居株洲,皮革厂继承人。带专拿了两奖学金然并卵。致力于畅享摆烂人生。一个非常ordinary的人。爱做大梦,摆烂人生。以至于在毕......
  • 认识Java的整形数据结构
    摘要:java中一切都是对象,为什么int不用创建对象实例化,而可以直接使用?本文分享自华为云社区《【Java】对基本类型-整型数据结构的认识》,作者:huahua.Dr。整型数据类型有两......
  • 【数据结构】跳表
    一、基本概念1.1定义跳表(SkipList):增加了向前指针的链表叫做指针。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质是一种可以进行二分查找的有序链表。......
  • 数据结构算法(一)之二分查找
    internalclassProgram{staticvoidMain(string[]args){varn=50;varrandom=newRandom();while......