数据结构笔记归档2

Giesen

2021-10-23

队列

1.队列的基本概念

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

1.1.队列的定义

队列也是一种特殊的线性表，插入操作在一端进行，称为队头，删除操作在另一端进行，称为队尾。

队列就跟生活中的排队类似，不允许插队，先排的人可以先得到服务。

1.2.队列的特征

先进先出（FIFO）

1.3.队列的基本运算

初始化队列
入队
出队
取队头的元素
判断队列是否为空

2.队列的存储结构

2.1.顺序存储结构

#define QueueSize 100

typedef char ElemType;

typedef struct  
{    
    ElemType data[QueueSize];    /*保存队中元素*/
    int front,rear;                /*队头和队尾指针*/
} SqQueue;

2.2.链式存储结构

typedef char ElemType;

typedef struct QNode 
{
    ElemType data;
    struct QNode *next;
} QType;                /*链队中结点的类型*/

typedef struct qptr        
{
    QType *front,*rear;
} LinkQueue;            /*链队类型*/

3.顺序队基本运算

3.1.顺序队列的定义

#include <stdio.h>
#define QueueSize 100

typedef char ElemType;

typedef struct  
{    
    ElemType data[QueueSize];    /*保存队中元素*/
    int front,rear;                /*队头和队尾指针*/
} SqQueue;

3.2.初始化队列

void InitQueue(SqQueue &qu)        /*qu为引用型参数*/
{
       qu.rear=qu.front=0;           /*指针初始化*/
}

3.3.入队运算

int EnQueue(SqQueue &qu,ElemType x)    /*入队运算,qu为引用型参数*/
{
    if ((qu.rear+1)%QueueSize==qu.front)    /*队满*/
        return 0;
    qu.rear=(qu.rear+1)%QueueSize;      /*队尾指针进1*/
    qu.data[qu.rear]=x;
    return 1;
}

3.4.出队运算

int DeQueue(SqQueue &qu,ElemType &x)    /*出队运算,qu和x为引用型参数*/
{
    if (qu.rear==qu.front)
        return 0;
    qu.front=(qu.front+1)%QueueSize;    /*队头指针进1*/
    x=qu.data[qu.front];
    return 1;
}

3.5.取队头元素运算

int GetHead(SqQueue qu,ElemType &x)        /*取队头元素运算,x为引用型参数*/
{
    if (qu.rear==qu.front)        /*队空*/
        return 0;
    x=qu.data[(qu.front+1)%QueueSize];
    return 1;
}

3.6.判断队空运算

int QueueEmpty(SqQueue qu)        /*判断队空运算*/
{
    if (qu.rear==qu.front)        /*队空*/
        return 1;
    else
        return 0;
}

3.7.main

void main()
{
    SqQueue qu;
    ElemType e;
    InitQueue(qu);
    printf("队%s\n",(QueueEmpty(qu)==1?"空":"不空"));
    printf("a进队\n");EnQueue(qu,'a');
    printf("b进队\n");EnQueue(qu,'b');
    printf("c进队\n");EnQueue(qu,'c');
    printf("d进队\n");EnQueue(qu,'d');
    printf("队%s\n",(QueueEmpty(qu)==1?"空":"不空"));
    GetHead(qu,e);
    printf("队头元素:%c\n",e);
    printf("出队次序:");
    while (!QueueEmpty(qu))
    {
        DeQueue(qu,e);
        printf("%c ",e);
    }
    printf("\n");
}

4.链队基本运算

4.1.链式队列的定义

#include <stdio.h>
#include <malloc.h>

typedef char ElemType;

typedef struct QNode 
{
    ElemType data;
    struct QNode *next;
} QType;                /*链队中结点的类型*/

typedef struct qptr        
{
    QType *front,*rear;
} LinkQueue;            /*链队类型*/

4.2.初始化队列

void InitQueue(LinkQueue *&lq)            /*lq为引用型参数*/
{    
    lq=(LinkQueue *)malloc(sizeof(LinkQueue));
    lq->rear=lq->front=NULL;             /*初始情况*/
}

4.3.入队运算

void EnQueue(LinkQueue *&lq,ElemType x)    /*入队运算,lq为引用型参数*/
{
    QType *s;
    s=(QType *)malloc(sizeof(QType));      /*创建新结点，插入到链队的末尾*/
    s->data=x;s->next=NULL;
    if (lq->front==NULL && lq->rear==NULL)     /*空队*/
        lq->rear=lq->front=s;
    else 
    {
        lq->rear->next=s;
        lq->rear=s;
    }
}

4.4.出队运算

int DeQueue(LinkQueue *&lq,ElemType &x)     /*出队运算,lq和x均为引用型参数*/
{
    QType *p;
    if (lq->front==NULL && lq->rear==NULL)  /*空队*/
        return 0;
    p=lq->front;
    x=p->data;
    if (lq->rear==lq->front)  /*若原队列中只有一个结点,删除后队列变空*/
        lq->rear=lq->front=NULL;
    else
        lq->front=lq->front->next;
    free(p);
    return 1;
}

4.5.取队头元素运算

int GetHead(LinkQueue *lq,ElemType &x)     /*取队头元素运算,x为引用型参数*/
{
    if (lq->front==NULL && lq->rear==NULL)    /*队空*/
        return 0;
    x=lq->front->data;
    return 1;
}

4.6.判断队空运算

int QueueEmpty(LinkQueue *lq)    /*判断队空运算*/
{
    if (lq->front==NULL && lq->rear==NULL)
        return 1;
    else
        return 0;
}

