C/C++ - 数据结构（链表、栈、队列、树（二叉树））、动态数组

发布日期：2021-06-30 16:57:24 浏览次数：2 分类：技术文章

本文共 22078 字，大约阅读时间需要 73 分钟。

文章目录

链表（思路一）

普通单向链表

初始化

在这里插入图片描述

2020年10月08日
缺点：

结构体设计没有通用性
int val 换成 void *data

优化参考：

#include 
   
    #include 
    
     struct LinkNode{
       int val;    struct LinkNode *next;} l;void destroy(struct LinkNode *node){
       if (node == NULL)    {
           return;    }    struct LinkNode *next = node->next;    free(node);    printf("(destroy)%p\n", node);    if (next != NULL)    {
           destroy(next);    }}void show(struct LinkNode *first){
       if (first == NULL)    {
           return;    }    printf("%p %d\n", first, first->val);    if (first->next != NULL)    {
           show(first->next);    }}void build(struct LinkNode **first, int *vals, int len){
       if (len > 0)    {
           *first = malloc(sizeof(struct LinkNode));        (*first)->val = vals[0];        build(&(*first)->next, vals + 1, len - 1);    }    else    {
           *first = NULL;    }}void test(){
       struct LinkNode *node1;    int vals[] = {
   1, 2, 3, 4, 5, 6};    int len = sizeof(vals) / sizeof(vals[0]);    build(&node1, vals, len);    show(node1);    destroy(node1);}int main(int argc, char *argv[]){
       test();    return 0;}

在这里插入图片描述

插入、删除（add_next、remove_next）

void add_next(struct LinkNode *first, struct LinkNode *node){
       if (first == NULL || node == NULL)    {
           return;    }    // 合并尾部    struct LinkNode *end = node;    while (end->next != NULL)    {
           end = end->next;    }    end->next = first->next;    // 合并前面    first->next = node;}void remove_next(struct LinkNode *node){
       if (node == NULL || node->next == NULL)    {
           return;    }    struct LinkNode *next = node->next->next;    free(node->next);    node->next = next;}void test(){
       struct LinkNode *node1;    int vals[] = {
   1, 2, 3, 4, 5, 6};    int len = sizeof(vals) / sizeof(vals[0]);    printf("\n-------原始-------\n");    build(&node1, vals, len);    show(node1);    printf("\n-------删除-------\n");    remove_next(node1);    //             1    3    4     5    remove_next(node1->next->next->next);    show(node1);    printf("\n-------增加-------\n");    struct LinkNode *nodel2;    int vals2[] = {
   11, 22, 33, 44};    int len2 = sizeof(vals2) / sizeof(vals2[0]);    build(&nodel2, vals2, len2);    add_next(node1->next, nodel2);    show(node1);    printf("\n-------清理-------\n");    destroy(node1);}

在这里插入图片描述

链表（思路二）

在这里插入图片描述

首地址可以表示用户数据，也可以表示node

