西南科技大学：《数据结构》课程教学资源（教案讲义）实验四 树（一）

、实验目的 1.进一步掌握指针变量,动态变量的含义 2.掌握二叉树的结构特征 掌握用指针类型描述,访问二叉树的运算 ,试验内容 编写以二叉树链表作存储结构的二茬树的建立,及三种遍历算法的实现。 基本思想设二叉树的根指针为t,且以二叉树连表表示,以先序遍历建立该二叉树, 然后用中序、后序遍历算法对该树进行遍历,输出遍历结果。以下图所示的二叉树为例, 先序遍历建树的关键在与确定输入数据序列,即可建立树,其余就非常简单了 (2 7 算法实现 #define null o typedef struct node struct node *lchild. rchild itree creato∥建立二又树(先序遍历的应用) scanf(“%d”,&x); if(x==0) t=malloc(sizeof(bitree)); t->data=x

一、实验目的 1． 进一步掌握指针变量，动态变量的含义。 2． 掌握二叉树的结构特征 3． 掌握用指针类型描述，访问二叉树的运算 二，试验内容 编写以二叉树链表作存储结构的二茬树的建立，及三种遍历算法的实现。 [基本思想]设二叉树的根指针为 t，且以二叉树连表表示，以先序遍历建立该二叉树， 然后用中序、后序遍历算法对该树进行遍历，输出遍历结果。以下图所示的二叉树为例， 先序遍历建树的关键在与确定输入数据序列，即可建立树，其余就非常简单了。 [算法实现] #define null o typedef struct node { int data; struct node *lchild ,rchild; } bitree; bitree *creat()//建立二叉树（先序遍历的应用） { bitree *t; int x; scanf(“%d”,&x); if(x==0) t=null; else { t=malloc(sizeof(bitree)); t->data=x; 4 7 5 8 9 2 3 11 6 ＋ 12 1 3

t->lchild=creato .>rchild=creat(; return t; void inorder(t)/中序遍历二叉树 bitree"t; (t:=null) der(t->lchild); printf(t->data); void postorder(t∥后序遍历二叉树 if(t!=null) postorder(t->rchild); root-creat( inorder(root); postorder(root);

t->lchild=creat(); t->rchild=creat(); } return t; } void inorder(t)//中序遍历二叉树 bitree *t; { if(t!=null) { inorder(t->lchild); prinrf(t->data); inorder(t->rchild); } } void postorder(t)//后序遍历二叉树 bitree *t; { if(t!=null) { postorder (t->lchild); postorder (t->rchild); prinrf(t->data); } } main() { bitree *root; root=creat(); inorder(root); postorder (root); }