C语言数据结构基础学习笔记—

树是一种一对多的逻辑结构，树的子树之间没有关系。

度：结点拥有的子树数量。

树的度：树中所有结点的度的最大值。

结点的深度：从根开始，自顶向下计数。

结点的高度：从叶结点开始，自底向上计数。

树的性质：①树的结点数等于所有结点的度数加1；②度为m的树中第i层上至多有m^i-1个结点（i>=1）；③度为h的m叉数至多有(m^h-1)/(m-1)个结点；④具有n个结点的m叉树的最小高度为[log_m(n(m-1)+1)]。

树的表示方法：

①双亲表示法（顺序表示法）：根节点parent=-1

typedef char ElemType;

typedef struct TNode{

    ElemType data;                     //结点数据

    int parent;                        //该结点双亲在数组中的下标

}TNode;                                //结点数据类型

#define MaxSize 50

typedef struct{

    TNode nodes[MaxSize];              //结点数组

    int n;                             //结点数量

}Tree;                                 //树的双亲表示结构

②孩子表示法：把每个孩子的孩子结点排列起来存储成一个单链表，n个结点就有n个单链表，n个单链表的头指针又存储在一个顺序表（数组）中

typedef char ElemType;

typedef struct CNode{

    int child;                         //该孩子在表头数组的下标

    struct CNode *next;                //指向该结点的下一个孩子结点

}CNode,*Child;                         //孩子结点数据类型

typedef struct{

    ElemType data;                     //结点数据域

    Child firstchild;                  //指向该结点的第一个孩子结点

}TNode;                                //孩子结点数据类型

 #define MaxSize 100

 typedef struct{

     TNode nodes[MaxSize];             //结点数据域

     int n;                            //树中的结点个数

 }Tree;                                //树的孩子表示结构

③孩子兄弟表示法：分别指向孩子结点和兄弟结点，其结点结构为：

 typedef char ElemType;

 typedef struct CSNode{

     ElemType data;                          //该结点的数据域

     struct CSNode *firstchild,*rightsib;    //指向该结点的第一个孩子结点和该结点的右兄弟结点

 }CSNode;                                    //孩子兄弟结点数据类型

二叉树：①每个结点最多有两棵子树；②左右子树有顺序。

二叉树的种类：①斜二叉树；②满二叉树；③完全二叉树。

满二叉树是绝对的等腰三角形，每一个非叶子结点都有两个子树，而完全二叉树的结点个数随意，只需满足其层序遍历的序号与满二叉树相同即可。

二叉树的顺序存储：用一组地址连续的存储单元依次自上向下，自左至右存储完全二叉树上的结点元素，非完全二叉树需在对应空缺编号处保留数组空位，这是一种极其浪费的存储方式。

二叉树的链式存储：

①二叉链表：两个指针指向左右孩子结点。其实现为：