#include 
   
    #include 
    
     struct LinkNode{
       struct LinkNode *next;};struct LinkList{
       struct LinkNode header;    int size;};typedef void *List;// 初始化链表List init_LinkList(){
       struct LinkList *list = malloc(sizeof(List));    if (NULL == list)    {
           // log...        return NULL;    }    list->header.next = NULL;    list->size = 0;    return list;}//void insert_LinkList(List list, int offset, void *data){
       if (list == NULL)    {
           // log...        return;    }    struct LinkList *myList = (struct LinkList *)list;    struct LinkNode *newNode = (struct LinkNode *)data;    // 下标    if (0 > offset)    {
           offset = 0;    }    else if (offset >= myList->size)    {
           offset = myList->size;    }    //    struct LinkNode *previousNode = &myList->header;    for (int i = 0; i < offset; i++)    {
           previousNode = previousNode->next;    }    if (previousNode->next == NULL)    {
           previousNode->next = newNode;        (myList->size)++;    }    else    {
           if (newNode != NULL)        {
               newNode->next = previousNode->next->next;        }        previousNode->next = newNode;    }}//void foreach_LinkList(List list, void _callback_(int, void *)){
       if (list == NULL)    {
           return;    }    if (_callback_ == NULL)    {
           return;    }    struct LinkList *myList = (struct LinkList *)list;    struct LinkNode *currentNode = &myList->header;    int index = 0;    // while ((currentNode = currentNode->next) != NULL) // 会导致死循环    for(int i=0; i
     
      size; i++)    {
       	currentNode = currentNode->next;        _callback_(index++, currentNode);    }}//void destory_LinkList(List list){
       if (list == NULL)    {
           return;    }    free(list);    list = NULL;}//void remove_LinkList(List list, int offset){
       if (list == NULL)    {
           // log        return;    }    struct LinkList *myList = (struct LinkList *)list;    if (offset < 0 || offset >= myList->size)    {
           // log        return;    }    struct LinkNode *preNode = &myList->header;    for (int i = 0; i < offset; i++)    {
           preNode = preNode->next;    }    preNode->next = preNode->next->next;    (myList->size)--;}// -------- test -------------struct Persion{
       struct LinkNode node;    char *name;    int age;};void foreach_LinkList_handle_1(int index, void *item){
       struct Persion *p = (struct Persion *)item;    printf("%p node=%p next=%p name=%s age=%d\n", p, &p->node, p->node.next, p->name, p->age);}void test(){
       printf("----------------- data ---------------\n");    struct Persion p1 = {
   NULL, "p1", 11};    struct Persion p2 = {
   NULL, "p2", 12};    struct Persion p3 = {
   NULL, "p3", 13};    struct Persion p4 = {
   NULL, "p4", 14};    struct Persion p5 = {
   NULL, "p5", 15};    printf("----------------- init ---------------\n");    List list = init_LinkList();    printf("----------------- insert ---------------\n");    insert_LinkList(list, 0, &p1);    insert_LinkList(list, 1, &p2);    insert_LinkList(list, 2, &p3);    // insert_LinkList(list, 3, &p4); // 死回环链表的处理    insert_LinkList(list, 3, &p4);    insert_LinkList(list, 4, &p5);    insert_LinkList(list, 1, &p5);    printf("----------------- foreach ---------------\n");    foreach_LinkList(list, foreach_LinkList_handle_1);    printf("----------------- remove ---------------\n");    remove_LinkList(list, 3);    remove_LinkList(list, 0);    remove_LinkList(list, 2);    printf("----------------- foreach ---------------\n");    foreach_LinkList(list, foreach_LinkList_handle_1);    //    destory_LinkList(list);}int main(){
       test();    return 0;}

----------------- data -------------------------------- init -------------------------------- insert -------------------------------- foreach ---------------0x7ffc54961570 node=0x7ffc54961570 next=0x7ffc549615f0 name=p1 age=110x7ffc549615f0 node=0x7ffc549615f0 next=0x7ffc549615b0 name=p5 age=150x7ffc549615b0 node=0x7ffc549615b0 next=0x7ffc549615d0 name=p3 age=130x7ffc549615d0 node=0x7ffc549615d0 next=0x7ffc549615f0 name=p4 age=140x7ffc549615f0 node=0x7ffc549615f0 next=0x7ffc549615b0 name=p5 age=15----------------- remove -------------------------------- foreach ---------------0x7ffc549615f0 node=0x7ffc549615f0 next=0x7ffc549615b0 name=p5 age=150x7ffc549615b0 node=0x7ffc549615b0 next=0x7ffc549615b0 name=p3 age=13

动态数组

（C实现一）

