2021 |
您所在的位置：网站首页 › 严蔚敏数据结构代码实现 › 2021 |
|
线索二叉树
若结点有左子树，则其 lchild 域指示其左孩子，否则令其 lchild 域指示其前驱； 若结点有右子树，则其 rchild 域指示其右r孩子，否则令其 rchild 域指示其后继； 为了避免混淆，尚需改变结点的结构，增加两个标志域： lchildLTagdataRTagrchildLTag: 0 lchild 域指示结点的左孩子1 lchild 域指示结点的前驱RTag: 0 rchild 域指示结点的右孩子1 rchild 域指示结点的后继以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树称之为线索二叉树，对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。 #include using namespace std; #define TElemType char #define Status int typedef enum PointerTag { Link, Thread }; //-------------二叉树的二叉线索类型存储表示--------------------- typedef struct BiThrNode { TElemType data; // 结点数据域 struct BiThrNode *lchild, *rchild; // 左右孩子指针 int LTag, RTag; }BiThrNode, *BiThrTree; //---------------全局变量pre---------------------------------- BiThrNode *pre = new BiThrNode; //---------------建立二叉链表--------------------------------- Status CreateBiTree(BiThrTree &T){ TElemType ch; scanf("%c", &ch); if (ch == ' ') T = NULL; else { T = (BiThrTree)malloc(sizeof(BiThrNode)); if (!T) exit(_OVERFLOW); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return 1; } //--------------------算法6.5------------------------------------ Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(TElemType e)) { //中序遍历二叉线索树T的非递归算法，对每个数据元素直接输出 BiThrTree p; p = T->lchild; // p指向根结点 while (p != T) // 空树或遍历结束时，p==T { while (p->LTag == Link) // 沿左孩子向下 p = p->lchild; // 访问其左子树为空的结点 if(!Visit(p->data)) return 0; while (p->RTag == Thread && p->rchild != T) { p = p->rchild; // 沿右线索访问后继结点 Visit(p->data); } p = p->rchild; } return 1; } //---------------------算法6.6------------------------------------- // 带头结点的中序线索化 Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { //中序遍历二叉树T，并将其中序线索化，Thrt指向头结点 if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))// 建头结点 exit(_OVERFLOW); Thrt->LTag = Link; // 头结点有左孩子，若树非空，则其左孩子为树根 Thrt->RTag = Thread; // 头结点的右孩子指针为右线索 Thrt->rchild = Thrt; // 初始化时右指针指向自己 if (!T) Thrt->lchild = Thrt; // 若树为空，则左指针也指向自己 else { Thrt->lchild = T; pre = Thrt; // 头结点的左孩子指向根，pre初值指向头结点 InThreading(T); // 对以T为根的二叉树进行中序线索化 pre->rchild = Thrt; // pre为最右结点，pre的右线索指向头结点 pre->RTag = Thread; Thrt->rchild = pre; // 头结点的右线索指向pre } return 1; } //---------------------算法6.7------------------------------------- // 以结点P为根的子树中序线索化 void InThreading(BiThrTree p) { // pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索 if (p) { InThreading(p->lchild); // 左子树递归线索化 if (!p->lchild) { // p的左孩子为空 p->LTag = Thread; // 给p加上左线索 p->lchild = pre; // p的左孩子指针指向pre（前驱） } else p->LTag = Link; if (!pre->rchild) { // pre的右孩子为空 pre->RTag = Thread; // 给pre加上右线索 pre->rchild = p; // pre的右孩子指针指向p（后继） } else pre->RTag = Link; pre = p; // 保持pre指向p的前驱 InThreading(p->rchild); // 右子树递归线索化 } } Status visit(TElemType e){ cout rchild = NULL; BiThrTree tree, Thrt; cout |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |