if(T->Rchild) newrptr= Copy Tree((I> Rchild);∥复制(历右子树 else newrptr= NULL newnode:= GetTreeNodel(I->daa, newlptr, newrptr);∥生成根结点 return newnode; 5复 a,aua void locate( BiTree T, ElemType x, BiTree& p) :// Eo ]- T OD'aeouoi x lai-HAOEOf-oo HA sOul NULL pO.loA%￡→iO0pμAO士涯p if T) iif if(T->data==x)p=Tf iii: locate (T-lchild, x, P); iiiilocate(T->rchild, x, P); 中序遍历(非递归) · Initstack(S) Push(S,D);∥根入栈 while(StackEmpty(s) while(get Top(s, p)&& p) Push(S,p-> lchild);/向左到尽头 Pop(S, p) ∥空指针出栈 if(Stack Empty(S)/问,向右 Pop(S, P) if( visit(p->data))return ERROR Push(S, p->rchild); return OK: 表达式的二叉树 二叉树的线索链表 °将在二叉树中每个结点(除第一个和最后一个外)的直接前驱和直接后继保存起来。这种信息 是在历的动态过程中产生的,如果将这些信息在第一次遍历时就保存起来,则在以后再次需 要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。 定义指针想,以tm表步分m typedef struct BiThrNodet ElemType data; struct BiThrNode *Lchild, Rchild;∥右指针 PointerType LTag,RIag;∥左右指针类型标志 )*BiThrTree 在线索链表中添加了一个”头结点”,头结点的左指针指向二叉树的根结点,其右线索指向中 序序列中的最后一个结点if (T->Rchild) newrptr = CopyTree(T->Rchild); // 复制(遍历)右子树 else newrptr = NULL; newnode = GetTreeNode(T->data, newlptr, newrptr); // 生成根结点 return newnode; } 6-4-5 后序遍历复制.swf ÔÚ¶þ²æÊ÷Éϲéѯij¸ö½áµã •void locate(BiTree T,ElemType x,BiTree& p) { ¡¡// Èô¶þ²æÊ÷ T ÖдæÔÚºÍ x ÏàͬµÄÔªËØ£¬Ôò p Ö¸Ïò¸Ã½áµã£¬·ñÔò p µÄÖµ²»±ä£¬p µÄ³õֵΪ NULL ¡¡if (T) ¡¡{ if (T->data==x) p=T; ¡¡¡¡locate(T->lchild, x, p); ¡¡¡¡locate(T->rchild, x, p); ¡¡} } 中序遍历（非递归） •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(!Visit(p->data))return ERROR; Push(S,p->rchild); } } return OK; 表达式的二叉树 二叉树的线索链表 •将在二叉树中每个结点（除第一个和最后一个外）的直接前驱和直接后继保存起来。这种信息 是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需 要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。 •typedef enum PointerType{ Link=0, Thread=1 }; // 定义指针类型，以 Link 表示指针，Thread 表示线索 typedef struct BiThrNode{ ElemType data; struct BiThrNode *Lchild, *Rchild; //左右指针 PointerType LTag, RTag; // 左右指针类型标志 } *BiThrTree; •在线索链表中添加了一个"头结点"，头结点的左指针指向二叉树的根结点，其右线索指向中 序序列中的最后一个结点