c/c++语言开发共享c语言代码实现二叉树

代码实现二叉树

  #include<stdlib.h>  //二叉树的节点定义  typedef struct treenode  {      char ch;                  //数据域      struct treenode *lchild;  //左孩子      struct treenode *rchild;  //右孩子  }btnode,*pbtnode;    //先序构造二叉树  void createbtree(pbtnode *root)  {      char ch;      ch=getchar();      if(ch=='#')          *root=null;      else{          *root=(pbtnode)malloc(sizeof(btnode));          (*root)->ch=ch;          (*root)->lchild=null;          (*root)->rchild=null;          createbtree(&(*root)->lchild);          createbtree(&(*root)->rchild);      }  }    //先序遍历二叉树  void preorder(pbtnode root)  {      if(root==null)          return;      printf("%-3c",root->ch);      preorder(root->lchild);      preorder(root->rchild);  }    //中序遍历二叉树  void inorder(pbtnode root)  {      if(root==null)          return;      preorder(root->lchild);      printf("%-3c",root->ch);      preorder(root->rchild);  }    //后序遍历二叉树  void postorder(pbtnode root)  {      if(root==null)          return;      preorder(root->lchild);      preorder(root->rchild);      printf("%-3c",root->ch);  }    //输出叶子结点  void displyleaf(pbtnode root)  {      if(root==null)          return;      if(root->lchild==null&&root->rchild==null)          printf("%-3c",root->ch);      else{          displyleaf(root->lchild);          displyleaf(root->rchild);      }  }    //左结点插入  void inseartleftnode(pbtnode root,char ch)  {      pbtnode p,newnode;      if(root==null)          return;      p=root->lchild;      newnode=(pbtnode)malloc(sizeof(btnode));      newnode->ch=ch;      newnode->rchild=null;      newnode->lchild=p;      root->lchild=newnode;  }    //右结点插入  void inseartrightnode(pbtnode root,char ch)  {      pbtnode p,newnode;      if(root==null)          return;      p=root->rchild;      newnode=(pbtnode)malloc(sizeof(btnode));      newnode->ch=ch;      newnode->lchild=null;      newnode->rchild=p;      root->rchild=newnode;  }    //销毁一颗二叉树  void clear(pbtnode* root)  {      pbtnode pl,pr;      if(*root==null)          return;      pl=(*root)->lchild;      pr=(*root)->rchild;      (*root)->lchild=null;      (*root)->rchild=null;      free((*root));      *root=null;      clear(&pl);      clear(&pr);  }    //删除左子树  void deletelefttree(pbtnode root)  {      if(root==null)          return;      clear(&root->lchild);      root->lchild=null;  }    //删除右子树  void deleterighttree(pbtnode root)  {      if(root==null)          return;      clear(&root->rchild);      root->rchild=null;  }    //查找结点  pbtnode   search(pbtnode root,char ch)  {      pbtnode p;      if(root==null)          return null;      if(root->ch==ch)          return root;      else{          if((p=search(root->lchild,ch))!=null)              return p;          else              return  search(root->rchild,ch);      }  }    //求二叉树的高度  int btreeheight(pbtnode root)  {      int lchildheight,rchildheight;      if(root==null)          return 0;      lchildheight=btreeheight(root->lchild);      rchildheight=btreeheight(root->rchild);      return (lchildheight>rchildheight)?(1+lchildheight):(1+rchildheight);  }    //求叶子结点的个数  int countleaf(pbtnode root)  {      if(root==null)          return 0;      if(root->lchild==null&&root->rchild==null)          return 1;      else{          return countleaf(root->lchild)+countleaf(root->rchild);      }  }    //求所有结点的个数  int countall(pbtnode root)  {      if(root==null)          return 0;      return countall(root->lchild)+countall(root->rchild)+1;  }    //复制二叉树  pbtnode copybtree(pbtnode root)  {      pbtnode p,lchild,rchild;      if(root==null)          return null;      lchild=copybtree(root->lchild);      rchild=copybtree(root->rchild);      p=(pbtnode)malloc(sizeof(btnode));      p->ch=root->ch;      p->lchild=lchild;      p->rchild=rchild;      return p;  }