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

二叉树是一种特殊的树，每个节点只能有最多二个孩子节点，或者没有孩子节点。建立，与撤销或遍历二叉树主要是靠递归的方法。#include#includetypedef struct stud/*定义二叉树的结构，只有一个数据项，和两个孩子节点*/char data;struct stud *left;struct stud *right; bitree;void destroy(bitree *root)/*撤销二叉树，这里用的是递归和二级指针*/if(*root!=NULL&(*root)-left!=NULL)/*当前结点与左子树不空，递归撤销左子树*/destroy(&(*root)-left);if(*root!=NULL&(*root)-right!=NULL)/*当前结点与右子树不空，递归撤销右子树*/destroy(&(*root)-right);free(*root);/*左右子树都为空，撤销该节点，并递归撤销其上的所有节点*/void inititate(bitree *root)/*初始化二叉树的头结点，并分配空间*/*root=(bitree *)malloc(sizeof(bitree );(*root)-left=NULL;(*root)-right=NULL;bitree *insert_left(bitree *curr,char x)/*在左子树插入数据*/bitree *s,*t;if(curr=NULL) return NULL;t=curr-left;/*保存当前左子树的数据*/s=(bitree *)malloc(sizeof(bitree);s-data=x;s-left=t;/*新结点指向原来的左子树*/s-right=NULL;curr-left=s;/*原来的节点指向新结点*/return curr-left;bitree *insert_right(bitree *curr,char x)/*在这个节点的右子树插入数据*/bitree *s,*t;if(curr=NULL) return NULL;t=curr-right;s=(bitree *)malloc(sizeof(bitree);s-data=x;s-left=NULL;s-right=t;curr-right=s;return curr-right;bitree *delete_left(bitree *curr)/*删除当前结点的左子树*/if(curr!=NULL&curr-left!=NULL) destroy(&curr-left);/*删除左子树本身及其以后的所有节点*/curr-left=NULL;return curr;bitree *delete_right(bitree *curr)/*删除右子树*/if(curr!=NULL&curr-right!=NULL) destroy(&curr-right);curr-right=NULL;return curr;void preorder(bitree *root)/*递归先序遍历根节点*/if(root!=NULL) printf(%c ,root-data); preorder( root-left); preorder( root-right);void midorder(bitree *root)/*递归中序遍历根节点*/if(root!=NULL) midorder( root-left); printf(%c ,root-data); midorder(root-right);void postorder(bitree *root)/*递归后序遍历根节点*/if(root!=NULL) postorder(root-left); postorder( root-right); printf(%c ,root-data);bitree *search(bitree *root,char x)/*递归某一数值*/bitree *find=NULL;if(root!=NULL) if(root-data=x) find=root; else find=search (root-left,x);)/*在左子树查找*/ if(find=NULL)/*左子树没有找到的话*/ find=search (root-right,x);/*右子树找*/ return find;void main() bitree *root,*s,*p,*find; int i,j,k; char c=E; inititate(&root); p=insert_left(root,A); p=insert_left(p,B); p=insert_left(p,D); p=insert_right(p,G); p=insert_right(root-left,C); insert_left(p,E); insert_right(p,F); printf(前序遍历为n); preorder(root-left); printf(n中序遍历为n); midorder(root-left); printf(n后序遍历为n); postorder(root-left); find=search(root-left,c); if(find) printf(这个元素%c在二叉树中n,c); else printf(这个元素%c不在二叉树中n,c); printf(撤销根节点的左子树为n); delete_left(root-left); printf(n前序遍历为n); preorder(root-left); printf(n中序遍历为n); midorder(root-left); printf(n后序遍历为n); postorder(root-left); printf(n撤销根节点的右子树为n); delete_right(root-left)