树的定义

树是n个节点的有限集。当n=0时称为空树。在任意一棵非空树中应满足:

  • 有且只有一个特定的称为根的结点。

  • 当n>1时有m个互不相交的优先集,称为根的子树。

节点结构

数据,左孩子和右孩子(分支标识)

编写笔记

  • 建树需要辅助队列-判断节点左右是否满了,满了移动到下一个节点处。建树过程中插入新节点时也要给辅助队列插入。

  • calloc可使结构体变量中的成员置NULL。

代码

结构体

需要辅助队列,如下:

typedef char ElemType;
typedef struct TreeNode{
    ElemType data;
    struct TreeNode *Lchild;
    struct TreeNode *Rchild;
}TreeNode,*TreeP;
//tag给辅助队列用
typedef struct tag{
    TreeP p;
    struct tag *next;
}tag,*tagP;

初始化

声明两个树状结构体变量,分别用作新节点和树根。再声明辅助队列头尾,现在位置以及队列新节点.

插入节点

如果是树的第一个节点,则把辅助队列指向listpnewTree指向pnew作为树根。
插入时先在辅助队列尾插,后用辅助队列的pur判断树中需要插入的节点位置,判断左右孩子是否有空,先左后右,插满后前进到下一个节点。

TreeP pnew;     //创建新节点
    TreeP tree=NULL;        //创建树根
    char c;
    tagP phead=NULL,ptail=NULL,listpnew=NULL,pcur;
    while(scanf("%c",&c)){
        if(c=='\n'){
            break;
        }
        //calloc申请的空间大小时两个参数直接相乘,且对空间初始化置0.
        pnew=(TreeP)calloc(1,sizeof(TreeNode));
        pnew->data=c;
        listpnew=(tagP)calloc(1,sizeof(tag));       //给队列节点申请空间
        listpnew->p=pnew;
        //如果是树的第一个节点
        if(tree==NULL){
            tree=pnew;
            phead=listpnew;
            ptail=listpnew;
            pcur=listpnew;
        }else{
            //先入队列
            ptail->next=listpnew;
            ptail=listpnew;
            if(pcur->p->Lchild==NULL){
                pcur->p->Lchild=pnew;   //左孩子为空
            }else if(pcur->p->Rchild==NULL){
                pcur->p->Rchild=pnew;   //右孩子为空
                pcur=pcur->next;    //满了pcur指向下一个
            }
        }

    }

输入abcdefgh后得到结果部分如下: