贵州民族学院数据结构课件 第九章.ppt

第九章 二叉树周游算法 第九章 二叉树周游算法 周游是二叉树各种运算的基础，可以在周游过程中进行各种操作。如，可以在周游过程中生成结点，从而建立一棵二叉树 9.1 使用栈的周游算法 9.2 逆转链的周游算法 9.3 二叉树的其他运算例 9.1 使用栈的周游算法 以中序周游为例 9.1 使用栈的周游算法 设有BiTree T，使用Stack s, BiTree p 算法S[使用栈的中序周游二叉树T] S1[树空？] 若T=nil，则算法结束，否则p←T，push(p,s); S2[周游完成？]当s不空反复执行下列步骤 S2.1[找左链尾] 当p≠nil反复做： push(s,p), p←p→lchild S2.2[空指针出栈] pop(s); S2.3[访问结点*p,并向右一步] 若栈不空，则 top(s,p), pop(s), 访问*p，p←p→rchild，push(s,p) S3[算法结束] 递归的周游算法 算法P[前序周游二叉树T的递归算法] P1[T空？]若T=nil，则算法结点 P2[访问根结点]访问结点*T P3[访问左子树] 调用算法P，前序访问T的左子树 P4[访问右子树] 调用算法P，前序访问T的右子树 P5[结束] void PreTraverse( BiTree T) { if(T){ visit(T-data) ; PreTraverse (T-lchild); PreTraverse (T-rchild); } } //PreTraverse 10.2 逆转链的周游算法 在二叉链表中增加一个字段tag，作为标志： tag=0，当访问本结点和其右子树时 Tag=1, 当访问本结点的左子树时 typedef struct node { datatype data; int tag; struct node *lchild, *rchild; } BTNode, *BTree; 在算法中使用三个指针p,r,q,分别指向： p—当前访问结点 r—*p的父结点 q—下一个要访问的结点 算法PV[逆转链法对二叉树T进行前序周游] PV1[T空？] 若T=nil,则算法结束；否则 p←T, r ←nil; PV2[进入二叉树p的子树] 当左或右子树不空时，反复执行下列步骤： PV2.1[访问结点] 访问结点*p PV2.2[进入左子树或右子树]若p→lchild≠nil， 则 p→tag←1， q←p→lchild，p→lchild← r， r←p， p←q，执行PV2.1 若 p→rchild≠nil，则 q←p→rchild， p→rchild← r， r←p， p←q， 执行PV2.1 PV2.3[回到上一层] 当下列条件之一成立时，反复执行 若r≠nil且r→tag=0， 则q←r→rchild， r→rchild←p，p←r，r←q 若 r≠nil且r→tag=1 且r→rchild=nil ，则r→tag←0，q←r→lchild， r→lchild←p，p←r，r←q PV2.4[从左子树回，准备进入右子树] 若r=nil ，则算法结束； 否则r→tag←0，q←r→rchild， r→rchild←r→lchild ，r→lchild ← p, p ←q 先序输入二叉树中元素值，构造二叉链表 void CreateBTree(BTree T){ //先序输入二叉树中元素值，构造二叉链表，用T指向 char ch; ch=getchar( ); if(ch== ) T=NULL; else{ T=(BTree )malloc(sizeof(BTNode)); T-data=ch; //生成根结点 CreateBiTree(T-lchild); //构造左子树 CreateBiTree(T-rchild); //构造右子树 } } //CreateBiTree 统计二叉树T的叶结点数，结果存于*c中 void countleaf(BiTree T, int *c) { //统计二叉树T的叶结点数，结果存于*c中 if(T){ if((!T-lchild)(!T-rchild)) { (*c)++; // 若T所指结点无左、右子结点则计数 return; } countleaf(T-lchild,c);