数据结构（部分）-锐单电子商城

数据结构：

一、逻辑结构(与存储无关):

1)线性关系：

除头结点和尾结点外，其他节点只有一个直接前驱和直接后继点

头结点没有前驱，尾结点没有后继

2)非线性关系：

树形结构：一对多，除根节点和叶节点外，其他节点只有唯一的前驱，多个后继

根节点没有前驱，叶节点没有后继

图形结构:多对多，所有节点都可以有多个前驱和多个后继

二、存储结构(与存储有关):

1)顺序存储:依次存储在内存中

2)链式存储:分散存储在内存中

3）索引存储

4）散列存储（Hash）

三、操作：

增删改查数据

算法：

时间复杂性：指执行该算法所需的计算工作量（语句频率）

空间复杂性：指执行该算法所需的内存空间

线性表：顺序表示

顺序表：线性表的数据元素用一组地址连续存储单元依次存储，称为线性表顺序存储结构或顺序映像 （sequential mapping）。线性表中数据元素之间的逻辑关系可以通过物理位置相邻来随机访问表中的任何元素。

#define SIZE 100 typedef int data_t struct HEAD{ data_t data[SIZE]; int len; ///表尾指针:下标最后一个有效元素 }sqlist_t;  sqlist_creat(); //创建表格 sqlist_destory(); ///删除表格

优点：具有简单、运算方便等优点，特别是对于小线性表或长度固定的线性表，采用顺序存储结构的优势更加突出；

缺点：1、顺序存储插入和删除一个元素，必须移动较大的数据元素，以便对于较大的线性表，特别是当元素插入和删除非常频繁时，顺序存储非常不方便，效率低；

2.顺序存储空间容易满，溢出，程序访问容易出现问题。在顺序存储结构下，存储空间不便扩展；

3、顺序存储空间的分配问题，分为，分为空间不足溢出。对于大线性表，特别是元素变化频繁的大线性表，不应采用顺序存储空间，而应采用链式存储结构。

线性表:链式表示(有头和无头)

链表：线性表中的数据元素用任何存储单元存储，称为线性表链式存储结构。它的存储单元可以是连续的或不连续的。

在逻辑上呈线性关系，在内存上是散列存储

