中序遍历和线索化二叉树

null6.3遍历二叉树和线索二叉树6.3遍历二叉树和线索二叉树6.3.1遍历二叉树 如果按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。先序遍历二叉树的操作定义为：先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 A B C D F E G先序遍历二叉树的递归算法先序遍历二叉树的递归算法Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (Visit(T->data)) if (PreOrderTraverse(T->lchild,Visit)) if (PreOrderTraverse(T->rchild,Visit)) return OK; return ERROR; }else return OK; }//PreOrderTraverse中序遍历二叉树的操作定义为：中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 C B D F A G E中序遍历二叉树示例中序遍历二叉树示例中序遍历二叉树得: a+b*(c-d)-e/f中序遍历二叉树的递归算法中序遍历二叉树的递归算法Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (InOrderTraverse(T->lchild,Visit)) if (Visit(T->data)) if (InOrderTraverse(T->rchild,Visit)) return OK; return ERROR; }else return OK; }//InOrderTraverse后序遍历二叉树的操作定义为：后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 C F D B G E A后序遍历二叉树的递归算法后序遍历二叉树的递归算法Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e)){ if (T){ if (PostOrderTraverse(T->lchild,Visit)) if (PostOrderTraverse(T->rchild,Visit)) if (Visit(T->data)) return OK; return ERROR; }else return OK; }//PostOrderTraverse中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法Status InOrderTraverse(BiTree T, Status(* Visit) (TElemType e)){ InitStack(S); Push(S,T); while(!StackEmpty(S)){ while(GetTop(S,p) && p)Push(S,p->lchild); Pop(S, p); if (!StackEmpty(S)){ Pop(S,p); if (!Visite(p->data)) return ERROR; Push(S,p->rchild); } } return OK; }//InOrderTraverse中序遍历二叉树的非递归算法 示意图中序遍历二叉树的非递归算法 示意图C B D F A G E例： 已知结点的先序序列和中序序列，求整棵二叉树。例： 已知结点的先序序列和中序序列，求整棵二叉树。先序序列：A B C D E F G 中序序列：C B E D A F G构造二叉链表表示的二叉树 的递归算法构造二叉链表表示的二叉树 的递归算法Status CreateBiTree(BiTree &T) { scanf(“%c”,&ch); if (ch==‘#’) T=NULL; else { if (!(T=(BiTNode *) malloc(sizeof (BiTNode)))) exit(OVERFLOW); T->data = ch ; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; }//CreateBiTree构造二叉链表构造二叉链表按下列次序输入字符: ABCDEGF (其中表示空格字符) 可建立如右图的二叉链表.6.3.2 线索二叉树6.3.2 线索二叉树遍历是非线性结构的线性化操作 保留遍历过程的顺序信息 ----- 线索二叉树的表示: 若结点有左子树，则其LCHILD域指示其左孩子，否则令LCHILD域指示其前驱； 若结点有右子树，则其RCHILD域指示其右孩子，否则令RCHILD域指示其后继。线索二叉树结点的结构:线索二叉树结点的结构: 0 lchild域指示其左孩子 ltag ={ 1 lchild域指示其前驱 0 rchild域指示其右孩子 rtag ={ 1 rchild域指示其后继 线索二叉树 线索化 线索链表 线索中序线索二叉树中序线索二叉树NILNIL中序线索二叉树中 查找结点的后继和前驱:中序线索二叉树中 查找结点的后继和前驱:如何在中序线索二叉树中找结点的后继： rtag = 1时，rchild所指的结点即为后继； rtag = 0时，其后继为遍历其右子树时的第一个结点（最左下结点）。 如结点 “*”的后继是“c” 。 如何在中序线索二叉树中找结点的前驱： ltag = 1时，lchild所指的结点即为前驱； ltag = 0时，其前驱为遍历其左子树时的最后一个结点（最右下结点）。 如根结点 “-”的前驱是“d” 。 中序线索二叉树中序线索二叉树// 二叉树的二叉线索存储表示 typedef enum {Link,Thread} PointerTag; //Link==0:指针,Thread==1:线索 typedef struct BiThrNode { TElemType data; struct BiThrNode *lchild,*rchild; //左右孩子指针 PointerTag LTag,RTag; //左右标志 }BiThrNode, *BiThrTree; 中序遍历二叉树T，并将其中序线索化: (为了记下遍历过程中访问结点的先后次序，附设一个全程指针pre)中序遍历二叉树T，并将其中序线索化: (为了记下遍历过程中访问结点的先后次序，附设一个全程指针pre)Status InOrderThreading(BiThrTree &Thrt, BiThrTree 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; InThreading(T); //中序遍历进行中序线索化 pre->rchild=Thrt; pre->RTag=Thread; //最后一个结点线索化 Thrt->rchild=pre; } return OK; }//InOrderThreading中序遍历进行中序线索化中序遍历进行中序线索化void InThreading(BiThrTree p){ // 一个全程指针pre if (p){ InThreading(p->lchild); //左子树线索化 if (!p->lchild){ p->LTag=Thread;p->lchild=pre;} //前驱线索 if (!pre->rchild){ pre->RTag=Thread; pre->rchild=p;} //后继线索 pre=p; //保持pre指向p的前驱 InThreading(p->rchild); //右子树线索化 } }//InThreading 例如: 将下列二叉链表改为中序线索链表例如: 将下列二叉链表改为中序线索链表1 2 3 4 5 6 7 8 9 10 11 12 13 14上例树的形态 上例树的形态 1 2 3 4 5 6 7 8 9 10 11 12 13 14中序遍历二叉线索树T的非递归算法:中序遍历二叉线索树T的非递归算法:Status InOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e)){ // T指向头结点，头结点的左链lchild 指向根结点， //可参见线索化算法。中序遍历二叉线索树T的非递归算法， // 对每个数据元素调用函数Visit. p=T->lchild; //p指向根结点 while(p!=T){ //空树或遍历结束时，p==T while(p->LTag==Link)p=p->lchild;//p寻找最左下结点 if (!Visit(p->data)) return ERROR; //访问其左子树为空的结点 while(p->RTag==Thread&&p->rchild!=T){ p=p->rchild; Visit(p->data); //访问后继结点 } p=p->rchild; } return OK; }//InOrderTraverse_Thr实验与习题实验与习题理论习题 6.12-6.16,6.23 实验算法题: 6.37