标签：数据结构

视频链接

构造一个二叉树，如图

使用递归的方式遍历此二叉树。

C语言实现代码：

#include <stdio.h>
#include <stdlib.h>

typedef int DataType;

typedef struct Node
{
    DataType data;                  //数据域
    struct Node * lchild;           //指向左孩子
    struct Node * rchild;           //指向右孩子
}BtNode;


//访问节点的函数
void visit(BtNode * node)
{
    printf("data = %d\n",node->data);
}

//先序遍历二叉树  根 - 左 - 右
void PreOrder(BtNode * root)
{
    if(root)
    {
       //访问根
       visit(root);
       PreOrder(root->lchild);          //先序遍历左子树
       PreOrder(root->rchild);          //先序遍历右子树
    }
}

int main()
{
    
    //构造一个二叉树

    BtNode * tree = (BtNode *)malloc(sizeof(BtNode));          //从内存中分配空间
    tree->data = 1;

    BtNode * node2 = (BtNode *)malloc(sizeof(BtNode));
    node2->data = 2;

    BtNode * node3 = (BtNode *)malloc(sizeof(BtNode));
    node3->data = 3;

    BtNode * node4 = (BtNode *)malloc(sizeof(BtNode));
    node4->data = 4;

    BtNode * node5 = (BtNode *)malloc(sizeof(BtNode));
    node5->data = 5;

    BtNode * node6 = (BtNode *)malloc(sizeof(BtNode));
    node6->data = 6;

    BtNode * node7 = (BtNode *)malloc(sizeof(BtNode));
    node7->data = 7;

    tree->lchild = node2;
    tree->rchild = node3;
    node2->lchild = node4;
    node2->rchild = node5;
    node3->lchild = NULL;
    node3->rchild = node6;
    node4->lchild = NULL;
    node4->rchild = NULL;
    node5->lchild = node7;
    node5->rchild = NULL;
    node6->lchild = NULL;
    node6->rchild = NULL;
    node7->lchild = NULL;
    node7->rchild = NULL;

    PreOrder(tree);

    return 0;
}

以上代码可在Linux中使用Gcc编译。

视频讲解

什么是线性表？线性表是一种线性结构，它是由n（n≥0）个元素组成的有穷序列。

顺序存储的实现方式：

• 定义一个固定长度的数组（数组的特点是存储空间连续，元素数据类型相同），将元素保存在数组中，通过数组的索引访问元素。
• 定义一个记录表长的变量

#define Maxsize 10             //数组最大长度

typedef struct {
	char data[Maxsize];	// 定义一个数组作为顺序存储
	int length;		// 记录当前顺序表长
}L;

顺序表的插入运算：

• 提前空出位置
• 将元素放在空出的位置
• 表长+1

视频内容：数据结构-内存2