第2讲 树型结构及二叉树.ppt

二、二叉树遍历的递归实现  由于二叉树的遍历是递归定义的，因此采用递归方式实现二叉树遍历的算法十分方便，只要按照各种遍历规定的次序，访问根结点时就输出根结点的值，访问左子树和右子树时进行递归调用即可。 结点的类型定义： typedef char datatype; typedef struct node{ datatype data; struct node *lchild, *rchild; } BiTNode,*BiTree; 前序遍历 void PreOrder (BiTree T) { if (T==NULL) return; /*递归调用结束*/ visit(T); /*visit()函数表示访问当前根结点*/ PreOrder(T-lchild); /*递归前序遍历T的左子树*/ PreOrder(T-rchild); /*递归前序遍历T的右子树*/ } void PreOrder(BiTree T) { if (T) { visit(T); PreOrder(T-lchild); PreOrder(T-rchild); } } 访问结点函数(输出值)： void visit (BiTree T) { printf(\nvalue=%c, T-data); 中序遍历 void InOrder (BiTree T) { if (T==NULL) return; /*递归调用结束*/ InOrder(T-lchild); /*递归中序遍历T的左子树*/ visit(T); /*visit()函数表示访问当前根结点*/ InOrder(T-rchild); /*递归中序遍历T的右子树*/ } void InOrder(BiTree T) { if (T) { InOrder(T-lchild); visit(T); InOrder(T-rchild); } } 后序遍历 void PostOrder (BiTree T) { if (T==NULL) return; /*递归调用结束*/ PostOrder(T-lchild); /*递归后序遍历T的左子树*/ PostOrder(T-rchild); /*递归后序遍历T的右子树*/ visit(T); /*visit()函数表示访问当前根结点*/ } void PostOrder(BiTree T) { if (T) { PostOrder(T-lchild); PostOrder(T-rchild); visit(T); } } 二叉树的创建递归算法  利用二叉树前序遍历的结果生成给定的二叉树：(1)将第一个输入的结点作为二叉树的根结点(2)由递归方式实现  后继输入的结点序列是二叉树左子树前序遍历的结果，由它们生成二叉树的左子树； 再接下来输入的结点序列为二叉树右子树前序遍历的结果，由它们生成二叉树的右子树；  BiTree CreateTree( ) { char ch; BiTree T; if ( (ch=getchar()) == ) return NULL; else { T=(BiTree)malloc(sizeof(BiTNode));  /*生成二叉树的根结点*/ T-data=ch; T-lchild=CreateTree( );  /*递归实现左子树的建立*/ T-rchild=CreateTree ( );  /*递归实现右子树的建立*/ return T; } } A B C D E ? ? ? ? ? root 此二叉树的前序序列是：ABDCE 中序序列是： BDACE 前序建立二叉树是输入的序列是： AB_