#include 
   
    #include 
    
     #include 
     
      // 动态数组// 1. 先把需要的数据信息结构定义下来struct DynamicArray{
       // 数组存储元素的空间首地址    void **addr; // 首地址的地址    // 存储数据的内存中最大能够容纳多少元素    unsigned int capacity; // 容量    // 当前存储数据的内存中有多少个元素    unsigned int size; // 大小};void destory_DynamicArray(struct DynamicArray *arr){
       if (arr != NULL)    {
           if (arr->addr != NULL)        {
               free(arr->addr);        }        free(arr);    }}// 初始化数组struct DynamicArray *init_DynamicArray(int capacity){
       if (capacity <= 0)    {
           // log        return NULL;    }    struct DynamicArray *arr = malloc(sizeof(struct DynamicArray));    if (NULL == arr)    {
           // log        return NULL;    }    arr->addr = calloc(0, sizeof(void *) * capacity);    arr->capacity = capacity;    arr->size = 0;    return arr;}// 处理下标越界int range(int size, int pos){
       if (size == 0)    {
           pos = 0;    }    else    {
           while (pos < 0 || pos >= size)        {
               pos = (pos < 0) ? (size + pos) : (pos - size);        }    }    return pos;}// 插入元素void insert(struct DynamicArray *arr, int pos, void *data){
       if (arr == NULL)    {
           // log        return;    }    // 处理下标越界    pos = range(arr->size, pos);    // 判断空间是否足够    if (arr->capacity < (arr->size + 1))    {
    // 扩容        // 移植        int n_capacity = (arr->capacity * 2);        void **n_addr = malloc(sizeof(void *) * n_capacity);        // 这里用calloc,当n_capacity==8时会影响到原来的堆空间，为什么？        memset(n_addr, 0, sizeof(n_addr));                           // 初始化        memcpy(n_addr, arr->addr, (sizeof(void *) * arr->capacity)); // 拷贝        free(arr->addr);                                             // 释放        // 部署        arr->addr = n_addr;        arr->capacity = n_capacity;    }    // 插入    signed int temp = arr->size;    for (int i = temp - 1; i >= pos; i--)    {
           arr->addr[i + 1] = arr->addr[i];    }    arr->addr[pos] = data;    (arr->size)++;}// 位置删除void remove_item(struct DynamicArray *arr, int pos){
       if (arr == NULL)    {
           // log ...        return;    }    if (arr->size == 0)    {
           return;    }    // 处理下标越界    pos = range(arr->size, pos);    // 左移，删尾    for (int i = pos; i < (signed)arr->size - 1; i++)    {
           arr->addr[i] = arr->addr[i + 1];    }    arr->addr[arr->size] = NULL;    (arr->size)--;}// 遍历void foreach (struct DynamicArray *arr, void (*_callback)(int, void *)){
       if (arr == NULL)    {
           // log        return;    }    if (_callback == NULL)    {
           // log        return;    }    for (int i = 0; i < arr->size; i++)    {
           _callback(i, arr->addr[i]);    }}// ------------------ test --------------------struct Persion{
       char *name;    int age;};void callback_1(int index, void *data){
       int *d = (int *)data;    printf("%p - %d \tindex=%d\n", data, *d, index);}void callback_2(int index, void *data){
       struct Persion *d = (struct Persion *)data;    printf("%p - name=%s age=%d \tindex=%d\n", data, d->name, d->age, index);}void show(struct DynamicArray *arr){
       foreach (arr, callback_1)        ;    printf("addr:%p size:%d capacity:%d\n", arr->addr, arr->size, arr->capacity);}void show_2(struct DynamicArray *arr){
       foreach (arr, callback_2)        ;    printf("addr:%p size:%d capacity:%d\n", arr->addr, arr->size, arr->capacity);}void test(void *a, void *b, void *c){
       //    printf("\n ------- init ------ \n");    struct DynamicArray *arr = init_DynamicArray(2);    show(arr);    //    printf("\n ------- insert ------ \n");    insert(arr, -1, a);    insert(arr, 1, b);    show(arr);    //    printf("\n ------- extend 1 ------ \n");    insert(arr, 2, b);    insert(arr, 3, c);    show(arr);    //    printf("\n ------- extend 2 ------ \n");    insert(arr, 2, b);    insert(arr, 3, c);    show(arr);    //    printf("\n ------- remove ------ \n");    remove_item(arr, 1);    remove_item(arr, arr->size);    remove_item(arr, arr->size - 1);    show(arr);    //    destory_DynamicArray(arr);}// test:标准数据类型void test_1(){
       printf("\n-------test 1-----------\n");    printf("\n-------test 1-----------\n");    printf("\n-------test 1-----------\n");    // pre    int a = 1;    int b = 2;    int c = 3;    printf("a %p %d\n", &a, a);    printf("b %p %d\n", &b, b);    printf("c %p %d\n", &c, c);    test(&a, &b, &c);}// test:结构体void test_2(){
       printf("\n******* test 2 ***********\n");    printf("\n******* test 2 ***********\n");    printf("\n******* test 2 ***********\n");    // pre    struct Persion a = {
           .name = "老王",        .age = 18};    struct Persion b = {
           .name = "翠花",        .age = 16};    struct Persion c = {
           .name = "二狗子",        .age = 19};    printf("a %p name=%s, age=%d\n", &a, a.name, a.age);    printf("b %p name=%s, age=%d\n", &b, b.name, b.age);    printf("c %p name=%s, age=%d\n", &c, c.name, c.age);    test(&a, &b, &c);}int main(){
       test_1();    test_2();    return 0;}

-------test 1------------------test 1------------------test 1-----------a 0x7fffffffe1dc 1b 0x7fffffffe1e0 2c 0x7fffffffe1e4 3 ------- init ------ addr:0x555555757690 size:0 capacity:2 ------- insert ------ 0x7fffffffe1e0 - 2      index=00x7fffffffe1dc - 1      index=1addr:0x555555757690 size:2 capacity:2 ------- extend 1 ------ 0x7fffffffe1e4 - 3      index=00x7fffffffe1e0 - 2      index=10x7fffffffe1e0 - 2      index=20x7fffffffe1dc - 1      index=3addr:0x5555557576b0 size:4 capacity:4 ------- extend 2 ------ 0x7fffffffe1e4 - 3      index=00x7fffffffe1e0 - 2      index=10x7fffffffe1e0 - 2      index=20x7fffffffe1e4 - 3      index=30x7fffffffe1e0 - 2      index=40x7fffffffe1dc - 1      index=5addr:0x5555557576e0 size:6 capacity:8 ------- remove ------ 0x7fffffffe1e0 - 2      index=00x7fffffffe1e4 - 3      index=10x7fffffffe1e0 - 2      index=2addr:0x5555557576e0 size:3 capacity:8******* test 2 ****************** test 2 ****************** test 2 ***********a 0x7fffffffe1b0 name=老王, age=18b 0x7fffffffe1c0 name=翠花, age=16c 0x7fffffffe1d0 name=二狗子, age=19 ------- init ------ addr:0x555555757730 size:0 capacity:2 ------- insert ------ 0x7fffffffe1c0 - 1431654931     index=00x7fffffffe1b0 - 1431654924     index=1addr:0x555555757730 size:2 capacity:2 ------- extend 1 ------ 0x7fffffffe1d0 - 1431654938     index=00x7fffffffe1c0 - 1431654931     index=10x7fffffffe1c0 - 1431654931     index=20x7fffffffe1b0 - 1431654924     index=3addr:0x5555557576b0 size:4 capacity:4 ------- extend 2 ------ 0x7fffffffe1d0 - 1431654938     index=00x7fffffffe1c0 - 1431654931     index=10x7fffffffe1c0 - 1431654931     index=20x7fffffffe1d0 - 1431654938     index=30x7fffffffe1c0 - 1431654931     index=40x7fffffffe1b0 - 1431654924     index=5addr:0x5555557576e0 size:6 capacity:8 ------- remove ------ 0x7fffffffe1c0 - 1431654931     index=00x7fffffffe1d0 - 1431654938     index=10x7fffffffe1c0 - 1431654931     index=2addr:0x5555557576e0 size:3 capacity:8

（C++实现一）（无泛型）【未实现】

https://www.bilibili.com/video/BV13b411V73v?p=356

#ifndef MYARRAY_H#define MYARRAY_Hclass MyArray{
   public:    // 无参构造函数，用户没有指定容量，则初始化为100    MyArray();    // 有参构造函数，用户指定容量初始化    explicit MyArray(int capacity);    // ---------------------------    // 用户操作接口    // ---------------------------    // 根据位置添加元素    void insert(int pos, int val);    // 获得指定位置数据    int get(int pos);    // 获得长度    int length();    // 析构函数，释放数组空间    ~MyArray();private:     int m_capacity; // 容量    int size; // 当前元素个数    int* data; // 数据};#endif

栈（stack）

首先它是一个线性表，也就是说，栈的元素具有线性关系，即前驱后继关系。只不过它是一种特殊的线性表而已。定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。

特性

它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也使得：栈底是固定的，最先进栈的只能在栈底。

操作

栈的插入操作，也叫做进栈、压栈。

栈的删除操作，也叫做出栈、弹栈、退栈。

在这里插入图片描述

栈的顺序存储

