实验四 二叉树
一、实验学时  2学时
二、背景知识
二叉树的存储定义分为两种：
1．顺序存储结构：
  #define MAX_TREE_SIZE 100    //最大结点数
  typedef TelemType SqBiTree[MAX_TREE_SIZE];  //0号单元存储根结点
  SqBiTree bt;
2．链式存储结构:
typedef struct BiTNode           
{
TElemType data;
struct BiTNode *lchild,*rchild;  //左右孩子指针
}BiTNode,*BiTree;
三、目的要求
    1．掌握树的基本概念、二叉树的基本操作；
2．重点掌握二叉树的生成、遍历及求深度等算法；
四、实验内容
1． 编写程序实现二叉树的前序遍历的算法
【问题描述】
前序遍历的方式是每遍历到一个结点就立刻处理结点。遍历的顺序是先向着树的左方走直到无法前进后，才转往右方走。
【基本要求】                                          图 4-1
    首先创建二叉树，然后编写前序遍历的函数，最后编写主函数。
【测试数据】
如图3-1所示二叉树的前序遍历的结果为：1,2,4,5,3,6。
【实现提示】
（1） 先检查是否已经到达叶结点，也就是指针root等于NULL。
（2） 如果不是叶结点表示可以继续走，此时的处理如下：
1） 处理目前的结点；
2） 递归调用前序遍历的函数（root->left）往左走；
3） 递归调用前序遍历的函数（root->right）往右走。
2． 编写程序实现二叉树的后序遍历的算法
【问题描述】
    后序遍历的方式刚好和前序遍历的方式相反，它是等到结点的两个子结点都遍历过后才运行处理。
【基本要求】
    首先创建二叉树，然后编写后序遍历的函数，最后编写主函数。
【测试数据】
如图3-1所示二叉树的后序遍历的结果为：4,5,2,6,3,1。
【实现提示】
（1） 先检查是否已经到达叶结点，也就是指针root等于NULL。
（2） 如果不是叶结点表示可以继续走，此时的处理如下：
1) 递归调用后序遍历的函数（root->left）往左走；
2) 递归调用后序遍历的函数（root->right）往右走；
3) 处理目前的结点。
五、程序实例
二叉树中序遍历的递归算法。
#include "stdlib.h"
#include “stdio.h”
struct tree
{ int data;
struct tree *left;
struct tree *right;
};
typedef struct tree treenode;
typedef struct tree *btree;
/*---------------------插入结点----------------------*/
btree insertnode(btree root,int value)
二叉树定义
{btree newnode;  /* 根指针 */
btree current;  /* 当前结点指针 */
btree back;    /* 父结点指针 */
/* 创建结点内存 */
newnode=(btree)malloc(sizeof(treenode));
newnode->data=value;
newnode->left=NULL;
newnode->right=NULL;
if(root==NULL)
  {return newnode;}
else
  {current=root;
  while(current!=NULL)
    {back=current;
    if(current->data>value)
      current=current->left;
    else
      current=current->right;
    }
  if(back->data>value)
  back->left=newnode;
  else
  back->right=newnode;
  }
return root;
}
/*------------------创建二叉树----------------*/
btree createbtree(int *data,int len)
{btree root=NULL;
int i;
for(i=0;i<len;i++)
root=insertnode(root,data[i]);
return root;
}
/*------------------二叉树中序遍历----------------*/
void inorder(btree ptr)
{if(ptr!=NULL)
{inorder(ptr->left);
printf("[%2d]\n",ptr->data);
inorder(ptr->right);
}
}
/*------------------主函数---------------------*/
void main()
{btree root=NULL;
int data[9]={5,6,4,8,2,3,7,1,9};
root=createbtree(data,9);
printf("out put the bitree:\n");
inorder(root);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。