二叉树是一种特殊的树.doc

《二叉树是一种特殊的树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、二叉树是一种特殊的树，每个节点只能有最多二个孩子节点，或者没有孩子节点。建立，与撤销或遍历二叉树主要是靠递归的方法。#include#includetypedefstructstud/*定义二叉树的结构，只有一个数据项，和两个孩子节点*/{chardata;structstud*left;structstud*right;}bitree;voiddestroy(bitree**root)/*撤销二叉树，这里用的是递归和二级指针*/{if(*root!=NULL&&(*

2、root)->left!=NULL)/*当前结点与左子树不空，递归撤销左子树*/destroy(&(*root)->left);if(*root!=NULL&&(*root)->right!=NULL)/*当前结点与右子树不空，递归撤销右子树*/destroy(&(*root)->right);free(*root);/*左右子树都为空，撤销该节点，并递归撤销其上的所有节点*/}voidinititate(bitree**root)/*初始化二叉树的头结点，并分配空间*/{*root=(bitree*)m

3、alloc(sizeof(bitree));(*root)->left=NULL;(*root)->right=NULL;}bitree*insert_left(bitree*curr,charx)/*在左子树插入数据*/{bitree*s,*t;if(curr==NULL)  returnNULL;t=curr->left;/*保存当前左子树的数据*/s=(bitree*)malloc(sizeof(bitree));s->data=x;s->left=t;/*新结点指向原来的左子树*/s->right

4、=NULL;curr->left=s;/*原来的节点指向新结点*/returncurr->left;}bitree*insert_right(bitree*curr,charx)/*在这个节点的右子树插入数据*/{bitree*s,*t;if(curr==NULL)  returnNULL;t=curr->right;s=(bitree*)malloc(sizeof(bitree));s->data=x;s->left=NULL;s->right=t;curr->right=s;returncurr->r

5、ight;}bitree*delete_left(bitree*curr)/*删除当前结点的左子树*/{if(curr!=NULL&&curr->left!=NULL)  destroy(&curr->left);/*删除左子树本身及其以后的所有节点*/curr->left=NULL;returncurr;}bitree*delete_right(bitree*curr)/*删除右子树*/{if(curr!=NULL&&curr->right!=NULL)  destroy(&curr->right);c

6、urr->right=NULL;returncurr;}voidpreorder(bitree*root)/*递归先序遍历根节点*/{if(root!=NULL){  printf("%c",root->data);  preorder(root->left);  preorder(root->right);}}voidmidorder(bitree*root)/*递归中序遍历根节点*/{if(root!=NULL){  midorder(root->left);  printf("%c",root->d

7、ata);  midorder(root->right);}}voidpostorder(bitree*root))/*递归后序遍历根节点*/{if(root!=NULL){  postorder(root->left);  postorder(root->right);  printf("%c",root->data);}}bitree*search(bitree*root,charx))/*递归某一数值*/{bitree*find=NULL;if(root!=NULL){  if(root->data

8、==x)   find=root;  else  {   find=search(root->left,x);)/*在左子树查找*/   if(find==NULL))/*左子树没有找到的话*/    find=search(root->right,x);/*右子树找*/  }}returnfind;}voidmain(){  bitree*root,*s,*p,*find;  inti,j,k;  charc='E';  i