节点：数据与指针域(如果没有下一个节点，则存储下一个节点的地址NULL）

有头链表：

链表的倒置

void linklist_invert(node_t *head) { node_t *p = head->next; node_t *q = NULL; //将链表断开成两个链表，只有头，只有有效节点 head->next = NULL; ///遍历所有有效节点，用头插法插入只有头的链表 while (p != NULL) { q = p->next; //头插法：将p插入head后面 p->next = head->next; head->next = p; p = q; } }

链表的排序

void linklist_sort(node_t *head) { node_t *p = head->next; //第一个有效节点 node_t *q = NULL; //p下一个节点 node_t *t = NULL; ///之前的节点需要插入位置 node_t *r = NULL; ///要插入位置的节点 head->next = NULL;///断开链表两个链表 //遍历无序链表，在有序链表中找到每个节点的相应位置 while (p != NULL) { q = p->next; ///保存p的下一个节点 //从head开始在有序链表中找到插入位置的前节点t t = head;    
        r = t->next;
        //当插入位置r存在且p值大于r值时，则t，r都后移一个节点
        while (r != NULL && p->data > r->data)
        {
            t = r;
            r = t->next;
        }
        //把p插入t后面
        p->next = r;
        t->next = p;
        //再插入下一个节点
        p = q;
    }
}

单向循环链表（尾结点指向头结点）

1）保证最后一个节点的指针域指向头结点

2）遍历时结束标志为头结点

3）循环删除时，不要删除头结点

4）可以循环插入，删除

typedef int data_t;

typedef struct node{
    data_t data;   //数据域
    struct node *next; //指针域：指向下一个节点
}node_t;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linklist.h"

node_t *linklist_create()
{
    node_t *head = (node_t *)malloc(sizeof(node_t));
    if (NULL == head)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    memset(head, 0, sizeof(node_t));
    head->next = head;
    return head;
}

void linklist_destory(node_t *head)
{
    linklist_clear(head);
    free(head);
}

void linklist_clear(node_t *head)
{
    node_t *p = head->next;  //第一个有效节点
    node_t *q = NULL;
    while (p != head)  //判断有效节点是否存在
    {
        q = p->next;  //先把下一个节点保存
        free(p);  //销毁p
        p = q;    //把下一个节点赋给p
    }
    head->next = head;  //把头节点指针域head
}

int linklist_isFull(node_t *head)
{
    return 0;
}

int linklist_isEmpty(node_t *head)
{
    return (head == head->next) ? 1 : 0;
}

int linklist_length(node_t *head)
{
    int len = 0;
    node_t *p = head->next; //p指向第一个有效节点
    while (p != head)  //判断节点是否head
    {
        len++;    
        p = p->next;  //p向下一个节点偏移
    }
    return len;
}

int linklist_insert(node_t *head, int pos, data_t data)
{
    //1. 判断pos是否有效，无效则报错返回
    int len = linklist_length(head);
    if ((pos < 0) || (pos > len))
    {
        printf("pos is invalid, insert failed!\n");
        return -1;
    }
    //2. 把data包装成节点p
    node_t *p = (node_t *)malloc(sizeof(node_t));
    if (NULL == p)
    {
        printf("malloc error, insert failed!\n");
        return -1;
    }
    p->data = data;
    p->next = NULL;
    //3. 找到要插入位置的前一个节点q
    node_t *q = head;
    while (pos--)
        q = q->next;
    //4. 把p插入节点q后面
    p->next = q->next;
    q->next = p;
    return 0;
}

int linklist_pos_delete(node_t *head, int pos)
{
    //1. 判断pos位置是否有效
    int len = linklist_length(head);
    if ((pos < 0) || (pos >= len))
    {
        printf("pos is invalid, delete failed!\n");
        return -1;
    }
    //2. 找到删除节点q的前一节点p
    node_t *p = head;
    node_t *q = NULL;
    while (pos--)
        p = p->next;
    q = p->next;
    //3. 删除节点q
    p->next = q->next;
    free(q);
    return 0;
}

int linklist_data_delete(node_t *head, data_t data)
{
    //1. 找到删除数据data的位置pos
    int pos = 0;
    node_t *p = head->next;
    while (p != head)
    {
        if (p->data == data)
            break;
        pos++;
        p = p->next;
    }
    if (head == p)
    {
        printf("No such data, delete failed!\n");
        return -1;
    }
    //2. 调用posDelete删除数据
    linklist_pos_delete(head, pos);
    return 0;
}

int linklist_pos_update(node_t *head, int pos, data_t data)
{
    int len = linklist_length(head);
    if ((pos < 0) || (pos >= len))
    {
        printf("pos is invalid, update failed!\n");
        return -1;
    }
    node_t *p = head->next;
    while (pos--)
        p = p->next;
    p->data = data;
    return 0;
}

int linklist_data_update(node_t *head, data_t old_data, data_t new_data)
{
    node_t *p = linklist_data_search(head, old_data);
    if (NULL == p)
    {
        printf("No such data, update failed!\n");
        return -1;
    }
    p->data = new_data;
    return 0;
}

data_t linklist_pos_search(node_t *head, int pos)
{
    int len = linklist_length(head);
    if ((pos < 0) || (pos >= len))
    {
        printf("pos is invalid, search failed!\n");
        return (data_t)-1;
    }
    node_t *p = head->next;
    while (pos--)
        p = p->next;
    return p->data;
}

node_t *linklist_data_search(node_t *head, data_t data)
{
    node_t *p = head->next;
    while (p != head)
    {
        if (p->data == data)
            return p;
        p = p->next;
    }
    printf("No such data, search failed!\n");
    return NULL;
}

void linklist_display(node_t *head)
{
    node_t *p = head->next;
    while (p != head)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void linklist_invert(node_t *head)
{
    node_t *p = head->next;
    node_t *q = NULL;
    //把链表断开成两个链表，一个只有头，一个只有有效节点
    head->next = head;
    //遍历所有的有效节点，使用头插法插入到只有头的链表中
    while (p != head)
    {
        q = p->next;
        //头插法：把p插入到head后面
        p->next = head->next;
        head->next = p;
        p = q;
    }
}

void linklist_sort(node_t *head)
{
    node_t *p = head->next; //第一个有效节点
    node_t *q = NULL; //p的下一个节点
    node_t *t = NULL; //要插入位置的前一个节点
    node_t *r = NULL; //要插入位置的节点
    head->next = head;  //断开链表为两个链表
    //遍历无序链表，把每一个节点在有序链表中找到相应位置插入
    while (p != head)
    {
        q = p->next; //先保存p的下一个节点
        //从head开始找到有序链表中要插入位置的前一节点t
        t = head;    
        r = t->next;
        //当插入位置r存在且p值大于r值时，则t，r都后移一个节点
        while (r != head && p->data > r->data)
        {
            t = r;
            r = t->next;
        }
        //把p插入t后面
        p->next = r;
        t->next = p;
        //再插入下一个节点
        p = q;
    }
}

双向循环链表

每个结点存在两个指针域，分别存储该结点的前驱结点引用和后继结点引用，从任意一个结点出发，都能通过前驱引用以及后继引用完成整个链表结点的访问。

linklist.h

#ifndef __LINKLIST_H__
#define __LINKLIST_H__

typedef int data_t;

typedef struct node{
    data_t data;   //数据域
    struct node *next; //指针域：指向下一个节点
}node_t;

node_t *linklist_create();
void linklist_destory(node_t *head);

void linklist_clear(node_t *head);
int linklist_isFull(node_t *head);
int linklist_isEmpty(node_t *head);
int linklist_length(node_t *head);

int linklist_insert(node_t *head, int pos, data_t data);
int linklist_pos_delete(node_t *head, int pos);
int linklist_data_delete(node_t *head, data_t data);
int linklist_pos_update(node_t *head, int pos, data_t data);
int linklist_data_update(node_t *head, data_t old_data, data_t new_data);
data_t linklist_pos_search(node_t *head, int pos);
node_t *linklist_data_search(node_t *head, data_t data);

//实现链表的倒置
void linklist_invert(node_t *head);
void linklist_sort(node_t *head);
void linklist_display(node_t *head);

#endif

linklist.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "linklist.h"

node_t *linklist_create()
{
    node_t *head = (node_t *)malloc(sizeof(node_t)); 
    if (NULL == head)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    memset(head, 0, sizeof(node_t));
    head->next = NULL;
    return head;
}

void linklist_destory(node_t *head)
{
    linklist_clear(head);
    free(head);
}

void linklist_clear(node_t *head)
{
    node_t *p = head->next;  //第一个有效节点
    node_t *q = NULL; 
    while (p != NULL)  //判断有效节点是否存在
    {
        q = p->next;  //先把下一个节点保存
        free(p);  //销毁p
        p = q;    //把下一个节点赋给p
    }
    head->next = NULL;  //把头节点指针域置空
}

int linklist_isFull(node_t *head)
{
    return 0;
}

int linklist_isEmpty(node_t *head)
{
    return (NULL == head->next) ? 1 : 0;
}

int linklist_length(node_t *head)
{
    int len = 0;
    node_t *p = head->next; //p指向第一个有效节点
    while (p != NULL)  //判断节点是否存在
    { 
        len++;    
        p = p->next;  //p向下一个节点偏移
    }
    return len;
}

int linklist_insert(node_t *head, int pos, data_t data)
{
    //1. 判断pos是否有效，无效则报错返回
    int len = linklist_length(head);
    if ((pos < 0) || (pos > len))
    {
        printf("pos is invalid, insert failed!\n");
        return -1;
    }
    //2. 把data包装成节点p
    node_t *p = (node_t *)malloc(sizeof(node_t));
    if (NULL == p)
    {
        printf("malloc error, insert failed!\n");
        return -1;
    }
    p->data = data;
    p->next = NULL;
    //3. 找到要插入位置的前一个节点q
    node_t *q = head;
    while (pos--)
        q = q->next;
    //4. 把p插入节点q后面
    p->next = q->next;
    q->next = p;
    return 0;
}

int linklist_pos_delete(node_t *head, int pos)
{
    //1. 判断pos位置是否有效
    int len = linklist_length(head);
    if ((pos < 0) || (pos >= len))
    {
        printf("pos is invalid, delete failed!\n");
        return -1;
    }
    //2. 找到删除节点q的前一节点p
    node_t *p = head;
    node_t *q = NULL;
    while (pos--)
        p = p->next;
    q = p->next;
    //3. 删除节点q
    p->next = q->next;
    free(q);
    return 0;
}

int linklist_data_delete(node_t *head, data_t data)
{
    //1. 找到删除数据data的位置pos
    int pos = 0;
    node_t *p = head->next;
    while (p != NULL)
    {
        if (p->data == data)
            break;
        pos++;
        p = p->next;
    }
    if (NULL == p)
    {
        printf("No such data, delete failed!\n");
        return -1;
    }
    //2. 调用posDelete删除数据
    linklist_pos_delete(head, pos);
    return 0;
}

int linklist_pos_update(node_t *head, int pos, data_t data)
{
    int len = linklist_length(head);
    if ((pos < 0) || (pos >= len))
    {
        printf("pos is invalid, update failed!\n");
        return -1;
    }
    node_t *p = head->next;
    while (pos--)
        p = p->next;
    p->data = data;
    return 0;
}

int linklist_data_update(node_t *head, data_t old_data, data_t new_data)
{
    node_t *p = linklist_data_search(head, old_data);
    if (NULL == p)
    {
        printf("No such data, update failed!\n");
        return -1;
    }
    p->data = new_data;
    return 0;
}

data_t linklist_pos_search(node_t *head, int pos)
{
    int len = linklist_length(head);
    if ((pos < 0) || (pos >= len))
    {
        printf("pos is invalid, search failed!\n");
        return (data_t)-1;
    }
    node_t *p = head->next;
    while (pos--)
        p = p->next;
    return p->data;
}

node_t *linklist_data_search(node_t *head, data_t data)
{
    node_t *p = head->next;
    while (p != NULL)
    {
        if (p->data == data)
            return p;
        p = p->next;
    }
    printf("No such data, search failed!\n");
    return NULL;
}

void linklist_display(node_t *head)
{
    node_t *p = head->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void linklist_invert(node_t *head)
{
    node_t *p = head->next;
    node_t *q = NULL;
    //把链表断开成两个链表，一个只有头，一个只有有效节点
    head->next = NULL;
    //遍历所有的有效节点，使用头插法插入到只有头的链表中
    while (p != NULL)
    {
        q = p->next;
        //头插法：把p插入到head后面
        p->next = head->next;
        head->next = p;
        p = q;
    }
}

void linklist_sort(node_t *head)
{
    node_t *p = head->next; //第一个有效节点
    node_t *q = NULL; //p的下一个节点
    node_t *t = NULL; //要插入位置的前一个节点
    node_t *r = NULL; //要插入位置的节点
    head->next = NULL;  //断开链表为两个链表
    //遍历无序链表，把每一个节点在有序链表中找到相应位置插入
    while (p != NULL) 
    {
        q = p->next; //先保存p的下一个节点
        //从head开始找到有序链表中要插入位置的前一节点t
        t = head;    
        r = t->next;
        //当插入位置r存在且p值大于r值时，则t，r都后移一个节点
        while (r != NULL && p->data > r->data)
        {
            t = r;
            r = t->next;
        }
        //把p插入t后面
        p->next = r;
        t->next = p;
        //再插入下一个节点
        p = q;
    }
}

栈：

顺序栈：栈中数据连续存储

#define SIZE 100
typedef int data_t;

typedef struct {
     data_t data[SIZE];
     int top;   //栈顶指针，最后一个有效元素下标
}stack_t;
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "stack.h"

stack_t *stack_create()
{
    stack_t *head = (stack_t *)malloc(sizeof(stack_t));
    if (NULL == head)
    {
        printf("malloc error, create failed!\n");
        return NULL;
    }
    memset(head, 0, sizeof(stack_t));
    head->top = -1;
    return head;
}

void stack_destory(stack_t *head)
{
    free(head);
}

void stack_clear(stack_t *head)
{
    head->top = -1;
}

int stack_isFull(stack_t *head)
{
    return (SIZE-1 == head->top) ? 1 : 0;
}

int stack_isEmpty(stack_t *head)
{
    return (-1 == head->top) ? 1: 0;
}

int stack_push(stack_t *head, data_t data)
{
    if (stack_isFull(head))
    {
        printf("stack is full, push failed!\n");
        return -1;
    }
    head->data[head->top+1] = data;
    head->top++;
    return 0;
}

data_t stack_pop(stack_t *head)
{
    if (stack_isEmpty(head))
    {
        printf("stack is empty, pop failed!\n");
        return (data_t)-1;
    }
    data_t data = head->data[head->top];
    head->top--;
    return data;
}

data_t stack_get_top(stack_t *head)
{
    if (stack_isEmpty(head))
    {
        printf("stack is empty, no top data!\n");
        return (data_t)-1;
    }
    return head->data[head->top];
}

void stack_display(stack_t *head)
{
    int i;
    for (i = 0; i <= head->top; i++)
        printf("%d ", head->data[i]);
    printf("\n");
}

链式栈：栈中数据散列存储

typedef int data_t;

typedef struct node{
    data_t data;   //数据域
    struct node *next; //指针域：指向下一个节点
}node_t;
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stack.h"

node_t *stack_create()
{
    node_t *head = (node_t *)malloc(sizeof(node_t));
    if (NULL == head)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    memset(head, 0, sizeof(node_t));
    head->next = NULL;
    return head;
}

void stack_destory(node_t *head)
{
    stack_clear(head);
    free(head);
}

void stack_clear(node_t *head)
{
    node_t *p = head->next;  //第一个有效节点
    node_t *q = NULL;
    while (p != NULL)  //判断有效节点是否存在
    {
        q = p->next;  //先把下一个节点保存
        free(p);  //销毁p
        p = q;    //把下一个节点赋给p
    }
    head->next = NULL;  //把头节点指针域置空
}

int stack_isFull(node_t *head)
{
    return 0;
}

int stack_isEmpty(node_t *head)
{
    return (NULL == head->next) ? 1 : 0;
}

int stack_length(node_t *head)
{
    int len = 0;
    node_t *p = head->next; //p指向第一个有效节点
    while (p != NULL)  //判断节点是否存在
    {
        len++;    
        p = p->next;  //p向下一个节点偏移
    }
    return len;
}

int stack_push(node_t *head, data_t data)
{
    //把data包装成节点p
    node_t *p = (node_t *)malloc(sizeof(node_t));
    if (NULL == p)
    {
        printf("malloc error, insert failed!\n");
        return -1;
    }
    p->data = data;
    p->next = NULL;
    
    node_t *q = head;
    //4. 把p插入节点q后面
    p->next = q->next;
    q->next = p;
    return 0;
}

data_t stack_pop(node_t *head)
{
    if (stack_isEmpty(head))
    {
        printf("stack is empty, pop failed!\n");
        return (data_t)-1;
    }
    //2. 找到删除节点q的前一节点p
    node_t *p = head;
    node_t *q = p->next;
    data_t data = q->data;
    //3. 删除节点q
    p->next = q->next;
    free(q);
    return data;
}

data_t stack_get_top(node_t *head)
{
    if (stack_isEmpty(head))
    {
        printf("stack is empty, no top data!\n");
        return (data_t)-1;
    }
    return head->next->data;
}

void stack_display(node_t *head)
{
    node_t *p = head->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

队列：

#ifndef __QUEUE_H__
#define __QUEUE_H__

#define SIZE 7
typedef int data_t;

typedef struct {
    data_t data[SIZE];
    int front;
    int rear;
}queue_t;

queue_t *queue_create();
void queue_destory(queue_t *head);
void queue_clear(queue_t *head);
int queue_isFull(queue_t *head);
int queue_isEmpty(queue_t *head);
//入队
int queue_en(queue_t *head, data_t data);
//出队
data_t queue_de(queue_t *head);

void queue_display(queue_t *head);

#endif

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "queue.h"

queue_t *queue_create()
{
    queue_t *head = (queue_t *)malloc(sizeof(queue_t));
    if (NULL == head)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    memset(head, 0, sizeof(queue_t));
    head->front = 0;
    head->rear = 0;
    return head;
}

void queue_destory(queue_t *head)
{
    free(head);
}

void queue_clear(queue_t *head)
{
    head->front = head->rear = 0;
}

int queue_isFull(queue_t *head)
{
    return (SIZE == head->rear - head->front) ? 1 : 0;
}

int queue_isEmpty(queue_t *head)
{
    return (head->rear == head->front) ? 1 : 0;
}

//入队
int queue_en(queue_t *head, data_t data)
{
    if (queue_isFull(head))
    {
        printf("queue is full, enter failed!\n");
        return -1;
    }
    head->data[head->rear % SIZE] = data;
    head->rear++;
    return 0;
}

//出队
data_t queue_de(queue_t *head)
{
    if (queue_isEmpty(head))
    {
        printf("queue is empty, delete failed!\n");
        return (data_t)-1;
    }
    data_t data = head->data[head->front % SIZE];
    head->front++;
    //当出队到SIZE时，rear和front重新回到数组下标对应位置
    if (SIZE == head->front)
    {
        head->front = 0;
        head->rear = head->rear % SIZE;
    }
    return data;
}

void queue_display(queue_t *head)
{
    int i;
    for (i = head->front; i < head->rear; i++)
        printf("%d ", head->data[i % SIZE]);
    printf("\n");
}

#include <stdio.h>
#include "queue.h"

int main(int argc, char *argv[])
{ 
    queue_t *head = queue_create();
    if (NULL == head)
    {
        printf("create failed!\n");
        return -1;
    }
    int i, n;
    for (i = 1; i <= 3; i++)
        queue_en(head, i);
    queue_display(head);
    n = 3;
    while (n--)
        printf("de: %d\n", queue_de(head));
    queue_display(head);
    for (i = 1; i <= 8; i++)
        queue_en(head, i);
    queue_display(head);
    
    
    queue_destory(head);
    head = NULL;

    return 0;
}

树

二叉树：

定义：二叉树(Binary Tree)是n(n≥0）个节点的有限集合，它或者是空集(n=0)，或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

完全二叉树：

二叉树的性质︰

二叉树第i (i≥1)）层上的节点最多为2i-1个。深度为k (k≥1)的二叉树最多有2一1个节点。

在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。

总节点数为各类节点之和：n = no + n + n2

总节点数为所有子节点数加一：n = n1+2*n2+ 1

故得： no= 2+ 1 ;

满二叉树：深度为k (k多1)时有2一1个节点的二叉树。

完全二叉树：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。具有n个节点的完全二叉树的深度为

( log2n）＋1或『log2(n+1)。

二叉树的存储∶

顺序存储结构∶完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。设完全二叉树的节点数为 n，某节点编号为i

1）当i>1(不是根节点）时，有父节点，其编号为i/2;

2）当2*i≤n时，有左孩子，其编号为2*i ,否则没有左孩子，本身是叶节点;当2*i十1≤n时，有右孩子，其编号为2*i+1 ,否则没有右孩子;

3）当i为奇数且不为1时，有左兄弟，其编号为i-1,否则没有左兄弟;

4）当i为偶数且小于n时，有右兄弟，其编号为i+1,否则没有右兄弟

#ifndef __TREE_H__
#define __TREE_H__

typedef int data_t;

typedef struct node{
    data_t data;
    struct node *lchild;
    struct node *rchild;
}tree_t;

//创建完全二叉树，树根编号i=1，总共节点数
tree_t *tree_create(int i, int n);

void tree_DLR(tree_t *root);
void tree_LDR(tree_t *root);
void tree_LRD(tree_t *root);
void tree_level_show(tree_t *root);

#endif

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "tree.h"

tree_t *tree_create(int i, int n)
{
    tree_t *root = (tree_t *)malloc(sizeof(tree_t));
    if (NULL == root)
    {
        printf("malloc failed!\n");
        return NULL;
    }
    root->data = i;
    if (2*i <= n)
        root->lchild = tree_create(2*i, n);
    else
        root->lchild = NULL;
    if (2*i+1 <= n)
        root->rchild = tree_create(2*i+1, n);
    else
        root->rchild = NULL;
    return root;
}

void tree_DLR(tree_t *root)
{
    if (NULL == root)
        return;
    printf("%d ", root->data);
    tree_DLR(root->lchild);
    tree_DLR(root->rchild);
}

void tree_LDR(tree_t *root)
{
    if (NULL == root)
        return;
    tree_LDR(root->lchild);
    printf("%d ", root->data);
    tree_LDR(root->rchild);

}

void tree_LRD(tree_t *root)
{
    if (NULL == root)
        return;
    tree_LRD(root->lchild);
    tree_LRD(root->rchild);
    printf("%d ", root->data);

}

void tree_level_show(tree_t *root)
{
    //1. 当树根为空时，报错返回
    if (NULL == root)
    {
        printf("This is NULL tree!\n");
        return;
    }
    //2. 定义队列
    tree_t *queue[100] = {NULL};
    int front, rear;
    front = rear = 0;
    //3. 让根节点入队
    queue[rear++] = root;
    //4. 循环判断队列是否为空，为空时跳出循环，否则让第一个元素出队，出队后判断其左右孩子是否存在，如果存在则让左右孩子入队
    while (rear != front)
    {
        tree_t *p = queue[front++];
        printf("%d ", p->data);
        if (NULL != p->lchild)
            queue[rear++] = p->lchild;
        if (NULL != p->rchild)
            queue[rear++] = p->rchild;
    }
    printf("\n");
}

二叉树的遍历

四种主要的遍历思想为：

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

层次遍历：只需按层次遍历即可

资讯详情

数据结构（部分）

数据结构：

单向循环链表（尾结点指向头结点）

双向循环链表

栈：

队列：

树

图：水平有限......但数据结构：图(Graph)【详解】 (editcode.net)该作者对图有详细理解，读者可以参考。

Molex Premo-Flex 0.5mm-Pitch跨接电缆带耳片的介绍、特性、及应用

数据结构（部分）

数据结构：

单向循环链表（尾结点指向头结点）

双向循环链表

栈：

队列：

树

图：水平有限......但数据结构：图(Graph)【详解】 (editcode.net)该作者对图有详细理解，读者可以参考。

Molex Premo-Flex 0.5mm-Pitch跨接电缆带耳片的介绍、特性、及应用

最近热搜

历史搜索 清除历史记录

历史搜索清除历史记录