链表与二叉树链表二叉树

113 阅读 0 评论 75 点赞

我是靠谱客的博主帅气鸵鸟，这篇文章主要介绍链表与二叉树链表二叉树，现在分享给大家，希望可以做个参考。

链表

链表是最基本的数据结构，链表是线性表的链式存储结构。每个结点不仅包含所存元素的信息，还包含元素之间的逻辑关系。
链表不支持随机访问，结点的存储空间利用率较顺序表稍低一些。在链表中插入删除元素无需移动元素，插入删除操作速度快，查询较顺序表速度慢

分类

单链表（循环单链表）

复制代码

1
2
3
4
5
6
typedef struct LNode
{
int Element;
struct Lnode *next;
}LinkList;

双链表（循环双链表）

复制代码

1
2
3
4
5
6
7
typedef struct DLNode
{
int Element;
struct DLnode *prior;
struct DLnode *next;
}DLinkList;

常用操作

头插法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
LinkList Creat_list(Linklist head) {
head = (Linklist)malloc(sizeof(LNode));
//
创建头节点
head->next = NULL;
Lnode *node = NULL;
//
定义新结点

node = head->next;
//
将最后一个结点的指针域永远保持为NULL
printf("Input the node number: ");
int count = 0 ;
scanf("%d", &count);
for (int i = 0; i < count; i++) {
node = (Linklist)malloc(sizeof(LNode));
node->data = i;
//
为新结点的数据域赋值
node->next = head->next;
//
将头结点的下一个结点的地址，赋给新创建结点的next 
head->next = node;
//
头结点下一个结点指针指向新插入结点
}
return head;
}

尾插法

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
LinkList Creat_list(Linklist head) {
head = (Linklist)malloc(sizeof(LNode));
//
为头指针开辟内存空间
head->next = NULL;
Linklist *end = NULL;
//
新增定义尾结点
Linklist *node = NULL;
//
定义结点

end = head;
//
未创建其余结点之前，只有一个头结点
printf("Input node number: ");
int count = 0 ;
scanf("%d", &count);
for (int i = 0; i < count; i++) {
node = (Linklist)malloc(sizeof(LNode));
//
为新结点开辟新内存
node->data = i;
end->next = node;
//新增结点插入在尾指针所指结点之后

end = node;
}
end->next = NULL;
}

删除指定元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 void deleteNode(LinkList *head,int pos) {
LNode* posNode=head->next;
LNode* posNodeFront=head;
if(posNode==NULL)
printf("链表为空！");
else{
while(posNode->data!=posData && posNode!=NULL){
posNodeFront=posNode;
posNode=posNodeFront->next;
}
if(posNode==NULL){
printf("无法找到指定位置");
return;
}
posNodeFront->next=posNode->next;
free(posNode);
}
}

二叉树

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

二叉树性质

1、二叉树中，第 i 层最多有 2i-1 个结点。
2、如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
3、二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1
深度为m的二叉树最多有2m-1个结点，最少有m个结点；

二叉树结构体

复制代码

1
2
3
4
5
6
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

二叉树的遍历方式（递归建立）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void PreOrderTraverse(BiTree T)//二叉树的先序遍历
{
if(T==NULL)
return ;
printf("%c ",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
void InOrderTraverse(BiTree T)//二叉树的中序遍历
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild);
printf("%c ",T->data);
InOrderTraverse(T->rchild);
}
void PostOrderTraverse(BiTree T)//后序遍历
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ",T->data);
}
void BinaryTreeLevelOrder(BiTNode* root) //层次遍历
{
Queue q;
//树为空，直接返回
if (root == NULL)
{
return;
}
QueueInit(&q);
//先将根节点入队
QueuePush(&q, root);
while (QueueEmpty(&q))
{
//出队保存队头并访问
BTNode* front = QueueFront(&q);
printf("%c", front->_data);
QueuePop(&q);
//将出队结点的左子树根入队
if (front->_left)
QueuePush(&q, front->_left);
//将出队结点的右子树根入队
if (front->_right)
QueuePush(&q, front->_right);
}
}