4.7.main

void main()
{
    LinkQueue *lq;
    ElemType e;
    InitQueue(lq);
    printf("队%s\n",(QueueEmpty(lq)==1?"空":"不空"));
    printf("a进队\n");EnQueue(lq,'a');
    printf("b进队\n");EnQueue(lq,'b');
    printf("c进队\n");EnQueue(lq,'c');
    printf("d进队\n");EnQueue(lq,'d');
    printf("队%s\n",(QueueEmpty(lq)==1?"空":"不空"));
    GetHead(lq,e);
    printf("队头元素:%c\n",e);
    printf("出队次序:");
    while (!QueueEmpty(lq))
    {
        DeQueue(lq,e);
        printf("%c ",e);
    }
    printf("\n");
}

5.队列的基本运算(By-Go)

// Package queue creates a ItemQueue data structure for the Item type
package queue

import (
    "sync"
)

// Item the type of the queue
type Item interface{}

// ItemQueue the queue of Items
type ItemQueue struct {
    items []Item
    lock  sync.RWMutex
}

// New creates a new ItemQueue
func (s *ItemQueue) New() *ItemQueue {
    s.lock.Lock()
    s.items = []Item{}
    s.lock.Unlock()
    return s
}

// Enqueue adds an Item to the end of the queue
func (s *ItemQueue) Enqueue(t Item) {
    s.lock.Lock()
    s.items = append(s.items, t)
    s.lock.Unlock()
}

// Dequeue removes an Item from the start of the queue
func (s *ItemQueue) Dequeue() *Item {
    s.lock.Lock()
    item := s.items[0]
    s.items = s.items[1:len(s.items)]
    s.lock.Unlock()
    return &item
}

// Front returns the item next in the queue, without removing it
func (s *ItemQueue) Front() *Item {
    s.lock.RLock()
    item := s.items[0]
    s.lock.RUnlock()
    return &item
}

// IsEmpty returns true if the queue is empty
func (s *ItemQueue) IsEmpty() bool {
    s.lock.RLock()
    defer s.lock.RUnlock()
    return len(s.items) == 0
}

// Size returns the number of Items in the queue
func (s *ItemQueue) Size() int {
    s.lock.RLock()
    defer s.lock.RUnlock()
    return len(s.items)
}

6.看病排队问题

#include <stdio.h>
#include <malloc.h>
#include <string.h>

typedef struct QNode 
{
    char data[10];
    struct QNode *next;
} QType;        /*链队结点类型*/

typedef struct 
{
    QType *front,*rear;
} LinkQueue;    /*链队类型*/

void SeeDoctor()
{
    int sel,flag=1;
    LinkQueue *lq;
    QType *s;
    char name[10];
    lq=(LinkQueue *)malloc(sizeof(LinkQueue));
    lq->front=(QType *)malloc(sizeof(QType));
    lq->front->next=NULL;
    lq->rear=lq->front;
    while (flag==1)     /*未下班时循环执行*/
    {
        printf("1:排队 2:看医生 3:查看排队 0:下班  请选择:");
        scanf("%d",&sel); 
        switch(sel) 
        {
        case 0:
            if (lq->front!=lq->rear)     /*队不空*/
                    printf("  >>请排队的患者明天就医\n");
            flag=0;
            break;
        case 1:
            printf("  >>输入患者姓名:");scanf("%s",name);
            s=(QType *)malloc(sizeof(QType));
            strcpy(s->data,name);s->next=NULL;
            lq->rear->next=s;lq->rear=s;
            break;
           case 2:    
            if (lq->front==lq->rear)    /*队空*/
                printf("  >>没有排队的患者\n");
            else 
            {
                s=lq->front->next;
                if (lq->rear==s)
                    lq->rear=lq->front;
                printf("  >>患者%s看医生\n",s->data);
                lq->front->next=s->next;
                free(s);
            }
            break;
           case 3:
            if (lq->front==lq->rear)    /*队空*/
                printf("  >>没有排列的患者\n");
            else 
            {    
                s=lq->front->next;
                printf("  >>排队患者:");
                while (s!=NULL) 
                {      
                    printf("%s ",s->data);
                    s=s->next;
                }
                printf("\n");
            }
            break;
        }
    }
}

void main()
{
    SeeDoctor();
}

串和数组

1.串的基本概念

字符串在存储上类似字符数组，所以它每一位的单个元素都是可以提取的，如s=“abcdefghij”，则s[1]=“b”，s[9]=”j”，这可以给我们提供很多方便，如高精度运算时每一位都可以转化为数字存入数组。

1.1.字符串的定义

字符串的由零个或多个的字符组成的有限序列，一般表示为”a1a2…an”。

1.2.字符串的特征

串中字符的个数称为串的长度
任意连续的字符组成的子序列称为该串的子串
子串的位置为子串第一个字符在原串中的位置

1.3.字符串的基本运算

串的赋值
串的复制
求串的长度
判断两个串是否相等
串的拼接
求子串
查找子串的位置
插入子串
删除子串
替换子串
输出串

2.字符串的存储结构

2.1.顺序存储结构

#define MaxSize 100  /*最多字符个数*/

typedef struct
{    
    char ch[MaxSize];    /*存放串字符*/
       int len;            /*存放串的实际长度*/
} SqString;                /*顺序串类型*/

2.2.链式存储结构

typedef struct node
{    
    char data;            /*存放字符*/
    struct node *next;    /*指针域*/
} LinkString;

