数据结构-树-白红宇

数据结构中的树

之前我们讲的都是一对一的线性结构，在实际应用上，还有许多一对多的情况需要我们去处理，所以这一篇我要讲一种一对多的数据结构——树。

树

对于A来说，它和B、C、D都有关系，对于B来说它和E、F都有关系，这就是“一对多”的关系

树的概念

结点：树中的每一个元素都是一个结点，如A、B、C。

父结点：对于B、C、D来说，A是它们的父结点。

子结点：对于A来说，B、C、D都是它的子结点。

根结点：如果一个结点没有父结点，那么个结点就是根结点。

兄弟结点：对于B、C、D来说它们是兄弟结点，对于E、F来说它们也是兄弟结点。

叶子结点：如果结点没有任何子结点，那么此结点为叶子结点。例如（K、L、F、G、M、I、J）

树的层次：从根开始定义，根为第一层，根的孩子（BCD）为第二层，（BCD）的孩子为第三层，以此类推。

结点的度：对于A来将，它的度是3（BCD），对于B来讲它的度是2（EF）。

满二叉树和完全二叉树

如果二叉树中除了叶子结点，每个结点的度都为2，那么此二叉树为满二叉树

如果二叉树中有一层结点的子树中不是从左到右分布那么它就是完全二叉树

图1和2都是二叉树，但是图2是完全二叉树，图一是满二叉树（二叉树中各个结点的度最多是2，可以是0，1，2）

二叉树的结点构成

Lchild 代表指向左孩子的指针域；data 为数据域；Rchild 代表指向右孩子的指针域。使用此种结点构建的二叉树称为“二叉链表”。

代码实现

#include 
    
     #define TElemType int//利用队列遍历二叉树//初始化队头和队尾指针开始时都为0int front=0,rear=0;typedef struct BiTNode{
        TElemType data;//数据域    struct BiTNode *lchild,*rchild;//定义左树指针域和右树指针域}BiTNode,*BiTree;复制代码

创建树

//前面学过指针的应该有基础了，这里我就不过多讲解了void CreateBiTree(BiTree *T){    *T=(BiTNode*)malloc(sizeof(BiTNode));    (*T)->data=1;    (*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));    (*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));       (*T)->lchild->data=2;    (*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));    (*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));    (*T)->lchild->rchild->data=5;    (*T)->lchild->rchild->lchild=NULL;    (*T)->lchild->rchild->rchild=NULL;       (*T)->rchild->data=3;    (*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));    (*T)->rchild->lchild->data=6;    (*T)->rchild->lchild->lchild=NULL;    (*T)->rchild->lchild->rchild=NULL;       (*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));    (*T)->rchild->rchild->data=7;    (*T)->rchild->rchild->lchild=NULL;    (*T)->rchild->rchild->rchild=NULL;       (*T)->lchild->lchild->data=4;    (*T)->lchild->lchild->lchild=NULL;    (*T)->lchild->lchild->rchild=NULL;}复制代码

使用队列来遍历树

void EnQueue(BiTree *a,BiTree node){    a[rear++]=node;}//出队函数BiTNode* DeQueue(BiTNode** a){
   //这里需要用二级指针（BiTNode）    return a[front++];}//输出函数void displayNode(BiTree node){    printf("%d ",node->data);}int main() {    BiTree tree;    //创建二叉树    CreateBiTree(&tree);    BiTNode * p;    //采用顺序队列，初始化创建队列数组    BiTree a[20];    //根结点入队    EnQueue(a, tree);    //当队头和队尾相等时，表示队列为空    while(front
    
     lchild!=NULL) {            EnQueue(a, p->lchild);//rear++        }        if (p->rchild!=NULL) {            EnQueue(a, p->rchild);//rear++        }    }    return 0;}复制代码

运行结果

1 2 3 4 5 6 7