【数据结构与算法】树2

1、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 (PreOrderTrave

2、rse(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-lchil

3、d,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 (PostOrderTrave

4、rse(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) /InOrderTraverse,中序遍历二叉树

5、的非递归算法示意图,C B D F A G E,例： 已知结点的先序序列和中序序列，求整棵二叉树。,先序序列：A B C D E F G 中序序列：C B E D A F G,构造二叉链表表示的二叉树的递归算法,Status CreateBiTree(BiTree /CreateBiTree,构造二叉链表,按下列次序输入字符: ABCDEGF (其中表示空格字符) 可建立如右图的二叉链表.,6.3.2 线索二叉树,遍历是非线性结构的线性化操作保留遍历过程的顺序信息 - 线索二叉树的表示: 若结点有左子树，则其LCHILD域指示其左孩子，否则令LCHILD域指示其前驱； 若结点有右子树，则其RC

6、HILD域指示其右孩子，否则令RCHILD域指示其后继。,线索二叉树结点的结构:,0 lchild域指示其左孩子 ltag = 1 lchild域指示其前驱 0 rchild域指示其右孩子 rtag = 1 rchild域指示其后继 线索二叉树 线索化 线索链表 线索,中序线索二叉树,NIL,NIL,中序线索二叉树中查找结点的后继和前驱:,如何在中序线索二叉树中找结点的后继： rtag = 1时，rchild所指的结点即为后继； rtag = 0时，其后继为遍历其右子树时的第一个结点（最左下结点）。 如结点 “*”的后继是“c” 。 如何在中序线索二叉树中找结点的前驱： ltag = 1时，l

7、child所指的结点即为前驱； 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，并将其

8、中序线索化:(为了记下遍历过程中访问结点的先后次序，附设一个全程指针pre),Status InOrderThreading(BiThrTree /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指

9、向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的非递归算法:,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