3.顺序串基本运算

3.1.顺序串的定义

#include <stdio.h>
#define MaxSize 100  /*最多字符个数*/

typedef struct
{    
    char ch[MaxSize];    /*存放串字符*/
       int len;            /*存放串的实际长度*/
} SqString;                /*顺序串类型*/

3.2.赋值运算

void Assign(SqString &s,char t[])    /*串赋值运算*/
{
    int i=0;
    while (t[i]!='\0')
    {
        s.ch[i]=t[i];
        i++;
    }
    s.len=i;
}

3.3.复制运算

void StrCopy(SqString &s,SqString t)    /*串复制运算*/
{
    int i;
    for (i=0;i<t.len;i++)
        s.ch[i]=t.ch[i];
    s.len=t.len;
}

3.4.求串长运算

int StrLength(SqString s)    /*求串长运算*/
{
    return(s.len);
}

3.5.判断串相等运算

int StrEqual(SqString s,SqString t)    /*判断串相等运算*/
{
    int i=0;
    if (s.len!=t.len)        /*串长不同时返回0*/
        return(0);
    else
    {
        for (i=0;i<s.len;i++)
            if (s.ch[i]!=t.ch[i]) /*有一个对应字符不同时返回0*/
                return(0);
        return(1);
    }
}

3.6.串连接运算

SqString Concat(SqString s,SqString t)    /*串连接运算*/
{
    SqString r;
    int i,j;
    for (i=0;i<s.len;i++)        /*将s复制到r*/
        r.ch[i]=s.ch[i];
    for (j=0;j<t.len;j++)        /*将t复制到r*/
        r.ch[s.len+j]=t.ch[j];
    r.len=i+j;
    return(r);                    /*返回r*/
}

3.7.求子串运算

SqString SubStr(SqString s,int i,int j)    /*求子串运算*/
{
    SqString t;
    int k;
    if (i<1 || i>s.len || j<1 || i+j>s.len+1)
        t.len=0;            /*参数错误时返回空串*/
    else
    {
        for (k=i-1;k<i+j;k++)
            t.ch[k-i+1]=s.ch[k];
        t.len=j;
    }
    return(t);
}

3.8.查找子串位置运算

int Index(SqString s,SqString t)    /*查找子串位置运算*/
{
    int i=0,j=0,k;                /*i和j分别扫描主串s和子串t*/
    while (i<s.len && j<t.len)
    {
        if (s.ch[i]==t.ch[j]) /*对应字符相同时,继续比较下一对字符*/
        {
            i++;j++;
        }
        else                /*否则,主子串指针回溯重新开始下一次匹配*/
        {
            i=i-j+1;j=0;
        }
    }
    if (j>=t.len)
        k=i-t.len+1;/*求出第一个字符的位置*/
    else
        k=-1;        /*置特殊值-1*/
    return(k);
}

3.9.子串插入运算

int InsStr(SqString &s,int i,SqString t)    /*子串插入运算*/
{
    int j;
    if (i>s.len+1)
        return(0);                    /*位置参数值错误*/
    else 
    {
        for (j=s.len;j>=i-1;j--)     /*将s.ch[i-1]-s.ch[s.len-1]*/
            s.ch[j+t.len]=s.ch[j];    /*后移t.len个位置*/
        for (j=0;j<t.len;j++)
            s.ch[i+j-1]=t.ch[j];
        s.len=s.len+t.len;             /*修改s串长度*/
        return(1);
    }
}

3.10.子串删除运算

int DelStr(SqString &s,int i,int j)    /*子串删除运算*/
{
    int k;
    if (i<1 || i>s.len || j<1 || i+j>s.len+1)
        return(0);        /*位置参数值错误*/
    else
    {
        for (k=i+j-1;k<s.len;k++)     /*将s的第i+j位置之后的字符前移j位*/
            s.ch[k-j]=s.ch[k];
        s.len=s.len-j;                /*修改s的长度*/
        return(1);
    }
}

3.11.子串替换运算

SqString RepStrAll(SqString s,SqString s1,SqString s2)    /*子串替换运算*/
{
    int i;
    i=Index(s,s1);
    while (i>=0)
    {
        DelStr(s,i,s1.len);    /*删除*/
        InsStr(s,i,s2);        /*插入*/
        i=Index(s,s1);
    }
    return(s);
}

3.12.输出串运算

void DispStr(SqString s)    /*输出串运算*/
{
    int i;
    for (i=0;i<s.len;i++)
        printf("%c",s.ch[i]);
    printf("\n");
}

3.13.main

void main()
{
    SqString s1,s2,s3,s4,s5,s6,s7;
    Assign(s1,"abcd");
    printf("s1:");DispStr(s1);
    printf("s1的长度:%d\n",StrLength(s1));
    printf("s1=>s2\n");
    StrCopy(s2,s1);
    printf("s2:");DispStr(s2);
    printf("s1和s2%s\n",(StrEqual(s1,s2)==1?"相同":"不相同"));
    Assign(s3,"12345678");
    printf("s3:");DispStr(s3);
    printf("s1和s3连接=>s4\n");
    s4=Concat(s1,s3);
    printf("s4:");DispStr(s4);
    printf("s3[2..5]=>s5\n");
    s5=SubStr(s3,2,4);
    printf("s5:");DispStr(s5);
    Assign(s6,"567");
    printf("s6:");DispStr(s6);
    printf("s6在s3中位置:%d\n",Index(s3,s6));
    printf("从s3中删除s3[3..6]字符\n");
    DelStr(s3,3,4);
    printf("s3:");DispStr(s3);
    printf("从s4中将s6替换成s1=>s7\n");
    s7=RepStrAll(s4,s6,s1);
    printf("s7:");DispStr(s7);
}

