原理
浪费资源
- 对于一个有n个结点的二叉链表，每个结点有指向左右孩子的指针域
- 所以一共是2n个指针域
- 而n个结点的二叉树一共n-1条分支，也就是说，其实存在
2n-(n-1) = n+1个空指针域
结点信息知而不全
- 我们无法得知某个结点的前驱或后继，要想知道，就必须先遍历一遍
办法
- 利用那些空的地址，存放指向结点在某种遍历次序下的前驱与后继结点的地址
线索二叉树
- 把这种指向前驱或后继的指针称为线索
- 加上线索的二叉链表称为线索链表
- 相应的二叉树就称为线索二叉树
- 对二叉树以某种次序遍历使其变为线索二叉树的过程称作线索化
实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//结构 typedef enum { Link,//Link == 0表示指向左右孩子指针 Thread//Thread == 0表示指向前驱后继的线索 }PointerTag; typedef struct BiThrNode { ElemType data; struct BiThrNode * lchild,*rchild; PointerTag LTag; PointerTag RTag; }BiThrNode,*BiThrTree; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
BiThrTree pre;//始终指向刚刚访问过的结点 //中序遍历中序线索化 void InThreading(BiThrTree p) { if(p) { InThreading(p->lchild); if(!p->lchild)//没有左孩子 { p->LTag = Thread;//前驱线索 p->lchild = pre;//左孩子指向前驱 } if(!pre->rchild)//没有右孩子 { pre->LTag = Thread;//后继线索 pre-rchild = p;//前驱右孩子指针指向后继 } pre = p; InThreading(p->rchild); } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
//中序遍历二叉线索链表表示二叉树T int InOderTraverse_Thr(BiThrTree * T) { BiThrTree p; p = T->lchild; while(p != T) { while(p->LTag == Link) p = p->lchild; printf("%c",p->data); while(p->RTag == Thread && p->rchild != T) { p = p->rchild; printf("%c",p->data); } p = p->rchild; } return 1; } |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 大话数据结构_栈_应用11/01
- ♥ 大话数据结构_二叉树11/03
- ♥ 红黑树05/01
- ♥ 大话数据结构_算法相关&&AVL&&B树相关02/20
- ♥ 大话数据结构_栈11/01
- ♥ 大话数据结构_树11/02
热评文章
- 大话数据结构_二叉树_结构&&遍历&&推导 0
- 大话数据结构_图 0
- 大话数据结构_二叉树 0
- 大话数据结构_图表示 0
- 大话数据结构_树 0
- 大话数据结构_图遍历 0