栈的顺序存储结构简称顺序栈，它是运算受限制的顺序表。顺序栈的存储结构是：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同事附设指针top只是栈顶元素在顺序表中的位置。

设计与实现

因为栈是一种特殊的线性表，所以栈的顺序存储可以通过顺序线性表来实现。

实现一：数组实现

接口

SeqStack.h

/* * SeqStack.h * *  Created on: Oct 9, 2020 *      Author: lawsssscat */#ifndef SEQSTACK_H_#define SEQSTACK_H_#ifdef __cplusplusextern "c"{
   #endif#define MAX 1024	// 顺序栈数据结构	struct SStack	{
   		void *data[MAX]; // 存放数据的数组		int size; // 栈元素的个数	};	typedef void* SeqStack;	// 数组高下标的位置当做栈顶，因为不需要移动数组中的元素在插入和删除中	// 初始化	SeqStack init_SeqStack();	// 入栈	void push_SeqStack(SeqStack stack, void* data);	// 出栈	void* pop_SeqStack(SeqStack stack);	// 获得栈的大小	int size_SeqStack(SeqStack stack);	// 销毁栈	void destroy_SeqStack(SeqStack stack);#ifdef _cplusplus}#endif#endif /* SEQSTACK_H_ */

实现

SeqStack.c

#include "SeqStack.h"#include 
   
    #include 
    
     #include 
     
      /* * SeqStack.c * *  Created on: Oct 9, 2020 *      Author: lawsssscat */// 初始化SeqStack init_SeqStack(){
       int size = sizeof(struct SStack *);    struct SStack *stack = malloc(size);    memset(stack, 0, size);    stack->size = 0;    return stack;}struct SStack *to(SeqStack stack){
       return (struct SStack *)stack;}// 入栈void push_SeqStack(SeqStack stack, void *data){
       struct SStack *myStack = to(stack);    myStack->data[myStack->size] = data;    myStack->size++;}// 出栈void *pop_SeqStack(SeqStack stack){
       struct SStack *myStack = to(stack);    void *data = myStack->data[myStack->size-1];    myStack->size--;    return data;}int size_SeqStack(SeqStack stack){
       return to(stack)->size;}void destroy_SeqStack(SeqStack stack){
       free(stack);    stack = NULL;}

测试

test.c

#include "SeqStack.h"#include 
   
    /* * test.c * *  Created on: Oct 9, 2020 *      Author: lawsssscat */struct Persion{
   	char *name;	int age;};void test01(){
   	// inti	SeqStack stack = init_SeqStack();	printf("%p size=%d\n", stack, size_SeqStack(stack));	// 插入	struct Persion p0 = {
   		.name = "老王",		.age = 18};	struct Persion p00 = {
   		.name = "翠花",		.age = 16};	struct Persion p000 = {
   		.name = "小明",		.age = 17};	push_SeqStack(stack, &p0);	printf("<----%p name=%s age=%d %p size=%d\n", &p0, p0.name, p0.age, stack, size_SeqStack(stack));	push_SeqStack(stack, &p00);	printf("<----%p name=%s age=%d %p size=%d\n", &p00, p00.name, p00.age, stack, size_SeqStack(stack));	push_SeqStack(stack, &p000);	printf("<----%p name=%s age=%d %p size=%d\n", &p000, p000.name, p000.age, stack, size_SeqStack(stack));	// 取出	struct Persion *p1 = pop_SeqStack(stack);	printf("---->%p name=%s age=%d %p size=%d\n", &p1, p1->name, p1->age, stack, size_SeqStack(stack));	struct Persion *p11 = pop_SeqStack(stack);	printf("---->%p name=%s age=%d %p size=%d\n", &p11, p11->name, p11->age, stack, size_SeqStack(stack));	struct Persion *p111 = pop_SeqStack(stack);	printf("---->%p name=%s age=%d %p size=%d\n", &p111, p111->name, p111->age, stack, size_SeqStack(stack));}int main(){
   	test01();	return 0;}

控制台

0x563de6fed260 size=0<----0x7ffcce45faa0 name=老王 age=18 0x563de6fed260 size=1<----0x7ffcce45fab0 name=翠花 age=16 0x563de6fed260 size=2<----0x7ffcce45fac0 name=小明 age=17 0x563de6fed260 size=3---->0x7ffcce45fa80 name=小明 age=17 0x563de6fed260 size=2---->0x7ffcce45fa88 name=翠花 age=16 0x563de6fed260 size=1---->0x7ffcce45fa90 name=老王 age=18 0x563de6fed260 size=0