4.链串基本运算

4.1.链串的定义

#include <stdio.h>
#include <malloc.h>

typedef struct node
{    
    char data;            /*存放字符*/
    struct node *next;    /*指针域*/
} LinkString;

4.2.赋值运算

void Assign(LinkString *&s,char t[])
{
    int i=0;
    LinkString *q,*tc;
    s=(LinkString *)malloc(sizeof(LinkString)); /*建立头结点*/
    s->next=NULL;
    tc=s;                    /*tc指向s串的尾结点*/
    while (t[i]!='\0')
    {
        q=(LinkString *)malloc(sizeof(LinkString));
        q->data=t[i];
        tc->next=q;tc=q;
        i++;
    }
    tc->next=NULL;        /*终端结点的next置NULL*/
}

4.3.复制运算

void StrCopy(LinkString *&s,LinkString *t)    /*t=>s*/
{
    LinkString *p=t->next,*q,*tc;
    s=(LinkString *)malloc(sizeof(LinkString)); /*建立头结点*/
    s->next=NULL;
    tc=s;                /*tc指向s串的尾结点*/
    while (p!=NULL)        /*复制t的所有结点*/
    {
        q=(LinkString *)malloc(sizeof(LinkString));
        q->data=p->data;
        tc->next=q;tc=q;
        p=p->next;
    }
    tc->next=NULL;        /*终端结点的next置NULL*/
}

4.4.求串长运算

int StrLength(LinkString *s)
{
    int n=0;
    LinkString *p=s->next;
    while (p!=NULL)        /*扫描串s的所有结点*/
    {
        n++;p=p->next;
    }
    return(n);
}

4.5.判断串相等运算

int StrEqual(LinkString *s,LinkString *t)
{
    LinkString *p=s->next,*q=t->next;
    while (p!=NULL && q!=NULL)    /*比较两串的当前结点*/
    {
        if (p->data!=q->data)    /*data域不等时返回0*/
            return(0);
        p=p->next;q=q->next;
    }
    if (p!=NULL || q!=NULL)        /*两串长度不等时返回0*/
        return(0);
    return(1);
}

4.6.串连接运算

LinkString *Concat(LinkString *s,LinkString *t)
{
    LinkString *p=s->next,*q,*tc,*str;
    str=(LinkString *)malloc(sizeof(LinkString));  /*建立头结点*/
    str->next=NULL;
    tc=str;                /*tc总是指向新链表的尾结点*/
    while (p!=NULL)        /*将s串复制给str*/
    {
        q=(LinkString *)malloc(sizeof(LinkString));
        q->data=p->data;
        tc->next=q;tc=q;
        p=p->next;
    }
    p=t->next;
    while (p!=NULL)        /*将t串复制给str*/
    {
        q=(LinkString *)malloc(sizeof(LinkString));
        q->data=p->data;
        tc->next=q;tc=q;
        p=p->next;
    }
    tc->next=NULL;
    return(str);
}

4.7.求子串运算

LinkString *SubStr(LinkString *s,int i,int j)
{
    int k=1;
    LinkString *p=s->next,*q,*tc,*str;
    str=(LinkString *)malloc(sizeof(LinkString));  /*建立头结点*/
    str->next=NULL;
    tc=str;                            /*tc总是指向新链表的尾结点*/
    while (k<i && p!=NULL)
    {
        p=p->next;k++;
    }
    if (p!=NULL)
    {
        k=1;
        while (k<=j && p!=NULL)        /*复制j个结点*/
        {
            q=(LinkString *)malloc(sizeof(LinkString));
            q->data=p->data;
            tc->next=q;tc=q;
            p=p->next;
            k++;
        }
        tc->next=NULL;
    }
    return(str);
}

4.8.查找子串位置运算

int Index(LinkString *s,LinkString *t)
{
    LinkString *p=s->next,*p1,*q,*q1;
    int i=0;
    while (p!=NULL)           /*循环扫描s的每个结点*/
    {
        q=t->next;            /*子串总是从第一个字符开始比较*/
        if (p->data==q->data)/*判定两串当前字符相等*/
        {            /*若首字符相同,则判定s其后字符是否与t的依次相同*/
            p1=p->next;q1=q->next;
            while (p1!=NULL && q1!=NULL && p1->data==q1->data)
            {
                p1=p1->next;
                q1=q1->next;
            }
            if (q1==NULL)    /*若都相同,则返回相同的子串的起始位置*/
                return(i);
        }
        p=p->next;i++;
    }
    return(-1);        /*若不是子串,返回-1*/
}

4.9.子串插入运算

int InsStr(LinkString *&s,int i,LinkString *t)
{
    int k;
    LinkString *q=s->next,*p,*str;
    StrCopy(str,t);        /*将t复制到str*/
    p=str;str=str->next;
    free(p);            /*删除str的头结点*/
    for (k=1;k<i;k++)    /*在s中找到第i-1个结点,由p指向它,q指向下一个结点*/
    {
        if (q==NULL)    /*位置参数i错误*/
            return(0);
        p=q;
        q=q->next;
    }
    p->next=str;        /*将str链表链接到*p之后*/
    while (str->next!=NULL)    /*由str指向尾结点*/
        str=str->next;        
    str->next=q;        /*将*q链接到*str之后*/
    return(1);
}