typedef struct BiTNode{

    ELemType data;

    struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

②三叉链表：在二叉链表的基础上添加一个指针指向双亲。

二叉树的遍历：按某种次序依次访问树中的每个结点，使得每个结点均被访问人一次，而且仅被访问一次。

有以下四种方法：

①先序遍历：a.访问根节点；b.先序遍历左子树；c.先序遍历右子树。

递归实现：

void PreOrder(BiTree T){

    if(T!=NULL){

        printf("%c",T->data);        //访问根节点

        PreOrder(T->lchild);         //递归遍历左子树

        PreOrder(T->rchild);         //递归遍历右子树

    }

}

非递归实现：在实现过程中利用了栈的思想

void PreOrder(BiTree b){

    InitStack(s);

    BiTree p=b;                        //工作指针p

    while(p||!IsEmpty(s)){

        while(p){

            printf("%c",p->data);

            Push(s,p);                 //进栈

            p=p->lchild;

        }

        if(!IsEmpty(s)){

            p=P0p(s);

            p=p->rchild;

        }

    }

}

②中序遍历：a.中序遍历左子树；b.访问根节点；c.中序遍历右子树。

递归实现：

void InOrder(BiTree T){

    if(T!=NULL){

        InOrder(T->lchild);          //递归遍历左子树

        printf("%c",T->data);        //访问根节点

        InOrder(T->rchild);          //递归遍历右子树

    }

}

非递归实现：

void InOrder(BiTree b){

    InitStack(s);

    BiTree p=b;

    while(p||!IsEmpty(s)){

        while(p){

            Push(s,p);

            p=p->lchild;

        }

        p=Pop(s);

        printf("%c",p->data);

        p=p->rchild;

    }

}

③后序遍历：a.后序遍历左子树；b.后序遍历右子树；c.访问根节点。

递归实现：

void PostOrder(BiTree T){

    if(T!=NULL){

        PostOrder(T->lchild);        //递归遍历左子树

        PostOrder(T->rchild);        //递归遍历右子树

        printf("%c",T->data);        //访问根节点

    }

}

非递归实现：

void PostOrder(BiTree b){

    InitStack(s);

    BiTree p=b,r=NULL;                        //工作指针p，辅助指针r

    while(p||!IsEmpty(s)){                    //从根节点到最左下角的左子树都入栈

        if(p){

            Push(s,p);

            p=p->lchild;

        }

        else{

            GetTop(s,p);                      //取栈顶，不是出栈

            if(p->rchild&&p->rchild!=r)       //如果栈顶存在右子树且未被访问过，就去访问

                p=p->rchild;

            else{                             //不存在右子树或者被访问过，则出栈

                Pop(s,p);

                printf("%c",p->data);

                r=p;

                p=NULL;

            }

        }

    }

}

④层序遍历：从上向下逐层遍历，在同一层中，从左到右对结点逐个访问。

层序遍历没有递归实现，只有非递归实现：其采用了队列的思想

void LevelOrder(BiTree b){

    InitQueue(Q);

    BiTree p;

    EnQueue(Q,b);                      //根结点入队

    while(!IsEmpty(Q)){                //队列不空循环

        DeQueue(Q,p)                   //队头元素出队

        printf("%c",p->data);

        if(p->lchild!=NULL)

            EnQueue(Q,p->lchild);

        if(p->rchild!=NULL)

            EnQueue(Q,p->rchild);

    }

}

如何将一棵树转化成二叉树：①将同一结点的各个孩子用线串起来；②将每个结点的子树分支，从左往右，除了第一个以外全部删除。

将二叉树转化成树：将二叉树从上到下分层，并调节成水平方向，之后是正向转化的逆过程。

一个重要结论：n个结点的二叉链表，每一个结点都有指向左右孩子的结点指针，所以一共有2n个指针，而n个结点的二叉树一共有n-1条分支，也就是存在2n-(n-1)=n+1个空指针。

线索二叉树：指向前驱和后继的指针称为线索，加上线索的二叉链表就称为线索链表，相应的二叉树就称为线索二叉树。对二叉树以某种次序遍历使其变成线索二叉树的过程叫作线索化。

下面我们以中序遍历作为例子，实现线索二叉树，并对其遍历：

线索二叉树的实现：

typedef struct ThreadTNode{

    ELemType data;

    struct ThreadTNode *lchild,*rchild;

    int ltag,rtag;            //tag=0指向孩子，tag=1指向前驱或者后继

}ThreadTNode,*ThreadTree;

void InThread(ThreadTree &p,ThreadTree &pre){

    //pre指向中序遍历时上一个刚刚访问过的结点，初值为NULL

    if(p){

        InThread(p->lchild,pre);

        if(p->lchild==NULL){

            p->lchild=pre;

            p->ltag=;

        }

        if(pre!=NULL&&pre->rchild==NULL){

            pre->rchild=p;

            pre->rtag=;

        }

        pre=p;

        InThread(p->rchild,pre);

    }

}

对线索二叉树进行中序遍历：

void InOrderTraverse(ThreadTree T){

    ThreadTree p=T;

    while(p){

        while(p->ltag==) p=p->lchild;

        printf("%c",p->data);

        while(p->ltag==&&p->rchild){

            p=p->rchild;

            printf("%c",p->data);

        }

        p->rchild;

    }

}

哈夫曼树中相关概念：

权：树中结点相关的数值；

路径长度：从树中某个结点到另一个结点之间的分支数目（经过的边数）；

带权路径长度：从树的根结点到任意结点的路径长度与该结点权值的乘积；

树的带权路径长度：树中所有结点带权路径长度的和。

哈夫曼树的定义：含有n个带权叶子结点的二叉树中，其中带权路径长度最小的二叉树，也称为最优二叉树。

巴特西

C语言数据结构基础学习笔记——树

最新文章

热门文章