栈的链式存储

实现二：链表实现【待实现】

大同小异，有空再弄

https://www.bilibili.com/video/BV13b411V73v?p=290

2020年10月11日

#include 
   
    #include 
    
     struct LinkNode{
       void *data;    struct LinkNode *next;};struct LStack{
       struct LinkNode header;    int size;};typedef void *LinkStack;// 初始化LinkStack init_LinkStack(){
       struct LStack *stack = malloc(sizeof(struct LStack));    memset(stack, 0, sizeof(stack));    stack->size = 0;    stack->header.next = NULL;    stack->header.data = NULL;    return stack;}// 入栈void push_LinkStack(LinkStack stack, void *data){
       struct LStack *myStack = (struct LStack *)stack;    if (data == NULL)    {
           // log...        return;    }    struct LinkNode *new_node = malloc(sizeof(struct LinkNode));    memset(new_node, 0, sizeof(new_node));    new_node->data = data;    new_node->next = myStack->header.next;    myStack->header.next = new_node;    myStack->size++;}// 出栈void *pop_LinkNode(struct LinkNode *node){
       void *data = node->data;    free(node);    return data;}void* pop_LinkStack(LinkStack stack){
       struct LStack *myStack = (struct LStack *)stack;    //    myStack->size--;    struct LinkNode *node = myStack->header.next;    myStack->header.next = node->next;    return pop_LinkNode(node);}// 大小int size_LinkStack(LinkStack stack){
       return ((struct LStack *)stack)->size;}// 销毁void destroy_LinkStack(LinkStack stack){
       while(size_LinkStack(stack)>0)    {
           pop_LinkStack(stack);    }    free(stack);}// ======================= test ==============================#include 
     
      struct Persion{
       char *name;    int age;};void printf_foreach_handler(int index, struct LinkNode *node){
   }int main(){
       struct Persion ps[] = {
           {
   "老王", 18},        {
   "翠花", 16},        {
   "小明", 17}};    int len = sizeof(ps) / sizeof(struct Persion);    LinkStack stack = init_LinkStack();    for (int i = 0; i < len; i++)    {
           push_LinkStack(stack, &ps[i]);        printf("%p size=%d\n", stack, size_LinkStack(stack));    }    for (int i = 0; i < len; i++)    {
           struct Persion *p = (struct Persion *)pop_LinkStack(stack);        printf("%d %p %s %d\n", index, p, p->name, p->age);    }    destroy_LinkStack(stack);    return 0;}

在这里插入图片描述

栈的应用（案例）【待完成】

https://www.bilibili.com/video/BV13b411V73v?p=291

就近匹配

几乎所有的编辑器都具有检测括号是否匹配的能力，那么如何实现编译器中的符号成对检测？

算法思路

从第一个字符开始扫描

当遇见普通字符时忽略，

当遇见左符号时压入栈中

当遇见右符号时从栈中弹出栈顶符号，并进行匹配

匹配成功：继续读入下一个字符

匹配失败：立即停止，并报错

结束

成功：所有字符扫描完毕，且栈为空

失败：匹配失败或所有字符扫描完毕但栈非空

总结

赶时间、有空再弄吧。。

队列（Queue）

队列基本概念

队列是一种特殊的受限制的线性表

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出的（First in First out）的线性表，简称FIFO。允许插入的一端为队尾，允许删除的一端为队头。队列不允许中间操作

在这里插入图片描述

队列的顺序存储

https://www.bilibili.com/video/BV13b411V73v?p=292

队列的链式存储

https://www.bilibili.com/video/BV13b411V73v?p=294

在这里插入图片描述

树

在这里插入图片描述

定义

由一个或多个（n>=U）节点组成的有限集合，有且仅有一个节点称为根（root），当n>1时，其余的节点分为m（m>-0）个互不相交的有限集合T1,T2,…,Tm。每个集合本身又是棵树，被称作这个根的子树。

树的结构特点

非线性结构，有一个直接前驱，但可以有多个直接后继（1:n）

树的定义具有递归性，树中还有树。