4.10.子串删除运算

int DelStr(LinkString *&s,int i,int j)
{
    int k;
    LinkString *q=s->next,*p,*t;
    for (k=1;k<i;k++)    /*在s中找到第i-1个结点,由p指向它,q指向下一个结点*/
    {
        if (q==NULL)        /*位置参数i错误*/
            return(0);
        p=q;
        q=q->next;
    }
    for (k=1;k<=j;k++)    /*删除*p之后的j个结点,并由q指向下一个结点*/
    {
        if (q==NULL)    /*长度参数j错误*/
            return(0);
        t=q;
        q=q->next;
        free(t);
    }
    p->next=q;
    return(1);
}

4.11.子串替换运算

LinkString *RepStrAll(LinkString *s,LinkString *s1,LinkString *s2)
{
    int i;
    i=Index(s,s1);
    while (i>=0)
    {
        DelStr(s,i+1,StrLength(s1));    /*删除串s1*/
        InsStr(s,i+1,s2);                /*插入串s2*/
        i=Index(s,s1);
    }
    return(s);
}

4.12.输出串运算

void DispStr(LinkString *s)
{
    LinkString *p=s->next;
    while (p!=NULL)
    {
        printf("%c",p->data);
        p=p->next;
    }
    printf("\n");
}

4.13.main

void main()
{
    LinkString *s1,*s2,*s3,*s4,*s5,*s6,*s7;
    Assign(s1,"abcd");
    printf("s1:");DispStr(s1);
    printf("s1的长度:%d\n",StrLength(s1));
    printf("s1=>s2\n");
    StrCopy(s2,s1);
    printf("s2:");DispStr(s2);
    printf("s1和s2%s\n",(StrEqual(s1,s2)==1?"相同":"不相同"));
    Assign(s3,"12345678");
    printf("s3:");DispStr(s3);
    printf("s1和s3连接=>s4\n");
    s4=Concat(s1,s3);
    printf("s4:");DispStr(s4);
    printf("s3[2..5]=>s5\n");
    s5=SubStr(s3,2,4);
    printf("s5:");DispStr(s5);
    Assign(s6,"567");
    printf("s6:");DispStr(s6);
    printf("s6在s3中位置:%d\n",Index(s3,s6));
    printf("从s3中删除s3[3..6]字符\n");
    DelStr(s3,3,4);
    printf("s3:");DispStr(s3);
    printf("从s4中将s6替换成s1=>s7\n");
    s7=RepStrAll(s4,s6,s1);
    printf("s7:");DispStr(s7);
}

二叉树

1.二叉树的基本概念

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。

1.1.二叉树的定义

树形结构是一种非线性结构，二叉树是度为2，即子结点的个数最多为2的有序树（左右子树是有次序的）。最重要，应用最广泛的一种树。

1.2.完全二叉树

在一个二叉树中，除了最后一层外，其余的其他层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干个结点，则该树称为完全二叉树。

满二叉树是一种特殊的完全二叉树，即所有的层的结点都是满的。

1.3.树的基本术语

结点的度：该节点的后继节点的个数
树的度：所有节点的度的最大值
分支结点
叶子结点
孩子结点
双亲结点
子孙结点
祖先结点
兄弟结点
结点层数
树的深度（高度）：树中结点的最大的层数
有序树：左右子树是有次序的
无序树：左右子树是无次序的
森林：不同树的集合

1.4.二叉树的性质

二叉树上叶子节点的个数等于度为2的结点的个数加1
二叉树上第i层上至多有2^(i-1)个结点（i>1）
深度为h的二叉树至多有2^h-1个结点

1.5.二叉树的基本运算

创建二叉树
求二叉树的高度
求二叉树结点的个数
求二叉树叶子结点的个数
用括号表示法输出二叉树
用凹入表示法输出二叉树

2.二叉树的存储结构

2.1.顺序存储结构

1	typedef ElemType SqBinTree[MaxSize]

2.2.链式存储结构

#define MaxSize 100
#define MaxWidth 40

typedef char ElemType;

typedef struct tnode
{
    ElemType data;
    struct tnode *lchild,*rchild;
} BTNode;

3.二叉树基本运算

3.1.二叉树的定义

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
#define MaxWidth 40

typedef char ElemType;

typedef struct tnode
{
    ElemType data;
    struct tnode *lchild,*rchild;
} BTNode;

3.2.由str创建二叉链

void CreateBTree(BTNode * &bt,char *str)    /*由str创建二叉链bt*/
{
    BTNode *St[MaxSize],*p=NULL;
    int top=-1,k,j=0;  
    char ch;
    bt=NULL;            /*建立的二叉树初始时为空*/
    ch=str[j];
    while (ch!='\0')      /*str未扫描完时循环*/
    {
              switch(ch) 
        {
        case '(':top++;St[top]=p;k=1; break;    /*为左孩子结点*/
        case ')':top--;break;
        case ',':k=2; break;                    /*为孩子结点右结点*/
        default:p=(BTNode *)malloc(sizeof(BTNode));
                p->data=ch;p->lchild=p->rchild=NULL;
                if (bt==NULL)                   /**p为二叉树的根结点*/
                    bt=p;
                else                              /*已建立二叉树根结点*/
                {    switch(k) 
                    {
                    case 1:St[top]->lchild=p;break;
                    case 2:St[top]->rchild=p;break;
                    }
                }
        }
        j++;
        ch=str[j];
    }
}

