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;
}