二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合

性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:深度为k的二叉树至多有2^k - 1个结点 性质3:对任意一棵二叉树T,若终端结点数为n0,而其度数为2的结点数为n2,则n0 = n2 + 1 满二叉树:深度为k且有2^-1个结点的树 完全二叉树:深度为k,结点数为n的二叉树,如果其结点1~n的位置序号分别与等高的满二叉树的结 点1~n的位置序号一一对应,则为完全二叉树。 性质4:具有n的结点的完全二叉树深度为log2n + 1 性质5:对于具有n个结点的完全二叉树,如果按照从上到下和从左到右的顺序对二叉树中的所有结点 从1开始顺序编号,则对于任意的序号为i的结点有: 1.如i = 1,则序号为i的结点为根结点,无双亲结点;如i>1,则序号为i的结点的双亲结点序号为 i/2。 2.如2i>n,则序号为i的结点无左孩子;如2i<=n,则序号为i的结点的左孩子结点的序号为2i。 3.如2i+1>n,则序号为i的结点无右孩子,如2i+1<=n,则序号为i的结点的右孩子序号为2i+1。

1.宏定义:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define datatypebt char
#define MAXNODE 1024
#define BOTTOMNODE 1024
#define FULLNODE 1024
2.结构体:
typedef struct bitnode
{
    datatypebt data;
    struct bitnode *lchild,*rchild;
}Bitnode,*Bitree;
3.基本函数:
Bitree Initiate_Bitree()
/*初始化二叉树函数1.先决条件:无2.函数作用:初始化一棵空的带头结点的二叉树,返回头结点的地址*/
{
    Bitnode *bt;
    bt=(Bitnode *)malloc(sizeof(Bitnode));
    bt->lchild=NULL;
    bt->rchild=NULL;
    return bt;
}
Bitnode *Create_Bitree(datatypebt x,Bitnode *lbt,Bitnode *rbt)
/*建立二叉树函数1.先决条件:无2.函数作用:生成一棵以x为根结点数据域信息,以lbt,rbt为左右子树的二叉树,返回新二叉树的地址*/
{
    Bitree p;
    p=(Bitnode *)malloc(sizeof(Bitnode));
    p->data=x;
    p->lchild=lbt;
    p->rchild=rbt;
    return p;
}
void Precreate_Bitree(Bitree *T)
/*先序构建二叉树函数1.先决条件:T是子树根结点的地址2.函数作用:以先序遍历序列构造二叉树链表存储的二叉树T*/
{
    char ch;
    scanf("%c",&ch);
    if(ch=='0')
        *T=NULL;
    else
    {
        (*T)=(Bitnode *)malloc(sizeof(Bitnode));
        (*T)->data=ch;
        Precreate_Bitree(&(*T)->lchild);
        Precreate_Bitree(&(*T)->rchild);
    }
}
void Preinorder_Bitree(Bitree *t,char preod[],int i,int j,char inod[],int k,int h)
/*先中序恢复树函数1.先决条件:t是子树根结点的地址2.函数作用:preod[i..j]为先序子序列,inod[k..h]为中子序序列,根据先序序列和中序序列恢复二叉树t*/
{
    int m;
    *t=(Bitnode *)malloc(sizeof(Bitnode));
    (*t)->data=preod[i];
    m=k;
    while(inod[m]!=preod[i])
        m++;
    if(m==k)
        (*t)->lchild=NULL;
    else
        Preinorder_Bitree(&(*t)->lchild,preod,i+1,i+m-k,inod,k,m-1);
    if(m==h)
        (*t)->rchild=NULL;
    else
        Preinorder_Bitree(&(*t)->rchild,preod,i+m-k+1,j,inod,m+1,h);
}
int Recovery_Bitree(Bitree bt,char preod[],char inod[],int n)
/*先中序恢复树函数1.先决条件:初始化二叉树,bt为头结点,拥有Preinorder_Bitree()函数2.函数作用:根据先序和中序序列恢复二叉树bt,成功返回1*/
{
    if(n<=0)
        bt->lchild=NULL;
    else Preinorder_Bitree(&bt->lchild,preod,0,n-1,inod,0,n-1);
    return 1;
}
void Postfree_Bitree(Bitree p)
/*后序释放函数1.先决条件:p为子树根结点的地址2.函数作用:释放子树p的全部空间*/
{
    if(p==NULL)
        return ;
    Postfree_Bitree(p->lchild);
    Postfree_Bitree(p->rchild);
    free(p);
}
int Empty_Bitree(Bitree bt)
/*判空函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:若二叉树bt为空,则返回1,否则返回0*/
{
    if(bt->lchild==NULL)
        return 1;
    else return 0;
}
Bitnode *Root_Bitree(Bitree bt)
/*求根函数1.先决条件:初始化二叉树,bt为头结点2.函数作用:求二叉树bt的根结点,返回根结点的地址,若bt为空二叉树,则函数返回NULL*/
{
    return bt->lchild;
}
Bitnode *Search_Bitree(Bitree bt,datatypebt x)
/*查找函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:在二叉树bt中查找值为x的数据元素,成功返回其地址,找不到返回NULL*/
{
    Bitree p=NULL;
    if(bt)
    {
        if(bt->data==x)
            return bt;
        if(bt->lchild)
            p=Search_Bitree(bt->lchild,x);
        if(p)
            return p;
        if(bt->rchild)
            p=Search_Bitree(bt->rchild,x);
        if(p)
            return p;
    }
    return NULL;
}
int InsertL_Bitree(Bitnode *parent,datatypebt x)
/*左插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其左子树之间插入数据元素为x的结点,成功返回1*/
{
    Bitnode *p;
    if(parent==NULL)
    {
        printf("插入出错.\n");/*此句可以根据情况删除*/
        return 0;
    }
    p=(Bitnode *)malloc(sizeof(Bitnode));
    p->data=x;
    p->lchild=NULL;
    p->rchild=NULL;
    if(parent->lchild==NULL)
        parent->lchild=p;
    else
    {
        p->lchild=parent->lchild;
        parent->lchild=p;
    }
    return 1;
}
int InsertR_Bitree(Bitnode *parent,datatypebt x)
/*右插入函数1.先决条件:无2.函数作用:在二叉树中的parent所指结点和其右子树之间插入数据元素为x的结点,成功返回1*/
{
    Bitnode *p;
    if(parent==NULL)
    {
        printf("插入出错.\n");/*此句可以根据情况删除*/
        return 0;
    }
    p=(Bitnode *)malloc(sizeof(Bitnode));
    p->data=x;
    p->lchild=NULL;
    p->rchild=NULL;
    if(parent->rchild==NULL)
        parent->rchild=p;
    else
    {
        p->rchild=parent->rchild;
        parent->rchild=p;
    }
    return 1;
}
int DeleteL_Bitree(Bitnode *parent)
/*左删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的左子树,成功返回1*/
{
    Bitnode *p;
    if(parent==NULL||parent->lchild==NULL)
    {
        printf("删除出错.\n");/*此句可以根据情况删除*/
        return NULL;
    }
    p=parent->lchild;
    parent->lchild=NULL;
    Postfree_Bitree(p);
    return 1;
}
int DeleteR_Bitree(Bitnode *parent)
/*右删除函数1.先决条件:parent为子树的根结点,拥有Postfree_Bitree()函数2.函数作用:在二叉树中删除parent的右子树,成功返回1*/
{
    Bitnode *p;
    if(parent==NULL||parent->rchild==NULL)
    {
        printf("删除出错.\n");/*此句可以根据情况删除*/
        return NULL;
    }
    p=parent->rchild;
    parent->rchild=NULL;
    Postfree_Bitree(p);
    return 1;
}
Bitnode *Parent_Bitree(Bitree bt,Bitnode *x)
/*求双亲函数1.先决条件:初始化二叉树bt,bt是子树根或头结点;2.函数作用:求二叉树bt中结点x的双亲结点,若结点x是二叉树的根结点或二叉树bt中无结点x,则返回NULL*/
{
    Bitnode *p=NULL;
    if(bt)
    {
        if(bt->lchild==x||bt->rchild==x)
        {
            p=bt;
            return p;
        }
        p=Parent_Bitree(bt->lchild,x);
        if(p)
            return p;
        p=Parent_Bitree(bt->rchild,x);
        if(p)
            return p;
    }
    return NULL;
}
void Visit_Bitree(Bitnode *p)
/*访问函数1.先决条件:无2.函数作用:输出一个二叉树结点p的数据*/
{
    if(p)
        printf("%c ",p->data);
}
int Countleaf_Bitree(Bitree bt)
/*统计叶子数函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:统计二叉树bt中叶子结点的个数,返回值为bt的叶子数*/
{
    if(bt==NULL)
        return 0;
    if(bt->lchild==NULL&&bt->rchild==NULL)
        return 1;
    return Countleaf_Bitree(bt->lchild)+Countleaf_Bitree(bt->rchild);
}
void Preorder_Bitree(Bitree bt)
/*先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法先序遍历二叉树bt*/
{
    if(bt==NULL)
        return;
    Visit_Bitree(bt);
    Preorder_Bitree(bt->lchild);
    Preorder_Bitree(bt->rchild);
}
void Inorder_Bitree(Bitree bt)
/*中序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法中序遍历二叉树bt*/
{
    if(bt==NULL)
        return;
    Inorder_Bitree(bt->lchild);
    Visit_Bitree(bt);
    Inorder_Bitree(bt->rchild);
}
void Postorder_Bitree(Bitree bt)
/*后序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点;2.函数作用:用递归方法后序遍历二叉树bt*/
{
    if(bt==NULL)
        return ;
    Postorder_Bitree(bt->lchild);
    Postorder_Bitree(bt->rchild);
    Visit_Bitree(bt);
}
int NRPreorder_Bitree(Bitree bt)
/*非递归先序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归先序遍历二叉树bt,空树返回0,非空树返回1,栈溢出返回-1*/
{
    Bitnode *p,*s[MAXNODE];/*MAXNODE最少是二叉树的层数h*/
    int top=-1;
    if((p=bt)==NULL)
    {
        printf("此为空二叉树.\n");/*此句可以根据情况删除*/
        return 0;
    }
    while(p!=NULL||top!=-1)
    {
        while(p!=NULL)
        {
            Visit_Bitree(p);
            top++;
            if(top>=MAXNODE)
            {
                printf("栈溢出.\n");
                return -1;
            }
            s[top]=p;
            p=p->lchild;
        }

        p=s[top];
        top--;
        p=p->rchild;
    }
    return 1;
}
int NRInorder_Bitree(Bitree bt)
/*非递归中序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归中序遍历二叉树bt,空树返回0,非空树返回1,栈溢出返回-1*/
{
    Bitnode *p,*s[MAXNODE];/*MAXNODE最少是二叉树的层数h*/
    int top=-1;
    if((p=bt)==NULL)
    {
        printf("此为空二叉树.\n");/*此句可以根据情况删除*/
        return 0;
    }
    while(p!=NULL||top!=-1)
    {
        while(p!=NULL)
        {
            top++;
            if(top>=MAXNODE)
            {
                printf("栈溢出.\n");
                return -1;
            }
            s[top]=p;
            p=p->lchild;
        }
        p=s[top];
        Visit_Bitree(p);
        top--;
        p=p->rchild;
    }
    return 1;
}
int NRPostorder_Bitree(Bitree bt)
/*非递归后序遍历函数1.先决条件:初始化二叉树,bt是子树根或头结点2.函数作用:非递归后序遍历二叉树bt,p为当前结点指针,q为前驱结点指针,空树返回0,非空树返回1,栈溢出返回-1*/
{
    Bitnode *s[MAXNODE];/*MAXNODE最少是二叉树的层数h*/
    int top;
    Bitnode *p,*q;
    q=NULL;
    p=bt;
    if(!p)
        return 0;
    top=-1;
    while(p!=NULL||top!=-1)
    {
        while(p!=NULL)
        {
            top++;
            if(top>=MAXNODE)
            {
                printf("栈溢出.\n");
                return -1;
            }
            s[top]=p;
            p=p->lchild;
        }
        if(top>-1)
        {
            p=s[top];
            if(p->rchild==NULL||p->rchild==q)
            {
                Visit_Bitree(p);
                q=p;
                top--;
                p=NULL;
            }
            else
                p=p->rchild;
        }
    }
    return 1;
}
int Levelorder_Bitree(Bitree bt)
/*层次遍历二叉树函数1.先决条件:bt是子树根结点2.函数作用:层次遍历二叉树bt,队满溢出返回-1,空树返回0,非空树返回1*/
{
    Bitnode *sq[BOTTOMNODE];/*MAXNODE最少是2^(h-1),其中h为层数*/
    int front=-1,rear=0,num=0;
    if(bt==NULL)
        return 0;
    if(num<MAXNODE)
    {
        sq[rear]=bt;
        num++;
    }
    else
    {
        printf("队满.\n");/*可视情况删除此句*/
        return -1;
    }
    while(num)
    {
        front=(front+1)%MAXNODE;
        num--;
        Visit_Bitree(sq[front]);
        if(sq[front]->lchild)
            if(num==MAXNODE)
            {
                printf("队满.\n");/*可视情况删除此句*/
                return -1;
            }
            else
            {
                rear=(rear+1)%MAXNODE;
                sq[rear]=sq[front]->lchild;
                num++;
            }
        if(sq[front]->rchild)
            if(num==MAXNODE)
            {
                printf("队满.\n");/*可视情况删除此句*/
                return -1;
            }
            else
            {
                rear=(rear+1)%MAXNODE;
                sq[rear]=sq[front]->rchild;
                num++;
            }
    }
    return 1;
}
int Posttreedepth_Bitree(Bitree bt)
/*后序二叉树高度函数1.先决条件:bt为子树根结点2.函数作用:通过后序遍历求二叉树bt的高度,返回二叉树的高度*/
{
    int hl,hr,max;
    if(bt!=NULL)
    {
        hl=Posttreedepth_Bitree(bt->lchild);
        hr=Posttreedepth_Bitree(bt->rchild);
        max=hl>hr?hl:hr;
        return max+1;
    }
    else
        return 0;
}
void Pretreedepth_Bitree(Bitree bt,int h,int *depth)
/*前序二叉树高度函数1.先决条件:bt是子树根结点,h为bt结点所在层次,初值为1,depth为当前求得的最大层次,调用前初值为0;
2.函数作用:通过先序遍历求二叉树bt高度*/
{
    if(bt!=NULL)
    {
        if(h>*depth)
            *depth=h;
        Pretreedepth_Bitree(bt->lchild,h+1,depth);
        Pretreedepth_Bitree(bt->rchild,h+1,depth);
    }
}
void Pretreelevel_Bitree(Bitree bt,int h)
/*前序二叉树打印层号函数1.先决条件:bt是子树根结点,h为bt结点所在层次,初值为1;2.函数作用:通过先序遍历打印二叉树bt中结点和层号*/
{
    if(bt!=NULL)
    {
        printf("%d %c\n",h,bt->data);
        Pretreelevel_Bitree(bt->lchild,h+1);
        Pretreelevel_Bitree(bt->rchild,h+1);
    }
}
void Pretreenode_Bitree(Bitree bt,int *num)
/*前序二叉树结点函数1.先决条件:bt是子树根结点,num为累计的结点数,调用前初值为0;2.函数作用:通过先序遍历求二叉树的结点数目num*/
{
    if(bt!=NULL)
    {
        *num=*num+1;
        Pretreenode_Bitree(bt->lchild,num);
        Pretreenode_Bitree(bt->rchild,num);
    }
}
int Print1_Bitree(Bitree bt)
/*按树状打印二叉树函数1.先决条件:bt是子树根结点,拥有Posttreedepth_Bitree()函数2.函数作用:按树状打印二叉树bt*/
{
    int i,j,k,n,flag=1,kongge,chuduigeshu=1;
    Bitnode *sq[FULLNODE],*temp;/*FULLNODE最少为满二叉树结点数+1*/
    int rear,front,num;
    if(bt==NULL)
        return 0;
    front=rear=FULLNODE-1;
    num=0;
    if(num==FULLNODE)
    {
        printf("队满.\n");/*可视情况删除此句*/
        return -1;
    }
    else
    {
        rear=(rear+1)%FULLNODE;
        sq[rear]=bt;
        num++;
    }
    n=Posttreedepth_Bitree(bt);
    for(i=1,kongge=1;i<n;i++)
        kongge=kongge*2;
    for(i=1;i<=n;i++)
    {
        j=1;
        while(j<=chuduigeshu)
        {
            if(flag==1)
            {
                for(k=1;k<kongge;k++)
                    printf(" ");/*因树结点的数据长度不同而不同*/
                front=(front+1)%FULLNODE;
                temp=sq[front];
                num--;
                if(temp)
                {
                    printf("%c",temp->data);/*因二叉树数据类型不同而不同*/
                    if(num==FULLNODE-1)
                    {
                        printf("队满.\n");/*可视情况删除此句*/
                        return -1;
                    }
                    else
                    {
                        rear=(rear+1)%FULLNODE;
                        sq[rear]=temp->lchild;
                        rear=(rear+1)%FULLNODE;
                        sq[rear]=temp->rchild;
                        num=num+2;
                    }
                }
                else
                {
                    printf(" ");/*因树结点的数据长度不同而不同*/
                    if(num==FULLNODE-1)
                    {
                        printf("队满.\n");/*可视情况删除此句*/
                        return -1;
                    }
                    else
                    {
                        rear=(rear+1)%FULLNODE;
                        sq[rear]=NULL;
                        rear=(rear+1)%FULLNODE;
                        sq[rear]=NULL;
                        num=num+2;
                    }
                }
                j++;
            }
            else
                for(k=1;k<=kongge;k++)
                    printf(" ");/*因树结点的数据长度不同而不同*/
            flag=-flag;
        }
        printf("\n");
        kongge=kongge/2;
        chuduigeshu=chuduigeshu*2;
        flag=1;
    }
    return 1;
}
void Print2_Bitree(Bitree bt,int nlayer)
/*按竖向树状打印二叉树函数1.先决条件:bt为子树根结点,nlayer为bt指向结点所在层次,初值为0;2.函数作用:按竖向树状打印二叉树bt*/
{
    if(bt==NULL)
        return ;
    Print2_Bitree(bt->rchild,nlayer+1);
    for(int i=0;i<nlayer;i++)
        printf(" ");/*因树结点的数据长度不同而不同*/
    printf("%c\n",bt->data);/*因树结点的数据类型不同而不同*/
    Print2_Bitree(bt->lchild,nlayer+1);
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android机动车

数据结构——遍历二叉树

二叉树的遍历:是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。

10010
来自专栏武培轩的专栏

ArrayList源码解析(JDK1.8)

1 package java.util; 2 3 import sun.misc.SharedSecrets; 4 5 imp...

31750
来自专栏Android机器圈

数据结构与算法 -- 二叉树链式详解((非)/递归遍历,叶子个数,深度计算)

PS:树型结构是一种重要的非线性数据结构,教科书上一般都是树与二叉树,由此可见,树和二叉树是有区别和联系的,网上有人说二叉树是树的一种特殊形式,但经过查资料,树...

11450
来自专栏决胜机器学习

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六)——树与二叉树之概念及存储结构 (原创内容,转载请注明来源,谢谢) 一、树的含义 1、树为非线性结构,是n(n>=0)个节点的有限集,非空树...

544100
来自专栏我是东东强

常见算法之二叉树遍历

所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、...

17920
来自专栏xingoo, 一个梦想做发明家的程序员

B树 B-树 B+树 B*树

B树 即二叉搜索树:        1.所有非叶子结点至多拥有两个儿子(Left和Right);        2.所有结点存储一个关键字;        3...

20870
来自专栏LeetCode

LeetCode 102 & 103 &107 & 637. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie,...

10500
来自专栏王硕

原 B树C语言代码实现

748100
来自专栏数据结构与算法

codevs 1814 最长链

1814 最长链 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 现给出...

31450
来自专栏mukekeheart的iOS之旅

二叉树的基本概念和遍历

一、二叉树的基本概念 平衡二叉树:如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1。(空树是平衡二叉树)  1 //判断二叉树...

262100

扫码关注云+社区

领取腾讯云代金券