3.3.求二叉树高度

int BTHeight(BTNode *bt)    /*求二叉树高度*/
{
       int lchilddep,rchilddep;
       if (bt==NULL) return(0);             /*空树的高度为0*/
       else  
    {    lchilddep=BTHeight(bt->lchild);    /*求左子树的高度为lchilddep*/
          rchilddep=BTHeight(bt->rchild);    /*求右子树的高度为rchilddep*/
        return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);
       }
}

3.4.求二叉树的结点个数

int NodeCount(BTNode *bt)    /*求二叉树bt的结点个数*/
{
    int num1,num2;
        if (bt==NULL)    /*空树结点个数为0*/ 
            return 0;
        else
        {    num1=NodeCount(bt->lchild);    /*求出左子树的结点数*/
            num2=NodeCount(bt->rchild);    /*求出右子树的结点数*/
            return (num1+num2+1);
    }
}

3.5.求二叉树的叶子结点个数

int LeafCount(BTNode *bt)    /*求二叉树bt的叶子结点个数*/
{
    int num1,num2;
        if (bt==NULL)    /*空树叶子结点个数为0*/ 
            return 0;
        else if (bt->lchild==NULL && bt->rchild==NULL) 
            return 1;    /*若为叶子结点返回1*/ 
        else
        {    num1=LeafCount(bt->lchild);    /*求出左子树的叶子结点数*/
            num2=LeafCount(bt->rchild);    /*求出右子树的叶子结点数*/
            return (num1+num2);
    }
}

3.6.以括号表示法输出二叉树

void DispBTree(BTNode *bt)    /*以括号表示法输出二叉树*/
{
    if (bt!=NULL)
    {    
        printf("%c",bt->data);
        if (bt->lchild!=NULL || bt->rchild!=NULL)
        {    
            printf("(");
            DispBTree(bt->lchild);        /*递归处理左子树*/
            if (bt->rchild!=NULL) 
                printf(",");
            DispBTree(bt->rchild);        /*递归处理右子树*/
            printf(")");
        }
    }
}

3.7.以凹入表示法输出一棵二叉树

void DispBTree1(BTNode *bt)  /*以凹入表示法输出一棵二叉树*/
{
    BTNode *St[MaxSize],*p;
    int Level[MaxSize][2],top=-1,n,i,width=4;
    char type;        /*取值L表示为左结点,R表示为右结点,B表示为根结点*/
    if (bt!=NULL)
    {    
        top++;
        St[top]=bt;                        /*根结点入栈*/
        Level[top][0]=width;
        Level[top][1]=2;                /*2表示是根*/
        while (top>-1)
        {    
            p=St[top];                    /*退栈并凹入显示该结点值*/
            n=Level[top][0];
            switch(Level[top][1])
            {
            case 0:type='L';break;        /*左结点之后输出(L)*/
            case 1:type='R';break;        /*右结点之后输出(R)*/
            case 2:type='B';break;        /*根结点之后前输出(B)*/
            }
            for (i=1;i<=n;i++)            /*其中n为显示场宽,字符以右对齐显示*/
                printf(" ");
            printf("%c(%c)",p->data,type);
            for (i=n+1;i<=MaxWidth;i+=2)
                printf("━");
            printf("\n");
            top--;
            if (p->rchild!=NULL)
            {                            /*将右子树根结点入栈*/
                top++;
                St[top]=p->rchild;
                Level[top][0]=n+width;    /*场宽增width,即缩width格后再输出*/
                Level[top][1]=1;        /*1表示是右子树*/
            }
            if (p->lchild!=NULL)
            {                            /*将左子树根结点入栈*/
                top++;
                St[top]=p->lchild;
                Level[top][0]=n+width;  /*显示场宽增width*/
                Level[top][1]=0;        /*0表示是左子树*/
            }
        }
    }
}

3.8.main

void main()
{
    BTNode *bt;
    CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");    /*构造图5.10(a)所示的二叉树*/
    printf("二叉树bt:");DispBTree(bt);printf("\n");
    printf("bt的高度:%d\n",BTHeight(bt));
    printf("bt的结点数:%d\n",NodeCount(bt));
    printf("bt的叶子结点数:%d\n",LeafCount(bt));
    printf("bt凹入表示:\n");DispBTree1(bt);printf("\n");
}

4.二叉树基本运算(By-Go)

// Package binarysearchtree creates a ItemBinarySearchTree data structure for the Item type
package binarysearchtree

import (
    "fmt"
    "sync"
)

// Item the type of the binary search tree
type Item interface{}

// Node a single node that composes the tree
type Node struct {
    key   int
    value Item
    left  *Node //left
    right *Node //right
}

// ItemBinarySearchTree the binary search tree of Items
type ItemBinarySearchTree struct {
    root *Node
    lock sync.RWMutex
}

// Insert inserts the Item t in the tree
func (bst *ItemBinarySearchTree) Insert(key int, value Item) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    n := &Node{key, value, nil, nil}
    if bst.root == nil {
        bst.root = n
    } else {
        insertNode(bst.root, n)
    }
}

// internal function to find the correct place for a node in a tree
func insertNode(node, newNode *Node) {
    if newNode.key < node.key {
        if node.left == nil {
            node.left = newNode
        } else {
            insertNode(node.left, newNode)
        }
    } else {
        if node.right == nil {
            node.right = newNode
        } else {
            insertNode(node.right, newNode)
        }
    }
}

