数据结构课件 - 河南大学精品课程网

遍历的算法实现：用递归形式格外简单！

回忆1：二叉树结点的数据类型定义：typedef struct node *tree_pointer;typedef struct node {int data;

tree_pointer left_child, right_child;} node;

回忆2：第1章自测卷4.2题：

long int fact(n)//求n!int n;则三种遍历算法可写出:

{ long f;

if(n>1)f=n*fact(n-1);else f=1;return(f); }

33

结点数据类型自定义typedef struct liuyu{int data;

struct liuyu *lchild,*rchild；} liuyu;liuyu *root;

中序遍历算法LDR(x*root){if(root!=NULL){LDR(root->lchild);

printf(“%d”,root->data);LDR(root->rchild);}return(0);}

先序遍历算法

DLR(liuyu*root)

{if(root!=NULL)//非空二叉树

{printf(“%d”,root->data);//访问DDLR(root->lchild);//递归遍历左子树DLR(root->rchild);//递归遍历右子

树

}return(0);}后序遍历算法LRD(x*root){if(root!=NULL){LRD(root->lchild);LRD(root->rchild);

printf(“%d”,root->data);}return(0);}

34

对遍历的分析：

1. 从前面的三种遍历算法可以知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。

ACB从虚线的出发点到终点的路径上，每个结点经过3次。

第1次经过时访问＝先序遍历第2次经过时访问＝中序遍历第3次经过时访问＝后序遍历2. 二叉树遍历的时间效率和空间效率时间效率:O(n)//每个结点只访问一次空间效率:O(n)//栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）35

DEFG例：【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。

思路：输出叶子结点比较简单，用任何一种遍历算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。DLR(liuyu*root)

//采用中序遍历的递归算法

{if(root!=NULL)//非空二叉树条件，还可写成if(root)

{if(!root->lchild&&!root->rchild)//是叶子结点则统计并打印{sum++;printf(\DLR(root->lchild);}return(0);}

36

//递归遍历左子树，直到叶子处；

DLR(root->rchild);}//递归遍历右子树，直到叶子处；