二叉树的存储,遍历及应用

//二叉树的顺序存储
//利用数组，按完全二叉树顺序存储
//对任一结点tree[i],有双亲结点：tree[i/2],左孩子结点：tree[2*i],右孩子结点:tree[2*i+1
//二叉链存储表示
typedef struct btnode
{
    dataType data;
    struct btnode *lchild;
    struct btnode *rchild;    
}BTnode,*BiTree;
//静态二叉链存储表示
struct node
{
    datatype data;//数值字段
    int llink,rlink;//指针字段
}tree[n+1];//n:二叉树的结点个数
//二叉树的遍历
//1.先序遍历
void preorder(BiTree T)
{//先序遍历以T为根的二叉树
    if(T!=NULL)
    {
        visite(T->data);//访问根结点
        preorder(T->lchild);//先序遍历左子树
        preorder(T->rchild);//先序遍历右子树
    }    
}
//2.中序遍历
void inorder(BiTree T)
{//中序遍历以T为根的二叉树
    if(T)
    {
        inorder(T->lchild);//中序遍历左子树
        visite(T->data);//访问根结点
        inorder(T->rchild);//中序遍历右子树
    }
}
//3.后序遍历
void postorder(BiTree T)
{
    if(T)
    {
        postorder(T->lchild);//后序遍历左子树
        postorder(T->rchild);//后序遍历右子树
        visite(T->data);//访问根结点    
    }    
}
//应用：求二叉树的高度
int depth(BiTree T)
{
    int l,r;
    if(T==NULL)
        return 0;
    else
    {
        l=depth(T->lchild);
        r=depth(T->rchild);
        return (l>r)?(l+1):(r+1);
    }
}
//应用：求二叉树的结点数
int size(BiTree T)
{
    int l,r;
    if(T==NULL)
        return 0;
    else
    {
        l=size(T->lchild);
        r=size(T->rchild);
        return (l+r+1);
    }
}
//应用：建立动态二叉链表
void createtree(BiTree T)
{
    char ch;
    ch=getchar();
    if(ch==' ')
        T=NULL;
    else
    {
        T=(struct node*)malloc(sizeof(struct node));
        T->data=ch;
        createtree(T->lchild);
        createtree(T->rchild);
    }
}

最后

以上就是辛勤舞蹈为你收集整理的二叉树的存储,遍历及应用的全部内容，希望文章能够帮你解决二叉树的存储,遍历及应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。