// InOrderTraverse visits all nodes with in-order traversing
func (bst *ItemBinarySearchTree) InOrderTraverse(f func(Item)) {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    inOrderTraverse(bst.root, f)
}

// internal recursive function to traverse in order
func inOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        inOrderTraverse(n.left, f)
        f(n.value)
        inOrderTraverse(n.right, f)
    }
}

// PreOrderTraverse visits all nodes with pre-order traversing
func (bst *ItemBinarySearchTree) PreOrderTraverse(f func(Item)) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    preOrderTraverse(bst.root, f)
}

// internal recursive function to traverse pre order
func preOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        f(n.value)
        preOrderTraverse(n.left, f)
        preOrderTraverse(n.right, f)
    }
}

// PostOrderTraverse visits all nodes with post-order traversing
func (bst *ItemBinarySearchTree) PostOrderTraverse(f func(Item)) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    postOrderTraverse(bst.root, f)
}

// internal recursive function to traverse post order
func postOrderTraverse(n *Node, f func(Item)) {
    if n != nil {
        postOrderTraverse(n.left, f)
        postOrderTraverse(n.right, f)
        f(n.value)
    }
}

// Min returns the Item with min value stored in the tree
func (bst *ItemBinarySearchTree) Min() *Item {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    n := bst.root
    if n == nil {
        return nil
    }
    for {
        if n.left == nil {
            return &n.value
        }
        n = n.left
    }
}

// Max returns the Item with max value stored in the tree
func (bst *ItemBinarySearchTree) Max() *Item {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    n := bst.root
    if n == nil {
        return nil
    }
    for {
        if n.right == nil {
            return &n.value
        }
        n = n.right
    }
}

// Search returns true if the Item t exists in the tree
func (bst *ItemBinarySearchTree) Search(key int) bool {
    bst.lock.RLock()
    defer bst.lock.RUnlock()
    return search(bst.root, key)
}

// internal recursive function to search an item in the tree
func search(n *Node, key int) bool {
    if n == nil {
        return false
    }
    if key < n.key {
        return search(n.left, key)
    }
    if key > n.key {
        return search(n.right, key)
    }
    return true
}

// Remove removes the Item with key `key` from the tree
func (bst *ItemBinarySearchTree) Remove(key int) {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    remove(bst.root, key)
}

// internal recursive function to remove an item
func remove(node *Node, key int) *Node {
    if node == nil {
        return nil
    }
    if key < node.key {
        node.left = remove(node.left, key)
        return node
    }
    if key > node.key {
        node.right = remove(node.right, key)
        return node
    }
    // key == node.key
    if node.left == nil && node.right == nil {
        node = nil
        return nil
    }
    if node.left == nil {
        node = node.right
        return node
    }
    if node.right == nil {
        node = node.left
        return node
    }
    leftmostrightside := node.right
    for {
        //find smallest value on the right side
        if leftmostrightside != nil && leftmostrightside.left != nil {
            leftmostrightside = leftmostrightside.left
        } else {
            break
        }
    }
    node.key, node.value = leftmostrightside.key, leftmostrightside.value
    node.right = remove(node.right, node.key)
    return node
}

// String prints a visual representation of the tree
func (bst *ItemBinarySearchTree) String() {
    bst.lock.Lock()
    defer bst.lock.Unlock()
    fmt.Println("------------------------------------------------")
    stringify(bst.root, 0)
    fmt.Println("------------------------------------------------")
}

// internal recursive function to print a tree
func stringify(n *Node, level int) {
    if n != nil {
        format := ""
        for i := 0; i < level; i++ {
            format += "       "
        }
        format += "---[ "
        level++
        stringify(n.left, level)
        fmt.Printf(format+"%d\n", n.key)
        stringify(n.right, level)
    }
}

5.二叉树4种遍历算法

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
#define MaxWidth 40

typedef char ElemType;

typedef struct tnode
{
    ElemType data;
    struct tnode *lchild,*rchild;
} BTNode;

void CreateBTree(BTNode * &bt,char *str)    /*由str创建二叉链bt*/
{
    BTNode *St[MaxSize],*p=NULL;
    int top=-1,k,j=0;  
    char ch;
    bt=NULL;            /*建立的二叉树初始时为空*/
    ch=str[j];
    while (ch!='\0')      /*str未扫描完时循环*/
    {
              switch(ch) 
        {
        case '(':top++;St[top]=p;k=1; break;    /*为左孩子结点*/
        case ')':top--;break;
        case ',':k=2; break;                    /*为孩子结点右结点*/
        default:p=(BTNode *)malloc(sizeof(BTNode));
                p->data=ch;p->lchild=p->rchild=NULL;
                if (bt==NULL)                   /**p为二叉树的根结点*/
                    bt=p;
                else                              /*已建立二叉树根结点*/
                {    switch(k) 
                    {
                    case 1:St[top]->lchild=p;break;
                    case 2:St[top]->rchild=p;break;
                    }
                }
        }
        j++;
        ch=str[j];
    }
}

void DispBTree(BTNode *bt)    /*以括号表示法输出二叉树*/
{
    if (bt!=NULL)
    {    
        printf("%c",bt->data);
        if (bt->lchild!=NULL || bt->rchild!=NULL)
        {    
            printf("(");
            DispBTree(bt->lchild);        /*递归处理左子树*/
            if (bt->rchild!=NULL) 
                printf(",");
            DispBTree(bt->rchild);        /*递归处理右子树*/
            printf(")");
        }
    }
}

