wcy-dt/seu-cybersecurity-courses

东南大学网络空间安全学院学习资料整理。包含课件、笔记、试卷、作业等。

👋Hi there! I'm Ch3nyang, hailing from Southeast University, China, currently pursuing a Master's degree in Cybersecurity.

🌐Socials

💻Tech Stack

🏆GitHub Stats

✒️Recent Blogs

2024 - Jul - 内核，启动！

2024 - Jul - 旅程刚刚开始

2024 - Jul - 32位的世界

2024 - Jul - 系统，启动！

2024 - Jun - 再谈git

---

seu-cybersecurity-courses's Issues

/

数据结构线索化二叉树这里的图片显示失败了

线索化二叉树

​ 线索二叉树（Threaded Binary Tree）定义为：一个二叉树通过如下的方法“穿起来”：所有应该为空的右孩子指针指向该结点在中序序列中的后继，所有应该为空的左孩子指针指向该结点的中序序列的前驱。那么在有 $N$ 个结点的二叉树**有 $N+1$ 个空指针，这些空指针就叫做“线索”。（提示：在一个有 $N $个结点的二叉树中，每个结点有 $2 $个指针，所以一共有 $2N $个指针，将这 $N$ 个结点连接起来需要 $N-1$ 条线，即使用了 $N-1$ 个指针。所以剩下 $2N-(N-1)=N+1$ 个空指针。）那线索二叉树有何用处呢？由于巧妙地利用了空指针，所以它可以快速地查找到二叉树中某结点的前驱和后继。接下来具体介绍这个数据结构。

　　二叉树虽然是非线性结构，但二叉树的遍历却为二又树的结点集导出了一个线性序列。希望很快找到某一结点的前驱或后继，但不希望每次都要对二叉树遍历一遍，这就需要把每个结点的前驱和后继信息记录下来。为了做到这一点，可在原来的二叉链表中增加一个前驱指针域pre和一个后继指针域suc，分别指向该结点在某种次序下的前驱结点和后继结点。以中序遍历为例：

　　有许多指针是空指针又没有利用。为了不浪费存储空间，利用空的lchild域存放结点的前驱结点指针，利用空的rchild域存放结点的后继结点指针。为了区别线索和子女指针，在每个结点中设置两个标志ltag和rtag。以中序线索二叉树为例，如果ltag==0，标明lchild域中存放的是指向左子女结点的指针，否则lchild域中是指向该结点中序下的前驱的线索；如果rtag==0，标明rchild域中存放的是指向右子女结点的指针，否则rchild域中是指向该结点中序下的后继的线索。由于它们只需占用一个二进位，每个结点所需存储空间节省得多。