先序遍历算法 ●若二叉树为空树,则空操作;否则, ●(1)访问根结点; (2)先序遍历左子树; ●(3)先序遍历右子树。 ● void preorder( BiTree bt){先序遍历二叉树bt ●fif(bt==NUL) return;/递归调用的结束条件 ● Visite(bt>data);/访问结点的数据域 ● PreOrder(bt-> child);/先序递归遍历b的左子树 ● PreOrder(bt→ orchid);/先序递归遍历bt的右子树 北京邮电大学自动化学院
北京邮电大学自动化学院 26 先序遍历算法 ⚫ 若二叉树为空树，则空操作；否则， ⚫ （1）访问根结点； ⚫ （2）先序遍历左子树； ⚫ （3）先序遍历右子树。 ⚫ void PreOrder（BiTree bt）{/*先序遍历二叉树bt*/ ⚫ if (bt==NULL) return; /*递归调用的结束条件*/ ⚫ Visite（bt->data）; /*访问结点的数据域*/ ⚫ PreOrder（bt->lchild）; /*先序递归遍历bt的左子树*/ ⚫ PreOrder（bt->rchild）;/*先序递归遍历bt的右子树*/}
先序遍历 先序遍历 D R A D R DL R B D B)A DL R 先序遍历序列:ABDC①AA 北京邮电大学自动化学院 27
北京邮电大学自动化学院 27 A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 先序遍历: 先序遍历
void preorder(JD *bt ot) A if(btI=NULL) printf(" dt",bt->data);左是空返回(B preorder(bt->lchild); 左是空返回 preorder(bt->rchild); 是空返回 ∧ 返回 左是空返回 T→右是空返回 printf(B) 主程序 T→∧ pre(T→ printf); printf(a); pre(t- 返回 pre(T→ pre(T→ Pre(t R); L); T一∧ pre R); R); C 返回 T→→∧ printf(C); 返回 先序序列:ABDC pre(T→ T→∧ R) 返回 北京邮电大学自动化学院
北京邮电大学自动化学院 28 void preorder(JD *bt) { if(bt!=NULL) { printf("%d\t",bt->data); preorder(bt->lchild); preorder(bt->rchild); } } 主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A B C D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C
中序遍历算法 若二叉树为空树,则空操作;否则, ●(1)中序遍历左子树; ●(2)访问根结点; ●(3)中序遍历右子树。 ● void Inorder( BiTree bt){中序遍历二叉树bt* ●if(bt=NULL) return;鬥递归调用的结束条件 ● InOrder(bt-> Child);/中序递归遍历b的左子* ● /isite(bt>data);/访问结点的数据域 ● norder(bt> rchild);/中序递归遍历bt的右子树 北京邮电大学自动化学院
北京邮电大学自动化学院 29 ⚫ 若二叉树为空树，则空操作；否则， 中序遍历算法 ⚫ （1）中序遍历左子树； ⚫ （2）访问根结点； ⚫ （3）中序遍历右子树。 ⚫ void InOrder（BiTree bt）{/*中序遍历二叉树bt*/ ⚫ if (bt==NULL) return; /*递归调用的结束条件*/ ⚫ InOrder（bt->lchild）; /*中序递归遍历bt的左子*/ ⚫ Visite（bt->data）; /*访问结点的数据域*/ ⚫ InOrder（bt->rchild）; /*中序递归遍历bt的右子树*/}
中序遍历算法 中序遍历 D R ④ L D R B C D R B A(C∧ D R ∧ ∧ 中序遍历序列:BDAc 北京邮电大学自动化学院
北京邮电大学自动化学院 30 A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历 中序遍历算法