// 先序遍历序列
void PreOrder(BTNode *bt)
{
    if (bt!=NULL)
    {
        printf("%c ",bt->data);
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}

// 中序遍历序列
void InOrder(BTNode *bt)
{
    if (bt!=NULL)
    {    
        InOrder(bt->lchild);
        printf("%c ",bt->data);
        InOrder(bt->rchild);
    }
}

// 后序遍历序列
void PostOrder(BTNode *bt)
{
    if (bt!=NULL)
    {
        PostOrder(bt->lchild);
        PostOrder(bt->rchild);
        printf("%c ",bt->data);
    }
}

// 层次遍历序列
void LevelOrder(BTNode *b)
{
    BTNode *p;
    BTNode *qu[MaxSize];            /*定义环形队列,存放结点指针*/
    int front,rear;                    /*定义队头和队尾指针*/
    front=rear=-1;                    /*置队列为空队列*/
    rear++;
    qu[rear]=b;                        /*根结点指针进入队列*/
    while (front!=rear)                /*队列不为空*/
    {    front=(front+1)%MaxSize;
        p=qu[front];                /*队头出队列*/
        printf("%c ",p->data);        /*访问结点*/
        if (p->lchild!=NULL)        /*有左孩子时将其进队*/
        {    rear=(rear+1)%MaxSize;
            qu[rear]=p->lchild;
        }
        if (p->rchild!=NULL)        /*有右孩子时将其进队*/
        {    rear=(rear+1)%MaxSize;
            qu[rear]=p->rchild;
        }
    } 
}

void main()
{
    BTNode *bt;
    CreateBTree(bt,"A(B(D,E(G,H)),C(,F(I)))");    /*构造图5.10(a)所示的二叉树*/
    printf("二叉树bt:");DispBTree(bt);printf("\n");
    printf("先序遍历序列:");PreOrder(bt);printf("\n");
    printf("中序遍历序列:");InOrder(bt);printf("\n");
    printf("后序遍历序列:");PostOrder(bt);printf("\n");
    printf("层次遍历序列:");LevelOrder(bt);printf("\n");
}

6.哈夫曼树

#include <stdio.h>
#define N 50        /*叶子结点数*/
#define M 2*N-1        /*树中结点总数*/

typedef struct
{
    char data;        /*结点值*/
    double weight;    /*权重*/
    int parent;        /*双亲结点*/
    int lchild;        /*左孩子结点*/
    int rchild;        /*右孩子结点*/
} HTNode;

typedef struct
{
    char cd[N];        /*存放哈夫曼码*/
    int start;
} HCode;

void CreateHT(HTNode ht[],int n)
{
    int i,k,lnode,rnode;
    double min1,min2;
    for (i=0;i<2*n-1;i++)            /*所有结点的相关域置初值-1*/
        ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
    for (i=n;i<2*n-1;i++)            /*构造哈夫曼树*/
    {
        min1=min2=32767;            /*lnode和rnode为最小权重的两个结点位置*/
        lnode=rnode=-1;
        for (k=0;k<=i-1;k++)
            if (ht[k].parent==-1)    /*只在尚未构造二叉树的结点中查找*/
            {
                if (ht[k].weight<min1)
                {
                    min2=min1;rnode=lnode;
                    min1=ht[k].weight;lnode=k;
                }
                else if (ht[k].weight<min2)
                {
                    min2=ht[k].weight;rnode=k;
                }
            }
        ht[i].weight=ht[lnode].weight+ht[rnode].weight;
        ht[i].lchild=lnode;ht[i].rchild=rnode;
        ht[lnode].parent=i;
        ht[rnode].parent=i;
    }
}

void CreateHCode(HTNode ht[],HCode hcd[],int n)
{
    int i,f,c;
    HCode hc;
    for (i=0;i<n;i++)    /*根据哈夫曼树求哈夫曼编码*/
    {
        hc.start=n;c=i;
        f=ht[i].parent;
        while (f!=-1)    /*循序直到树根结点*/
        {
            if (ht[f].lchild==c)    /*处理左孩子结点*/
                hc.cd[hc.start--]='0';
            else                    /*处理右孩子结点*/
                hc.cd[hc.start--]='1';
            c=f;f=ht[f].parent;
        }
        hc.start++;        /*start指向哈夫曼编码最开始字符*/
        hcd[i]=hc;
    }
}

void DispHCode(HTNode ht[],HCode hcd[],int n)
{
    int i,k;
    double sum=0,m=0;
    int j;
    printf("输出哈夫曼编码:\n"); /*输出哈夫曼编码*/
    for (i=0;i<n;i++)
    {
        j=0;
        printf("   %c:",ht[i].data);
        for (k=hcd[i].start;k<=n;k++)
        {
            printf("%c",hcd[i].cd[k]);
            j++;
        }
        m+=ht[i].weight;
        sum+=ht[i].weight*j;
        printf("\n");
    }
}

void main()
{
    int n=5,i;        /*n表示初始字符串的个数*/
    char str[]={'a','b','c','d','e'};
    double fnum[]={4,2,1,7,3};
    HTNode ht[M];
    HCode hcd[N];
    for (i=0;i<n;i++)
    {
        ht[i].data=str[i];
        ht[i].weight=fnum[i];
    }
    printf("\n");
    CreateHT(ht,n);
    CreateHCode(ht,hcd,n);
    DispHCode(ht,hcd,n);
    printf("\n");
}