下载文档原格式
二叉树的建立与基本操作二叉树是一种特殊的树形结构，它由节点（node）组成，每个节点最多有两个子节点。
二叉树的基本操作包括建立二叉树、遍历二叉树、查找二叉树节点、插入和删除节点等。
本文将详细介绍二叉树的建立和基本操作，并给出相应的代码示例。
一、建立二叉树建立二叉树有多种方法，包括使用数组、链表和前序、中序、后序遍历等。
下面以使用链表的方式来建立二叉树为例。
1.定义二叉树节点类首先，定义一个二叉树节点的类，包含节点值、左子节点和右子节点三个属性。
```pythonclass Node:def __init__(self, value):self.value = valueself.left = Noneself.right = None```2.建立二叉树使用递归的方法来建立二叉树，先构造根节点，然后递归地构造左子树和右子树。
```pythondef build_binary_tree(lst):if not lst: # 如果 lst 为空，则返回 Nonereturn Nonemid = len(lst) // 2 # 取 lst 的中间元素作为根节点的值root = Node(lst[mid])root.left = build_binary_tree(lst[:mid]) # 递归构造左子树root.right = build_binary_tree(lst[mid+1:]) # 递归构造右子树return root```下面是建立二叉树的示例代码：```pythonlst = [1, 2, 3, 4, 5, 6, 7]root = build_binary_tree(lst)```二、遍历二叉树遍历二叉树是指按照其中一规则访问二叉树的所有节点，常见的遍历方式有前序遍历、中序遍历和后序遍历。
1.前序遍历前序遍历是指先访问根节点，然后访问左子节点，最后访问右子节点。
```pythondef pre_order_traversal(root):if root:print(root.value) # 先访问根节点pre_order_traversal(root.left) # 递归访问左子树pre_order_traversal(root.right) # 递归访问右子树```2.中序遍历中序遍历是指先访问左子节点，然后访问根节点，最后访问右子节点。
二叉树的创建和初始化步骤一、确定二叉树的节点数首先，我们需要确定二叉树中节点的数量。
这可以通过输入用户的需求来确定，或者根据具体的问题背景和数据结构要求来确定。
二、确定节点的值接下来，我们需要为每个节点分配一个唯一的值。
这些值可以是数字、字符或其他数据类型，具体取决于我们的需求和应用场景。
三、创建根节点在确定了节点数和节点值之后，我们可以开始创建二叉树的根节点。
根节点是二叉树中最重要的节点，它没有父节点，并且存储了整个二叉树的信息。
四、初始化二叉树接下来，我们需要初始化二叉树。
这包括为每个节点分配内存空间，并将其初始化为一个空节点。
在初始化过程中，我们需要为每个节点分配一个唯一的位置，以便后续的插入和删除操作。
五、构建左子树接下来，我们需要构建二叉树的左子树。
这可以通过递归地插入节点来完成。
在插入节点时，我们需要判断节点的左子节点是否为空，如果不为空则插入到右子树中。
在构建左子树时，我们需要遵循二叉树的性质，确保左子树的所有节点的值小于根节点的值。
六、构建右子树类似地，我们需要构建二叉树的右子树。
在构建右子树时，我们需要遵循二叉树的性质，确保右子树的所有节点的值大于根节点的值。
我们可以通过递归地插入节点来完成右子树的构建。
七、插入节点如果需要向二叉树中插入新的节点，我们可以按照以下步骤进行：1. 首先，我们需要找到要插入新节点的位置。
这可以通过递归地搜索二叉树来完成。
在搜索过程中，我们需要判断当前节点的左子节点和右子节点是否为空，如果为空则插入新节点，如果不为空则继续搜索。
2. 插入新节点时，我们需要更新节点的指针和引用计数器。
指针指向新节点，引用计数器加一。
同时，我们需要调整父节点的指针，指向新节点。
3. 最后，我们需要重新平衡二叉树，以确保其保持平衡和高效性能。
平衡二叉树的方法有很多种，包括AVL树、红黑树等。
八、遍历二叉树遍历二叉树是另一种重要的操作。
遍历可以帮助我们更好地理解二叉树的构造和结构，并能够更好地应用和处理二叉树中的数据。
数据结构⼊门-树的遍历以及⼆叉树的创建树定义：1. 有且只有⼀个称为根的节点2. 有若⼲个互不相交的⼦树，这些⼦树本⾝也是⼀个树通俗的讲：1. 树是有结点和边组成，2. 每个结点只有⼀个⽗结点，但可以有多个⼦节点3. 但有⼀个节点例外，该节点没有⽗结点，称为根节点⼀、专业术语结点、⽗结点、⼦结点、根结点深度：从根节点到最底层结点的层数称为深度，根节点第⼀层叶⼦结点：没有⼦结点的结点⾮终端节点：实际上是⾮叶⼦结点度：⼦结点的个数成为度⼆、树的分类⼀般树：任意⼀个结点的⼦结点的个数都不受限制⼆叉树：任意⼀个结点的⼦结点个数最多是两个，且⼦结点的位置不可更改⼆叉数分类：1. ⼀般⼆叉数2. 满⼆叉树：在不增加树层数的前提下，⽆法再多添加⼀个结点的⼆叉树3. 完全⼆叉树：如果只是删除了满⼆叉树最底层最右边的连续若⼲个结点，这样形成的⼆叉树就是完全⼆叉树森林：n个互不相交的树的集合三、树的存储⼆叉树存储连续存储(完全⼆叉树)优点：查找某个结点的⽗结点和⼦结点(也包括判断有没有⼦结点)速度很快缺点：耗⽤内存空间过⼤链式存储⼀般树存储1. 双亲表⽰法：求⽗结点⽅便2. 孩⼦表⽰法：求⼦结点⽅便3. 双亲孩⼦表⽰法：求⽗结点和⼦结点都很⽅便4. ⼆叉树表⽰法：把⼀个⼀般树转化成⼀个⼆叉树来存储，具体转换⽅法：设法保证任意⼀个结点的左指针域指向它的第⼀个孩⼦，右指针域指向它的兄弟，只要能满⾜此条件，就可以把⼀个⼀般树转化为⼆叉树⼀个普通树转换成的⼆叉树⼀定没有右⼦树森林的存储先把森林转化为⼆叉树，再存储⼆叉树四、树的遍历先序遍历：根左右先访问根结点，再先序访问左⼦树，再先序访问右⼦树中序遍历：左根右中序遍历左⼦树，再访问根结点，再中序遍历右⼦树后续遍历：左右根后续遍历左⼦树，后续遍历右⼦树，再访问根节点五、已知两种遍历求原始⼆叉树给定了⼆叉树的任何⼀种遍历序列，都⽆法唯⼀确定相应的⼆叉树，但是如果知道了⼆叉树的中序遍历序列和任意的另⼀种遍历序列，就可以唯⼀地确定⼆叉树已知先序和中序求后序先序：ABCDEFGH中序：BDCEAFHG求后序：这个⾃⼰画个图体会⼀下就可以了，⾮常简单，这⾥简单记录⼀下1. ⾸先根据先序确定根，上⾯的A就是根2. 中序确定左右，A左边就是左树(BDCE)，A右边就是右树(FHG)3. 再根据先序，A左下⾯就是B，然后根据中序，B左边没有，右边是DCE4. 再根据先序，B右下是C，根据中序，c左下边是D，右下边是E，所以整个左树就确定了5. 右树，根据先序，A右下是F，然后根据中序，F的左下没有，右下是HG，6. 根据先序，F右下为G，然后根据中序，H在G的左边，所以G的左下边是H再来⼀个例⼦，和上⾯的思路是⼀样的，这⾥就不详细的写了先序：ABDGHCEFI中序：GDHBAECIF已知中序和后序求先序中序：BDCEAFHG后序：DECBHGFA这个和上⾯的思路是⼀样的，只不过是反过来找，后序找根，中序找左右树简单应⽤树是数据库中数据组织⼀种重要形式操作系统⼦⽗进程的关系本⾝就是⼀棵树⾯向对象语⾔中类的继承关系哈夫曼树六、⼆叉树的创建#include <stdio.h>#include <stdlib.h>typedef struct Node{char data;struct Node * lchild;struct Node * rchild;}BTNode;/*⼆叉树建⽴*/void BuildBT(BTNode ** tree){char ch;scanf("%c" , &ch); // 输⼊数据if(ch == '#') // 如果这个节点的数据是#说明这个结点为空*tree = NULL;else{*tree = (BTNode*)malloc(sizeof(BTNode));//申请⼀个结点的内存 (*tree)->data = ch; // 将数据写⼊到结点⾥⾯BuildBT(&(*tree)->lchild); // 递归建⽴左⼦树BuildBT(&(*tree)->rchild); // 递归建⽴右⼦树}}/*⼆叉树销毁*/void DestroyBT(BTNode *tree) // 传⼊根结点{if(tree != NULL){DestroyBT(tree->lchild);DestroyBT(tree->rchild);free(tree); // 释放内存空间}}/*⼆叉树的先序遍历*/void Preorder(BTNode * node){if(node == NULL)return;else{printf("%c ",node->data );Preorder(node->lchild);Preorder(node->rchild);}}/*⼆叉树的中序遍历*/void Inorder(BTNode * node){if(node == NULL)return;else{Inorder(node->lchild);printf("%c ",node->data );Inorder(node->rchild);}}/*⼆叉树的后序遍历*/void Postorder(BTNode * node){if(node == NULL)return;else{Postorder(node->lchild);Postorder(node->rchild);printf("%c ",node->data );}}/*⼆叉树的⾼度树的⾼度 = max(左⼦树⾼度，右⼦树⾼度) +1*/int getHeight(BTNode *node){int Height = 0;if (node == NULL)return 0;else{int L_height = getHeight(node->lchild);int R_height = getHeight(node->rchild);Height = L_height >= R_height ? L_height +1 : R_height +1; }return Height;}int main(int argc, char const *argv[]){BTNode * BTree; // 定义⼀个⼆叉树printf("请输⼊⼀颗⼆叉树先序序列以#表⽰空结点:");BuildBT(&BTree);printf("先序序列：");Preorder(BTree);printf("\n中序序列：");Inorder(BTree);printf("\n后序序列：");Postorder(BTree);printf("\n树的⾼度为：%d" , getHeight(BTree));return 0;}// ABC##DE##F##G##。
数据结构中的双向链表实现和应用场景双向链表是一种常用的数据结构，它在许多实际应用中都发挥着重要的作用。
本文将介绍双向链表的实现原理以及一些常见的应用场景。
一、双向链表的实现原理双向链表由一系列节点组成，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。
相比于单向链表，双向链表可以实现双向遍历，提高了一些操作的效率。
1.1 节点定义双向链表的节点通常由数据域和两个指针域组成，例如：```struct Node {int data; // 节点数据Node* prev; // 前一个节点指针Node* next; // 后一个节点指针};```1.2 插入操作在双向链表中插入一个节点可以分为两种情况：在表头插入和在表尾插入。
在表头插入时，只需修改原来头节点的prev指针为新节点的地址，并将新节点的next指针指向原头节点即可。
在表尾插入时，需要先找到原来的尾节点，然后将尾节点的next指针指向新节点的地址，并将新节点的prev指针指向尾节点的地址。
1.3 删除操作删除操作与插入操作类似，同样分为在表头和表尾删除节点。
在表头删除时，只需将头节点的next指针指向新的头节点，同时将新头节点的prev指针置为空。
在表尾删除时，需要先找到尾节点的前一个节点，然后将该节点的next指针置为空。
1.4 查找操作双向链表支持从前向后和从后向前两种遍历方式。
从前向后遍历时，我们可以利用节点的next指针不断向后遍历得到所有节点。
同样，从后向前遍历时，可以利用节点的prev指针不断向前遍历得到所有节点。
二、双向链表的应用场景双向链表广泛应用于各种软件和系统中，下面列举了一些常见的应用场景。
2.1 浏览器的历史记录在浏览器中，经常需要记录用户浏览过的网页历史记录。
这时可以使用双向链表来实现。
每当用户访问一个新的网页，就在双向链表中插入一个新节点，同时将新节点的next指针指向前一个节点，prev指针指向后一个节点。
C 语⾔数据结构之⼆叉链表创建⼆叉树⽬录⼀、思想（先序思想创建）⼆、创建⼆叉树(1)传⼀级参数⽅法(2)传⼆级参数⽅法⼀、思想（先序思想创建）第⼀步先创建根节点,然后创建根节点左⼦树,开始递归创建左⼦树，直到递归创建到的节点下不继续创建左⼦树，也就是当下递归到的节点下的左⼦树指向NULL ，结束本次左⼦树递归，返回这个节点的上⼀个节点，开始创建右⼦树，然后⼜开始以当下这个节点，继续递归创建左⼦树，左⼦树递归创建完，就递归创建右⼦树，直到递归结束返回到上⼀级指针节点（也就是根节点下），此时根节点左边⼦树创建完毕，开始创建右边⼦树，原理和根节点左边创建左右⼦树相同⼆、创建⼆叉树⼆叉树的操作通常使⽤递归⽅法，如果递归不太明⽩，建议去对此进⾏⼀下学习和练习。
⼆叉树的操作可以分为两类，⼀类是需要改变⼆叉树的结构的，⽐如⼆叉树的创建、节点删除等等，这类操作，传⼊的⼆叉树的节点参数为⼆叉树指针的地址，这种参⼊传⼊，便于更改⼆叉树结构体的指针（即地址）。
这⾥稍微有⼀点点绕，可能需要多思考⼀下如下是⼆叉数创建的函数，这⾥我规定，节点值为整数，如果输⼊的数为-1，则表⽰结束继续往下创建⼦节点的操作。
然后我们使⽤递归的⽅法以此创建左⼦树和右⼦树为了更⽅便的使⽤⼆叉树结构体，可以使⽤ typedef 对结构体进⾏命名123456typedef struct Tree{int data; // 存放数据域struct Tree *lchild; // 遍历左⼦树指针struct Tree *rchild; // 遍历右⼦树指针}Tree,*BitTree;这⾥展⽰两种传参类型的创建⽅法，其中深意可多次参考理解，加深指针理解(1)传⼀级参数⽅法123456789101112131415161718BitTree CreateLink(){ int data; int temp; BitTree T;scanf("%d",&data); // 输⼊数据temp=getchar(); // 吸收空格if(data == -1){ // 输⼊-1 代表此节点下⼦树不存数据，也就是不继续递归创建 return NULL; }else{ T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间T->data = data; // 把当前输⼊的数据存⼊当前节点指针的数据域中printf("请输⼊%d 的左⼦树: ",data);T->lchild = CreateLink(); // 开始递归创建左⼦树192021222324printf("请输⼊%d 的右⼦树: ",data);T->rchild = CreateLink(); // 开始到上⼀级节点的右边递归创建左右⼦树return T; // 返回根节点 } }(2)传⼆级参数⽅法123456789101112131415161718192021222324252627282930BitTree CreateLink(BitTree *T) // 次数 T 为指向根节点的指针的地址{ int data; scanf("%d",&data); if(data == -1){*T=NULL; // 结束递归时，让指针当前节点的指针地址的 指针 指向NULL}else{*T = (BitTree)malloc(sizeof(Tree)); // 对指向节点指针地址的指针 分配内存 if(!(*T) ){ // *T = NULL 表⽰分配内存失败，也就是结束递归创建了 printf("内存分配失败\n");exit(-1);}(*T)->data = data; // 给节点指针地址内的数据域，存⼊数据 printf("请输⼊%d 的左⼦树: ",data); CreateLink(&(*T)->lchild); // 开始遍历左⼦树printf("请输⼊%d 的右⼦树: ",data);CreateLink(&(*T)->rchild); // 开始遍历右⼦树，遍历的思想⽂章开头处解释} }1234567891011121314#include<stdio.h>#include<stdlib.h> typedef struct Tree{ int data; // 存放数据域 struct Tree *lchild; // 遍历左⼦树指针 struct Tree *rchild; // 遍历右⼦树指针 }Tree,*BitTree;151617181920212223242526272829303132333435363738394041424344454647484950515253545556BitTree CreateLink(){int data; int temp; BitTree T; scanf("%d",&data); // 输⼊数据 temp=getchar(); // 吸收空格if(data == -1){ // 输⼊-1 代表此节点下⼦树不存数据，也就是不继续递归创建return NULL;}else{T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间 T->data = data; // 把当前输⼊的数据存⼊当前节点指针的数据域中 printf("请输⼊%d 的左⼦树: ",data); T->lchild = CreateLink(); // 开始递归创建左⼦树printf("请输⼊%d 的右⼦树: ",data);T->rchild = CreateLink(); // 开始到上⼀级节点的右边递归创建左右⼦树 return T; // 返回根节点 } } void ShowXianXu(BitTree T) // 先序遍历⼆叉树{if(T==NULL){return; } printf("%d ",T->data);ShowXianXu(T->lchild); // 递归遍历左⼦树ShowXianXu(T->rchild); // 递归遍历右⼦树} int main(){ BitTree S;printf("请输⼊第⼀个节点的数据:\n");S = CreateLink(); // 接受创建⼆叉树完成的根节点ShowXianXu(S); // 先序遍历⼆叉树 return 0; }123456789101112131415#include<stdio.h>#include<stdlib.h>typedef struct Tree{int data;struct Tree *lchild;struct Tree *rchild;}Tree,*BitTree; BitTree CreateLink(BitTree *T) // 次数 T 为指向根节点的指针的地址{ int data;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 51 52 53 54 55 56 57 58 59 60 61 scanf("%d",&data);if(data == -1){*T=NULL; // 结束递归时，让指针当前节点的指针地址的指针指向NULL }else{*T = (BitTree)malloc(sizeof(Tree)); // 对指向节点指针地址的指针分配内存if(!(*T) ){ // *T = NULL 表⽰分配内存失败，也就是结束递归创建了printf("内存分配失败\n");exit(-1);}(*T)->data = data; // 给节点指针地址内的数据域，存⼊数据printf("请输⼊%d的左⼦树: ",data);CreateLink(&(*T)->lchild); // 开始遍历左⼦树printf("请输⼊%d的右⼦树: ",data);CreateLink(&(*T)->rchild); // 开始遍历右⼦树，遍历的思想⽂章开头处解释}}void ShowXianXu(BitTree T) // 先序遍历⼆叉树{if(T==NULL){return;}printf("%d ",T->data);ShowXianXu(T->lchild); // 遍历左⼦树ShowXianXu(T->rchild); // 遍历右⼦树}int main(){BitTree *S; // 创建指向这个结构体指针地址的指针printf("请输⼊第⼀个节点的数据:\n");CreateLink(&S); // 传⼆级指针地址ShowXianXu(S);return0;}到此这篇关于C语⾔数据结构之⼆叉链表创建⼆叉树的⽂章就介绍到这了,更多相关C语⾔⼆叉链表创建⼆叉树内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！。
二叉树的基本操作与实现实验报告二叉树是一种重要的数据结构，在计算机科学领域中被广泛应用。
本实验将介绍二叉树的基本操作与实现，并给出相应的实验报告。
一、引言二叉树是一种特殊的树状结构，每个节点至多有两个子节点。
二叉树有许多重要的特性，如平衡二叉树、二叉树等，应用广泛。
在本实验中，我们将介绍二叉树的基本操作和实现。
二、实验目的1.掌握二叉树的基本概念和特性；2.熟悉二叉树的基本操作，包括创建、插入、删除、遍历等；3.学会使用编程语言实现二叉树的基本操作。
三、实验内容本实验主要包括以下内容：1.二叉树的定义和基本概念；2.二叉树的基本操作，包括创建、插入、删除、遍历等；3.使用编程语言实现二叉树的基本操作；4.测试和验证二叉树的基本操作的正确性。
四、实验步骤1.二叉树的定义和基本概念二叉树是一种树状结构，每个节点至多有两个子节点。
二叉树的每个节点包含一个数据项和指向左子树和右子树的指针。
二叉树的特性有很多，如完全二叉树、平衡二叉树、二叉树等。
2.二叉树的基本操作（1）创建二叉树：可以通过手动输入节点数据来创建二叉树，也可以通过读取文件中的数据来创建二叉树。
（2）插入节点：在指定位置插入一个新节点。
（3）删除节点：删除指定位置的节点。
（4）遍历二叉树：有前序遍历、中序遍历和后序遍历三种遍历方式。
3.使用编程语言实现二叉树的基本操作实现二叉树的基本操作可以使用编程语言来完成。
我们可以定义一个二叉树的结构体，包含节点数据和指向左右子树的指针。
然后根据具体的需求，实现相应的操作函数。
4.测试和验证二叉树的基本操作的正确性在完成二叉树的基本操作后，我们可以编写测试代码来验证操作的正确性。
通过创建二叉树，并进行插入、删除和遍历操作，观察输出结果是否符合预期。
五、实验结果与分析在完成二叉树的基本操作后，我们可以进行测试和验证。
通过输出二叉树的遍历结果，比对预期结果来判断操作是否正确。
同时，我们还可以观察二叉树的结构和特性，如是否满足平衡二叉树或二叉树的条件。
二叉树的基本操作实验报告二叉树的基本操作实验报告引言：二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。
二叉树的基本操作包括创建、遍历、插入和删除等。
本实验旨在通过实践来深入了解二叉树的基本操作，并通过实验结果验证其正确性和有效性。
一、创建二叉树创建二叉树是二叉树操作中的第一步。
在本实验中，我们使用了递归算法来创建二叉树。
递归算法是一种重要的算法思想，通过将问题划分为更小的子问题来解决复杂的问题。
在创建二叉树时，我们首先创建根节点，然后递归地创建左子树和右子树。
二、遍历二叉树遍历二叉树是对二叉树中的每个节点进行访问的过程。
常见的遍历方式有前序遍历、中序遍历和后序遍历。
前序遍历先访问根节点，然后递归遍历左子树和右子树；中序遍历先递归遍历左子树，然后访问根节点，最后递归遍历右子树；后序遍历先递归遍历左子树和右子树，最后访问根节点。
三、插入节点插入节点是向二叉树中添加新节点的操作。
插入节点的过程需要遵循二叉树的特性，即左子节点的值小于父节点的值，右子节点的值大于父节点的值。
在插入节点时，我们需要找到合适的位置，将新节点插入到正确的位置上。
四、删除节点删除节点是从二叉树中移除节点的操作。
删除节点的过程相对复杂，需要考虑多种情况。
如果要删除的节点是叶子节点，直接删除即可。
如果要删除的节点只有一个子节点，将其子节点连接到父节点上。
如果要删除的节点有两个子节点，我们需要找到其后继节点或前驱节点来替代被删除的节点。
实验结果：通过实验，我们成功地实现了二叉树的基本操作。
创建二叉树的递归算法能够正确地创建出符合要求的二叉树。
遍历二叉树的算法能够按照指定的顺序遍历每个节点。
插入节点和删除节点的操作也能够正确地修改二叉树的结构。
讨论与总结：二叉树的基本操作是数据结构中的重要内容，对于理解和应用其他数据结构具有重要意义。
通过本次实验，我们深入了解了二叉树的创建、遍历、插入和删除等操作，并通过实验验证了其正确性和有效性。
数据结构实验报告T1223-3-21余帅实验一实验题目：仅仅做链表部分难度从上到下1.双向链表，带表头，线性表常规操作。
2.循环表，带表头，线性表常规操作。
3.单链表，带表头，线性表常规操作。
实验目的：了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。
实验要求：常规操作至少有：1.数据输入或建立2.遍历3.插入4.删除必须能多次反复运行实验主要步骤：1、分析、理解给出的示例程序。
2、调试程序，并设计输入数据，测试程序的如下功能：1.数据输入或建立2.遍历3.插入4.删除单链表示意图：headhead head 创建删除双向循环链表示意图：创建程序代码://单链表#include<iostream.h>#include<windows.h>const MAX=5;enum returninfo{success,fail,overflow,underflow,range_error}; int defaultdata[MAX]={11,22,33,44,55};class node{public:int data;node *next;};class linklist{private:node *headp;protected:int count;public:linklist();~linklist();bool empty();void clearlist();returninfo create(void);returninfo insert(int position,const int &item);returninfo remove(int position) ;returninfo traverse(void);};linklist::linklist(){headp = new node;headp->next = NULL;count=0;}linklist::~linklist(){clearlist();delete headp;}bool linklist::empty(){if(headp->next==NULL)return true;elsereturn false;}void linklist::clearlist(){node *searchp=headp->next,*followp=headp;while(searchp->next!=NULL){followp=searchp;searchp=searchp->next;delete followp;}headp->next = NULL;count = 0;}returninfo linklist::create(){node *searchp=headp,*newnodep;for(int i=0;i<MAX;i++){newnodep = new node;newnodep->data = defaultdata[i];newnodep->next = NULL;searchp->next = newnodep;searchp = searchp->next;count++;}searchp->next = NULL;traverse();return success;}returninfo linklist::insert(int position,const int &item) //插入一个结点{if(position<=0 || position>=count)return range_error;node *newnodep=new node,*searchp=headp->next,*followp=headp;for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}newnodep->data=item; //给数据赋值newnodep->next=followp->next; //注意此处的次序相关性followp->next=newnodep;count++; //计数器加一return success;}returninfo linklist::remove(int position) //删除一个结点{if(empty())return underflow;if(position<=0||position>=count+1)return range_error;node *searchp=headp->next,*followp=headp; //这里两个指针的初始值设计一前一后for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}followp->next=searchp->next; //删除结点的实际语句delete searchp; //释放该结点count--; //计数器减一return success;}returninfo linklist::traverse(void){node *searchp;if(empty())return underflow;searchp = headp->next;cout<<"连表中的数据为："<<endl;while(searchp!=NULL){cout<<searchp->data<<" ";searchp = searchp->next;}cout<<endl;return success;}class interfacebase{public:linklist listface; //定义一个对象Cskillstudyonfacevoid clearscreen(void);void showmenu(void);void processmenu(void);};void interfacebase::clearscreen(void){system("cls");}void interfacebase::showmenu(void){cout<<"================================"<<endl;cout<<" 功能菜单 "<<endl;cout<<" 1.创建链表 "<<endl;cout<<" 2.增加结点 "<<endl;cout<<" 3.删除结点 "<<endl;cout<<" 4.遍历链表 "<<endl;cout<<" 0.结束程序 "<<endl;cout<<"======================================"<<endl;cout<<"请输入您的选择：";}void interfacebase::processmenu(void){int returnvalue,item,position;char menuchoice;cin >>menuchoice;switch(menuchoice) //根据用户的选择进行相应的操作{case '1':returnvalue=listface.create();if(returnvalue==success)cout<<"链表创建已完成"<<endl;break;case '2':cout<<"请输入插入位置："<<endl;cin>>position;cout<<"请输入插入数据："<<endl;cin>>item;returnvalue = listface.insert(position,item);if(returnvalue==range_error)cout<<"数据个数超出范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '3':cout<<"输入你要删除的位置："<<endl;cin>>position;returnvalue = listface.remove(position);if(returnvalue==underflow)cout<<"链表已空"<<endl;else if(returnvalue==range_error)cout<<"删除的数据位置超区范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '4':listface.traverse();break;case '0':cout<<endl<<endl<<"您已经成功退出本系统，欢迎再次使用!!!"<<endl;system("pause");exit(1);default:cout<<"对不起，您输入的功能编号有错!请重新输入!!!"<<endl;break;}}void main(){interfacebase interfacenow;linklist listnow;system("color f0");interfacenow.clearscreen();while(1){interfacenow.showmenu();interfacenow.processmenu();system("pause");interfacenow.clearscreen();}}/* 功能：用双向循环链表存储数据1.创建链表2.增加结点3.删除结点4.遍历链表制作人：余帅内容：239行*/#include<iostream.h>#include<windows.h>const MAX=5;enum returninfo{success,fail,overflow,underflow,range_error}; int defaultdata[MAX]={11,22,33,44,55};class node{public:int data;node * next; //指向后续节点node * pre; //指向前面的节点};class linklist{private:node *headp;protected:int count;public:linklist();~linklist();bool empty();void clearlist();returninfo create(void);returninfo insert(int position,const int &item);returninfo remove(int position) ;returninfo traverse(void);};linklist::linklist(){headp = new node;headp->next = NULL;headp->pre = NULL;count=0;}linklist::~linklist(){clearlist();delete headp;}bool linklist::empty(){if(headp->next==NULL)return true;elsereturn false;}void linklist::clearlist(){node *searchp=headp->next,*followp=headp;while(searchp->next!=NULL){followp=searchp;searchp=searchp->next;delete followp;}headp->next = NULL;headp->pre = NULL;count = 0;}returninfo linklist::create(){node *searchp=headp,*newnodep;for(int i=0;i<MAX;i++){newnodep = new node;newnodep->data = defaultdata[i];newnodep->next = NULL;searchp->next = newnodep;newnodep->pre = searchp;searchp = searchp->next;count++;}searchp->next = headp;headp->pre = searchp;traverse();return success;}returninfo linklist::insert(int position,const int &item) //插入一个结点{if(position<=0 || position>count+1)return range_error;node *newnodep=new node;node *searchp=headp->next,*followp=headp;for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}newnodep->data=item; //给数据赋值newnodep->next = searchp;searchp->pre = newnodep;followp->next = newnodep;newnodep->pre = followp;count++; //计数器加一return success;}returninfo linklist::remove(int position) //删除一个结点{if(empty())return underflow;if(position<=0||position>=count+1)return range_error;node *searchp=headp->next,*followp=headp; //这里两个指针的初始值设计一前一后for(int i=1; i<position && searchp!=NULL;i++){followp=searchp;searchp=searchp->next;}followp->next=searchp->next; //删除结点的实际语句searchp->next->pre = followp;delete searchp; //释放该结点count--; //计数器减一return success;}returninfo linklist::traverse(void){node *searchp1,*searchp2;if(empty())return underflow;searchp1 = headp;searchp2 = headp;cout<<"连表中的数据为："<<endl;cout<<"从左至右读取：";while (searchp1->next!=headp ) {searchp1 = searchp1 ->next;cout << searchp1->data<<" ";}cout<<endl;cout<<"从右至左读取：";while (searchp2->pre!=headp ) {searchp2 = searchp2 ->pre;cout << searchp2->data<<" ";}cout<<endl;return success;}class interfacebase{public:linklist listface; //定义一个对象Cskillstudyonface void clearscreen(void);void showmenu(void);void processmenu(void);};void interfacebase::clearscreen(void){system("cls");}void interfacebase::showmenu(void){cout<<"================================"<<endl;cout<<" 功能菜单 "<<endl;cout<<" 1.创建链表 "<<endl;cout<<" 2.增加结点 "<<endl;cout<<" 3.删除结点 "<<endl;cout<<" 4.遍历链表 "<<endl;cout<<" 0.结束程序 "<<endl;cout<<"======================================"<<endl;cout<<"请输入您的选择：";}void interfacebase::processmenu(void){int returnvalue,item,position;char menuchoice;cin >>menuchoice;switch(menuchoice) //根据用户的选择进行相应的操作{case '1':returnvalue=listface.create();if(returnvalue==success)cout<<"链表创建已完成"<<endl;break;case '2':cout<<"请输入插入位置："<<endl;cin>>position;cout<<"请输入插入数据："<<endl;cin>>item;returnvalue = listface.insert(position,item);if(returnvalue==range_error)cout<<"数据个数超出范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '3':cout<<"输入你要删除的位置："<<endl;cin>>position;returnvalue = listface.remove(position);if(returnvalue==underflow)cout<<"链表已空"<<endl;else if(returnvalue==range_error)cout<<"删除的数据位置超区范围"<<endl;elsecout<<"操作成功！！！"<<endl;break;case '4':listface.traverse();break;case '0':cout<<endl<<endl<<"您已经成功退出本系统，欢迎再次使用!!!"<<endl;system("pause");exit(1);default:cout<<"对不起，您输入的功能编号有错!请重新输入!!!"<<endl;break;}}void main(){interfacebase interfacenow;linklist listnow;system("color f0");interfacenow.clearscreen();while(1){interfacenow.showmenu();interfacenow.processmenu();system("pause");interfacenow.clearscreen();}}运行结果：1.创建链表：2.增加结点3．删除结点心得体会：本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。
二叉树操作实验报告一、实验背景二叉树是一种常用的数据结构，它由节点和连接节点的边组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。
在二叉树的操作中，常用的操作包括创建二叉树、插入节点、删除节点、查找节点、遍历等。
本次实验旨在通过对二叉树的操作，加强对二叉树数据结构的理解，并熟练掌握其操作方法。
二、实验目的1．掌握二叉树的创建方法，能够编写代码创建一个二叉树；2．了解二叉树的插入节点操作，掌握节点的插入方法；3．掌握二叉树的删除节点操作，了解节点删除的细节和方法；4．熟练掌握二叉树的查找节点操作；5．掌握二叉树的遍历方法，能够实现对二叉树的前序、中序、后序、层次遍历。
三、实验原理1．二叉树的创建方法：通过递归的方式，先创建根节点，再依次创建左子树和右子树；2．二叉树的插入节点操作：从根节点开始，根据节点值的大小关系，将待插入节点放到适当的位置；3．二叉树的删除节点操作：首先查找待删除的节点，然后根据其子节点的情况，进行相应的删除处理；4．二叉树的查找节点操作：从根节点开始遍历，根据节点值的大小关系，在左子树或右子树中继续查找，直到找到目标节点或遍历到叶子节点；5．二叉树的遍历方法：前序遍历先访问根节点，再遍历左子树和右子树；中序遍历先遍历左子树，再访问根节点和右子树；后序遍历先遍历左子树和右子树，再访问根节点；层次遍历按层次逐个访问节点。
四、实验过程1．创建二叉树：首先，定义二叉树的节点类，包含节点值和左右子节点；然后，通过递归的方式创建根节点、左子树和右子树。
2．插入节点：要插入一个节点，首先需要找到插入位置。
如果待插入节点大于当前节点的值，则插入到右子树中，否则插入到左子树中。
如果节点为空，则表示找到了插入位置。
3．删除节点：删除节点有以下几种情况：(1) 待删除节点为叶子节点：直接删除即可；(2) 待删除节点只有一个子节点：用子节点替换待删除节点的位置；(3) 待删除节点有两个子节点：找到待删除节点的后继节点（右子树的最左下角节点），用后继节点替换待删除节点的位置。