树可以为空，即节点个数为0.

若干术语

根 ⇒ 即根节点（没有前驱）

叶子 ⇒ 即终端节点（没有后继）

森林 ⇒ 指m棵不相交的树的集合（例如删除A后的子树个数）

有序树 ⇒ 节点各子树从左至右有序，不能互换（左为第一）

无序树 ⇒ 节点各子树可互换位置。

双亲 ⇒ 即上层的那个节点（直接前驱）parent

孩子 ⇒ 即下层节点的子树（直接后继）child

兄弟 ⇒ 同一双亲下的同层节点（孩子之间互称兄弟） sibling

堂兄弟 ⇒ 即双亲位于同一层的节点（但并非同一双亲） cousin

祖先 ⇒ 即从根到该节点所经分支的所有节点

子孙 ⇒ 即该节点下层子树中的任一节点

节点 ⇒ 即树的数据元素

节点的度 ⇒ 节点挂接的子树个数（有几个直接后继就是几度）

节点的层次 ⇒ 从根到该节点的层数（根节点算第一层）

终端节点 ⇒ 即度为0的节点，即叶子

分支节点 ⇒ 除树根以外的节点（也称为内部节点）

树的深度（高度） ⇒ 指所有节点中的最大层数（Max（各节点的层次））

上图的节点数13、度3、深度4

树的表示法

图形表示法

事物之间的逻辑关系可以通过树的形式很直观的表示出来

广义表示法

在这里插入图片描述

中国（河北（保定，石家庄），广东（广州，东莞），山东（青岛，济南））

根作为子树森林组成的表的名字写在表的左边

左孩子右兄弟表示法

在这里插入图片描述

左孩子右兄弟表示法可以将一颗多叉树转化为一颗二叉树

在这里插入图片描述

节点结构：

在这里插入图片描述

节点有两个指针域，其中一个指针指向子节点，另一个指针指向其兄弟节点。

二叉树

定义

n（n>=0）个节点的有限集合，由一个根节点以及两棵互不相交的二叉树组成。

逻辑结构

（1：2）

基本特征

每个节点最多只有两颗子树（不存在度大于2的节点）

左子树和右子树次序不能颠倒（有序树）

基本形态

在这里插入图片描述

二叉树性质

在二叉树的第i层有至多2^i-1个节点（i>0）

深度为k的二叉树至多有2^k-1个节点（k>0）

对于任何一颗二叉树，若深度为2的节点数有n₂个，则叶子数（n₀）必定为n₂+1
（n₀=n₂+1）

具有n个节点的完全二叉树的深度必为 $log_{2}n|+1$

对于完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲的编号必为i/2(i=1时为根除外)

使用此性质可以使用完全二叉树实现树的顺序存储
如果不是完全二叉树咋整？？
将其转换为完全二叉树即可

概念解释

满二叉树
一颗深度为k且有2^k-1个节点的二叉树
特点：每层都“充满”了节点

完全二叉树
除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干节点。

二叉树的遍历

定义

指按某条搜索路线访问遍访每个节点且不重复

遍历用途

它是树结构插入、删除、修改、查询和排序运算的前提，是二叉树一切运算的基础和核心

遍历方法

牢记一种约定对每个节点遍历都是“先左后右”

限定先左后右，树的遍历有三种实现方案：

DLR – 先序遍历，即先根再左再右

LDR – 中序遍历，即先左再根再右

LRD – 后序遍历，即先左再右再根

实现

在这里插入图片描述

C视频

转载地址：https://lawsssscat.blog.csdn.net/article/details/102987071 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：（回收站）Comparator

下一篇：Java培优班-第七天 - JavaSE -（面向对象）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

文章目录

链表（思路一）

初始化

插入、删除（add_next、remove_next）

链表（思路二）

动态数组

（C实现一）

（C++实现一）（无泛型）【未实现】

栈（stack）

栈的顺序存储

实现一：数组实现

栈的链式存储

实现二：链表实现【待实现】

栈的应用（案例）【待完成】

就近匹配

队列（Queue）

队列基本概念

队列的顺序存储

队列的链式存储

树

树的表示法

图形表示法

广义表示法

左孩子右兄弟表示法

二叉树

概念解释

二叉树的遍历

实现

发表评论

最新留言

关于作者

推荐文章