25线索二叉树的存储结构
2023-09-27 14:22:14 时间
1、线索二叉树:传统链式存储仅能体现一种父子关系,不能直接得到结点在遍历中的前驱或后继。二叉链表中存在大量的空指针,利用这些空链域存放指向其直接前驱或后继的指针,则可更方便地运用某些二叉树操作算法。引入线索二叉树是为了加快查找前驱和后继的速度。
2、在N个结点的二叉树中,有N+1个空指针
3、在二叉树线索化时,通常规定:若无左子树,令lchild指向其前驱结点;若无右子树,令rchild指向其后继结点。还需要增加两个标志域表明当前指针域所指对象是左(右)孩子还是直接前驱(后继)
其中标志域含义如下:
线索二叉树存储结构的描述代码:
Typedef struct ThreadNode{
ElemType data; //数据元素
Struct ThreadNode *lchild,*rchild;//左右孩子指针
Int ltag,rtag; //左右线索标志
}ThreadNode,*ThreadTree;
相关文章
- 【算法】【二叉树模块】二叉树的序列化和反序列化方法
- 层序创建二叉树
- 【Python 八股文】- 二叉树相关算法
- 数据结构 | 线索二叉树的原理及创建
- PTA - 6-1 输出二叉树的所有叶子 (15 分)
- 88、【树与二叉树】leetcode ——226. 翻转二叉树:先中后序的递归与DFS非递归遍历+BFS层次遍历(C++版本)
- 【剑指offer】38二叉树的深度
- 【剑指offer】24二叉树中和为某一值的路径
- 由中序和后序重建二叉树
- 【Leetcode】105: 从前序与中序遍历序列构造二叉树
- [LeetCode] 662. Maximum Width of Binary Tree 二叉树的最大宽度
- LeetCode合并二叉树
- 二叉树遍历算法的非递归实现