下载文档原格式
二叉树的基本操作二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。
二叉树在计算机领域中得到广泛应用，它的基本操作包括插入、删除、查找、遍历等。
1.插入操作：二叉树的插入操作是将一个新的节点添加到已有的二叉树中的过程。
插入操作会按照一定规则将新节点放置在正确的位置上。
插入操作的具体步骤如下：-首先，从根节点开始，比较新节点的值与当前节点的值的大小关系。
-如果新节点的值小于当前节点的值，则将新节点插入到当前节点的左子树中。
-如果新节点的值大于当前节点的值，则将新节点插入到当前节点的右子树中。
-如果当前节点的左子树或右子树为空，则直接将新节点插入到该位置上。
-如果当前节点的左子树和右子树都不为空，则递归地对左子树或右子树进行插入操作。
2.删除操作：二叉树的删除操作是将指定节点从二叉树中删除的过程。
删除操作有以下几种情况需要考虑：-如果待删除节点是叶子节点，则直接将其从二叉树中删除即可。
-如果待删除节点只有一个子节点，则将其子节点替换为待删除节点的位置即可。
-如果待删除节点有两个子节点，则需要找到其左子树或右子树中的最大节点或最小节点，将其值替换为待删除节点的值，然后再删除最大节点或最小节点。
3.查找操作：二叉树的查找操作是在二叉树中查找指定值的节点的过程。
查找操作的具体步骤如下：-从根节点开始，将待查找值与当前节点的值进行比较。
-如果待查找值等于当前节点的值，则返回该节点。
-如果待查找值小于当前节点的值，则在当前节点的左子树中继续查找。
-如果待查找值大于当前节点的值，则在当前节点的右子树中继续查找。
-如果左子树或右子树为空，则说明在二叉树中找不到该值。
4.遍历操作：二叉树的遍历操作是按照一定规则依次访问二叉树中的每个节点。
有三种常用的遍历方式：- 前序遍历（Preorder Traversal）：先访问根节点，然后递归地前序遍历左子树和右子树。
- 中序遍历（Inorder Traversal）：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。
二叉树的建立与基本操作二叉树是一种特殊的树形结构，它由节点（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. 顺序存储顺序存储是将二叉树中的所有元素按照一定的顺序存储在一段连续的内存单元中，通常采用数组来表示。
对于任意一个节点i，其左孩子节点的位置为2*i+1，右孩子节点的位置为2*i+2。
这种存储方式的优点是访问速度快，但需要预先确定节点总数，且不易于插入和删除操作。
2. 链式存储链式存储是采用指针的方式将二叉树的节点链接起来。
每个节点包含数据元素以及指向左孩子节点和右孩子节点的指针。
链式存储方式的优点是易于插入和删除操作，但访问速度较慢。
二、二叉树的基本操作1. 创建二叉树创建二叉树的过程就是将数据元素按照一定的顺序插入到二叉树中。
对于顺序存储的二叉树，需要预先分配内存空间；对于链式存储的二叉树，可以直接创建节点对象并链接起来。
2. 遍历二叉树遍历二叉树是指按照某种规律访问二叉树中的所有节点，通常有前序遍历、中序遍历和后序遍历三种方式。
前序遍历的顺序是根节点-左孩子节点-右孩子节点；中序遍历的顺序是左孩子节点-根节点-右孩子节点；后序遍历的顺序是左孩子节点-右孩子节点-根节点。
对于顺序存储的二叉树，可以采用循环结构实现遍历；对于链式存储的二叉树，需要使用指针逐个访问节点。
3. 查找元素在二叉树中查找元素，需要根据一定的规则搜索所有节点，直到找到目标元素或搜索范围为空。
对于顺序存储的二叉树，可以采用线性查找算法；对于链式存储的二叉树，可以采用深度优先搜索或广度优先搜索算法。
4. 插入元素在二叉树中插入元素需要遵循一定的规则，保证二叉树的性质。
对于顺序存储的二叉树，插入操作需要移动大量元素；对于链式存储的二叉树，插入操作相对简单，只需修改指针即可。
5. 删除元素在二叉树中删除元素同样需要遵循一定的规则，保证二叉树的性质。
实验三二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。
2、熟练掌握二叉树的各种遍历算法。
二、实验内容1、问题描述建立一棵二叉树，试编程实现二叉树的如下基本操作：(1). 按先序序列构造一棵二叉链表表示的二叉树T；(2). 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；(3). 求二叉树的深度/结点数目/叶结点数目；(选做)(4). 将二叉树每个结点的左右子树交换位置。
（选做）2、基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）。
3、测试数据如输入：abc00de0g00f000（其中ф表示空格字符）则输出结果为：先序：a->b->c->d->e->g->f中序：a->b->c->d->e->g->f后序：a->b->c->d->e->g->f三、程序代码#include<malloc.h>#include<iostream.h>#define OK 1#define ERROR -1typedef char TElemType;int i;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;int CreateBiTree(BiTree&T) //创建二叉树{char a;cin>>a;if(a=='0') T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode)))) {return ERROR;}T->data=a;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return OK;}int PreOrderTraverse(BiTree&T) //先序遍历二叉树{if(T){//cout<<"此为先序遍历"<<endl;cout<<T->data<<"->";if(PreOrderTraverse(T->lchild))if(PreOrderTraverse(T->rchild))return OK;return ERROR;}else return OK;}int InOrderTraverse(BiTree&T) //中序遍历二叉树{if(T){//cout<<"此为中序遍历"<<endl;if(InOrderTraverse(T->lchild)){cout<<T->data<<"->";if(InOrderTraverse(T->rchild))return OK;}return ERROR;}else return OK;}int PostOrderTraverse(BiTree&T) //后序遍历二叉树{if(T){//cout<<"此为后序遍历"<<endl;if (PostOrderTraverse(T->lchild))if(PostOrderTraverse(T->rchild)){cout<<T->data<<"->";i++;return (OK);}return (ERROR);}elsereturn (OK);}int CountDepth(BiTree&T) //计算二叉树的深度{if(T==NULL){return 0;}else{int depl=CountDepth(T->lchild);int depr=CountDepth(T->lchild);if(depl>depr){return depl+1;}else{return depr+1;}}}void main() //主函数{BiTree T;cout<<"请输入二叉树节点的值以创建树"<<endl;CreateBiTree(T);cout<<"此为先序遍历";PreOrderTraverse(T);cout<<"end"<<endl;cout<<"此为中序遍历";InOrderTraverse(T);cout<<"end"<<endl;cout<<"此为后序遍历";PostOrderTraverse(T);cout<<"end"<<endl<<"此树节点数是"<<i<<endl<<"此树深度是"<<CountDepth(T)<<endl;}四、调试结果及运行界面：五、实验心得通过这次程序上机实验让我认识到了以前还不太了解的二叉树的性质和作用，这次实验的的确确的加深了我对它的理解。
二叉树的顺序存储及基本操作二叉树的顺序存储是将树中的节点按照完全二叉树从上到下、从左到右的顺序依次存储到一个一维数组中，采用这种方式存储的二叉树也被称为完全二叉树。
一、在使用顺序存储方式时，可以使用以下公式来计算一个节点的左右子节点和父节点：
1. 左子节点：2i+1（i为父节点的在数组中的下标）
2. 右子节点：2i+2
3. 父节点：(i-1)/2（i为子节点在数组中的下标）
二、基本操作：
1. 创建二叉树：按照上述公式将节点存储到数组中。
2. 遍历二叉树：可采用递归或非递归方式，进行前序、中序、后序、层次遍历。
3. 插入节点：先将节点插入到数组末尾，然后通过比较节点和其父节点的大小，进行上浮操作直到满足二叉树的性质。
4. 删除节点：先将待删除节点和最后一个节点交换位置，然后通过比较交换后的节点和其父节点的大小，进行下沉操作直到满足二
叉树的性质。
5. 查找节点：根据节点值进行查找，可采用递归或非递归方式。
6. 修改节点：根据节点值进行查找，然后进行修改操作。
二叉树的基本操作看东西容易，写东西确实就复杂多了呀，花了两天时间把二叉树的数据结构及一些相关基本算法的原理认真研究了下，并写出了相应的代码，包括二叉树的前序创建、前中后序遍历、层序遍历、删除、通过前序和中序序列构造二叉树等等#include <stdio.h>//定义数据元素类型typedef int Element;//定义二叉树节点typedef struct bitree{Element data;struct bitree *left, *right;} Bitree;//定义队列节点，层序遍历typedef struct queueNode{Bitree * data;struct queueNode *next;} QueueNode;typedef struct queue{QueueNode *front, *rear;} Queue;//创建队列void createQueue(Queue **Q){*Q = (Queue *) malloc(sizeof(Queue));if(!*Q)exit("Memory error...\n");(*Q)->front = (*Q)->rear = NULL;}//入队操作void EnQueue(Queue *Q, Bitree *data){QueueNode * qn = (QueueNode*) malloc(sizeof(QueueNode));if(!qn)exit("Memory error...\n");qn->data = data;qn->next = NULL;if(IsQueueEmpty(Q))Q->front = Q->rear = qn;else{Q->rear->next = qn;Q->rear = qn;}}//出队操作void DeQueue(Queue *Q, Bitree **T){if(!IsQueueEmpty(Q)){QueueNode *qn = Q->front;(*T) = qn->data;Q->front = qn->next;free(qn);qn = NULL;}}//判断队列是否为空int IsQueueEmpty(Queue *Q){if(!Q->front)return 1;return 0;}//二叉树的创建void createBitree(Bitree **T){Element data;scanf("%d", &data);if(data != 0){(*T) = (Bitree*)malloc(sizeof(Bitree)); if(!*T)exit("Memory error...\n");(*T)->data = data;(*T)->left = (*T)->right = NULL;createBitree(&(*T)->left);createBitree(&(*T)->right);}}//根据前序和中序遍历结果生成二叉树(总是假设给定的序列是有效的，这里不进行错误检测)//@param p 递归前序子序列的起始位置//@param m 递归中序子序列的起始位置//@param length 递归子序列的长度void creByPreMid(Bitree **T, int p, int m, int length, int *pre, int *mid) {int i=0;for(;(i<length)&&(pre[p]!=mid[m+i]);i++);(*T) = (Bitree *) malloc(sizeof(Bitree));if(!*T)exit("Memory error...\n");(*T)->data = pre[p];(*T)->left = (*T)->right = NULL;//若有左子树则创建左子树if(i>0){creByPreMid(&(*T)->left, p+1, m, i, pre, mid);}//若有右子树则创建右子树if(i<length-1){creByPreMid(&(*T)->right, p+1+i, m+i+1, length-i-1, pre, mid); }}//删除树void delBitree(Bitree **T){if(*T){delBitree(&(*T)->left);delBitree(&(*T)->right);free(*T);*T = NULL;}}//二叉树的前序遍历void preOrder(Bitree *T){if(T){printf("%d ", T->data);preOrder(T->left);preOrder(T->right);}}//二叉树的中序遍历void midOrder(Bitree *T){if(T){midOrder(T->left);printf("%d ", T->data);midOrder(T->right);}}//二叉树的后序遍历void afterOrder(Bitree *T){if(T){afterOrder(T->left);afterOrder(T->right);printf("%d ", T->data);}}//二叉树的层序遍历//思路：利用队列，如果树不为空，将根节点入队// 然后循环队头元素出队，并作一下处理：判断出队的节点是否有左孩子，有则将左孩子入队，判断出队的节点是否有右孩子，有则将又孩子入队。
⼆叉树的基础操作⼆叉树 ⼀：创建以及初始化赋值：struct BiTree{char data;BiTree* lchild;BiTree* Rchild;};//初始化BiTree* create() {//先序创建⼆叉树BiTree *T;char a;cin >> a;if (a == '.')return NULL;else {T = (BiTree*)malloc(sizeof(BiTree));T->data = a;T->lchild = create();T->Rchild = create();}//若想中序或后序创建，则只需改变函数中//T->data=a;T->lchild=create();T->rchild=create();这三条语句的顺序//先给T->data=a在先的话是先序，在中间的话是中序，在最后的话是后序。
} ⼆：⼆叉树遍历⽅法：/*先序的遍历顺序是根节点->左⼦树->右⼦树。
中序的遍历顺序是左⼦树->根节点->右⼦树。
后序的遍历顺序是右⼦树->根节点->左⼦树。
层序的遍历顺序是按层顺次遍历。
先序、中序、后序的代码基本相同*/void pre(BiTree *root) {BiTree* p = root;if (p) {cout << p->data;pre(p->lchild);pre(p->Rchild);}}void mid(BiTree* root) {BiTree* p = root;if (root) {mid(p->lchild);cout << p->data;mid(p->Rchild);}}void post(BiTree* root) {BiTree* p = root;if (p) {post(p->Rchild);post(p->lchild);cout << p->data;}} 三：⼆叉树插⼊操作：//插⼊操作,没有重复的元素//插⼊法1：BiTree* BSTInsert(BiTree* L, int key) {if (!L) {//若是⼀个空表，那么就创建最开始的L = (BiTree*)malloc(sizeof(BiTree));L->data = key;L->lchild = L->Rchild = NULL;}else {//若不是空表就按照⼆叉树组成规则遍历插⼊if (L->data < key)L->Rchild = BSTInsert(L->Rchild, key);else if (L->data > key)L->lchild = BSTInsert(L->lchild, key);}return L;}//插⼊法2：整列树的插⼊//int data[9]={8,3,10,13,14,1,6,7,4};BiTree* Insert(BiTree* L, int data[], int n) {int i;for (int i = 0; i < n; i++) {L = BSTInsert(L, data[i]);}return L;} 四：⼆叉树查询：//查询元素位置：/*查询法1：寻找最⼩、最⼤元素的⽅法是相同的。
⼆叉树及⼆叉树的基本操作（基础篇）⼀、相关概念树是n（ n>=0）个有限个数据的元素集合，它的数据的存储结构形状像⼀颗倒过来的树。
根在上，叶在下：如图所⽰1.⼀个独⽴的节点也可看作⼀棵树，它既为根节点，⼜为叶⼦节点；2.⼀个节点也没有称作空树；3.这是⼀颗典型的树，根节点为A；4.⼀个节点只有唯⼀⽗节点。
节点：结点包含数据和指向其它节点的指针。
根节点：树第⼀个结点称为根节点。
结点的度：结点拥有的⼦节点个数。
叶节点：没有⼦节点的节点(度为0)。
⽗⼦节点：⼀个节点father指向另⼀个节点child，则child为孩⼦节点， father为⽗亲节点。
兄弟节点：具有相同⽗节点的节点互为兄弟节点。
节点的祖先：从根节点开始到该节点所经的所有节点都可以称为该节点的祖先。
⼦孙：以某节点为根的⼦树中任⼀节点都称为该节点的⼦孙。
树的⾼度：树中距离根节点最远节点的路径长度。
如图⽰：5.树的存储结构1 struct TreeNode2 {3 DataType data; //节点值4 TreeNode* _firistchild; //第⼀个孩⼦5 TreeMode* _nextchild; //第⼆个孩⼦6 ...7 }；有时候根据需要还会加⼊⽗节点，结构如下：1 struct TreeNode2 {3 DataType data; //节点值4 TreeNode* _parent;5 TreeNode* _firistchild; //第⼀个孩⼦6 TreeMode* _nextchild; //第⼆个孩⼦7 ...8 }；⼆、⼆叉树1.⼆叉树:⼆叉树是⼀棵特殊的树，⼆叉树每个节点最多有两个孩⼦结点，分别称为左孩⼦和右孩⼦。
如图：2.存储结构1 template <class T>2 struct TreeNode //定义⼆叉树结点3 {5 TreeNode<T>* _left; //指向左⼦树的指针6 TreeNode<T>* _right; //指向右⼦树的指针7 T _data; //节点数据8 TreeNode(const T& n)9 :_left(NULL)10 ,_right(NULL)11 ,_data(n)12 {}13 };有时候根据需要还会加⼊⽗节点，结构如下：1 template <class T>2 struct TreeNode //定义⼆叉树结点3 {4 TreeNode<T>* _parent; //指向⽗节点的指针5 TreeNode<T>* _left; //指向左⼦树的指针6 TreeNode<T>* _right; //指向右⼦树的指针7 T _data; //节点数据8 TreeNode(const T& n)9 :_left(NULL)10 ,_right(NULL)11 ,_data(n)12 {}13 };3.特殊的⼆叉树满⼆叉树:⾼度为N的满⼆叉树有2^N - 1个节点的⼆叉树。
c语言二叉树的基本操作一、概念二叉树是一种数据结构，它由节点组成，每个节点都有0个或2个子节点，左子节点的关键字小于或等于该节点的关键字，右子节点的关键字大于该节点的关键字。
二、基本操作1、创建二叉树（1）结构体定义typedef struct node{int data; // 数据struct node *left; // 左子节点struct node *right; // 右子节点}Node, *pNode;（2）创建节点return p;}// 创建根节点*pTree = create_node(arr[0]);// 寻找合适的位置插入节点while (p != NULL){q = p;if (arr[i] < p->data)p = p->left;elsep = p->right;}2、遍历二叉树遍历二叉树有三种方法，分别是前序遍历、中序遍历和后序遍历。
（1）前序遍历void pre_order(pNode pTree){if (pTree != NULL){printf("%d ", pTree->data);pre_order(pTree->left);pre_order(pTree->right);}}3、查找节点找到关键字为data的节点，返回指向该节点的指针。
pNode search_node(pNode pTree, int data){if (pTree == NULL)return NULL;4、计算深度计算二叉树的深度，即为根节点到叶子节点的最长路径所包含的节点个数。
return left_depth > right_depth ? left_depth + 1 : right_depth + 1; }5、计算叶子节点数return leaf_count(pTree->left) + leaf_count(pTree->right);}6、删除节点删除节点分为两种情况：（1）被删除节点为叶子节点直接将其父节点指向该节点的指针设置为NULL即可。
c语言数据结构二叉树的基本操作-回复C语言数据结构：二叉树的基本操作概述：二叉树是一种常用的数据结构，在计算机科学中广泛应用于各种算法和问题的解决方案中。
它的特点是每个节点至多有两个子节点，即左子节点和右子节点，且子节点的顺序不能颠倒。
本文将介绍常见的二叉树基本操作，包括创建二叉树、插入节点、删除节点、查找节点、遍历等。
1. 创建二叉树：创建一个二叉树的方法是从根节点开始，逐个插入子节点。
首先定义一个二叉树的结构体，包含一个值和指向左右子节点的指针。
然后使用malloc 函数分配内存空间，并将值赋给根节点的指针。
接着创建左子节点和右子节点，将子节点的指针分别赋给根节点的左右指针。
这样就完成了一个简单的二叉树的创建。
2. 插入节点：插入节点是在现有的二叉树上新增一个节点。
首先找到插入节点的位置，可以从根节点开始逐级比较。
如果插入节点的值小于当前节点，则向左子树查找，否则向右子树查找，直到找到合适的位置。
然后创建一个新节点，并将新节点的指针赋给找到位置的节点的左或右指针。
3. 删除节点：删除节点是将现有的二叉树中的一个节点删除。
首先找到要删除的节点位置，可以通过比较节点的值进行查找，直到找到要删除的节点。
然后根据删除节点的情况分三种情况考虑：若删除节点为叶子节点，直接删除即可；若删除节点只有一个子节点，将子节点的指针赋给删除节点的父节点，然后删除删除节点；若删除节点有两个子节点，需要找到删除节点的左子树中的最大节点或右子树中的最小节点，将其值赋给删除节点，然后删除此最大或最小节点。
4. 查找节点：查找节点是在现有的二叉树中寻找一个特定的节点。
与插入和删除类似，从根节点开始比较节点的值，若要查找的节点值小于当前节点，则继续向左子树查找，否则向右子树查找，直到找到要查找的节点。
若找到了节点，返回此节点的指针；若未找到，返回空指针。
5. 遍历：遍历二叉树是按照一定的顺序访问树中的所有节点。
常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。
《数据结构与数据库》实验报告实验题目二叉树的基本操作及运算一、需要分析问题描述：实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。
问题分析：二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。
由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。
处理本问题，我觉得应该：1、建立二叉树；2、通过递归方法来遍历（先序、中序和后序）二叉树；3、通过队列应用来实现对二叉树的层次遍历；4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等；5、运用广义表对二叉树进行广义表形式的打印。
算法规定：输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。
输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。
对二叉树的一些运算结果以整型输出。
程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。
计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。
对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。
测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E预测结果：先序遍历ABCDEGF中序遍历CBEGDFA后序遍历CGEFDBA层次遍历ABCDEFG广义表打印A（B（C,D（E（,G）,F）））叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2查找5，成功，查找的元素为E删除E后，以广义表形式打印A（B（C,D（,F）））输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B预测结果：先序遍历ABDEHCFG中序遍历DBHEAGFC后序遍历DHEBGFCA层次遍历ABCDEFHG广义表打印A（B(D,E(H)),C(F(,G))）叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3查找10，失败。
二叉树的建立与基本操作二叉树是一种重要的数据结构，它由节点以及节点之间的链接组成。
每个节点最多有两个子节点，被称为左子节点和右子节点。
二叉树的建立和操作是学习数据结构的基础内容，对于计算机科学和算法设计非常重要。
本文将介绍二叉树的建立和一些基本操作，包括插入节点、删除节点、查找节点以及遍历二叉树。
一、二叉树的建立要建立一个二叉树，我们需要先定义一个节点类，并指定节点的左子节点和右子节点。
节点类一般包含一个值以及左子节点和右子节点的指针。
下面是一个示例的节点类的定义：class Nodepublic:int value;Node* left;Node* right;};接下来，我们可以通过创建节点对象并将它们连接起来来构建一棵二叉树。
下面是一个示例的建立二叉树的函数：Node* buildTreNode* root = new Node(;root->value = 1;Node* node1 = new Node(;node1->value = 2;Node* node2 = new Node(;node2->value = 3;Node* node3 = new Node(;node3->value = 4;Node* node4 = new Node(;node4->value = 5;root->left = node1;root->right = node2;node1->left = node3;node1->right = node4;return root;在这个示例中，我们创建了一个根节点root，然后创建了四个子节点node1、node2、node3和node4，并将它们连接到正确的位置上。
二、二叉树的基本操作1.插入节点要插入一个节点，我们首先需要找到插入的位置。
如果节点要插入的位置为null，则直接将节点赋值给该位置；否则，继续找到合适的位置插入节点。
二叉树的基本操作二叉树是一种常见的数据结构，它由节点组成，每个节点最多连接两个子节点，分别称为左子节点和右子节点。
二叉树的基本操作包括创建、插入、删除、查找和遍历，下面将对这些操作进行详细介绍。
一、创建二叉树创建二叉树的方法有多种，其中最常用的是使用递归的方式。
递归创建二叉树时，可以先创建根节点，然后递归创建左子树和右子树。
如果子树为空，则使用特殊字符表示。
二、插入节点插入节点是向二叉树中添加新节点的操作。
插入节点的位置通常由二叉树的特性决定，左子节点小于父节点，右子节点大于父节点。
插入节点时，需要先找到插入位置，然后创建新节点，并将其连接到对应的位置。
三、删除节点删除节点是从二叉树中移除指定节点的操作。
删除节点的方式取决于节点的位置和子节点的情况。
如果要删除的节点是叶子节点，则直接将其删除即可。
如果要删除的节点有一个子节点，则将其子节点连接到父节点。
如果要删除的节点有两个子节点，则需要找到替代节点，将替代节点的值复制到当前位置，并将替代节点删除。
四、查找节点查找节点是在二叉树中寻找特定节点的操作。
常用的方式有深度优先（DFS）和广度优先（BFS）。
深度优先通常使用递归实现，分为前序遍历、中序遍历和后序遍历三种方式。
广度优先通常使用队列实现，先访问根节点，然后访问其所有子节点，再逐层访问下去，直到找到目标节点或遍历完整棵树。
五、遍历二叉树遍历二叉树是指按照一定顺序访问二叉树中的所有节点，常用的方式有前序遍历、中序遍历和后序遍历。
前序遍历先访问根节点，然后递归遍历左子树和右子树；中序遍历先递归遍历左子树，然后访问根节点，再遍历右子树；后序遍历先递归遍历左子树和右子树，然后访问根节点。
以上是二叉树的基本操作，通过这些操作可以有效地管理和处理二叉树数据结构。
在实际应用中，二叉树常用于、排序和表达等方面，因为它具有较高的查询效率和灵活性。
对于使用二叉树的相关算法和数据结构，理解和掌握其基本操作是非常重要的。
c语言实现二叉树的基本操作二叉树是一种树状数据结构，其中每个节点最多有两个子节点。
C语言中，我们可以使用结构体来表示一个二叉树节点：```struct TreeNode {int val; // 节点值struct TreeNode *left; // 左子节点struct TreeNode *right; // 右子节点};```二叉树的基本操作包括：1. 创建节点```struct TreeNode *createNode(int val) {struct TreeNode *node = (structTreeNode*)malloc(sizeof(struct TreeNode));node->val = val;node->left = NULL;node->right = NULL;return node;}```2. 插入节点```struct TreeNode *insertNode(struct TreeNode *root, int val) {if (root == NULL) {return createNode(val);}if (val < root->val) {root->left = insertNode(root->left, val);} else {root->right = insertNode(root->right, val);}return root;}```3. 删除节点```struct TreeNode *deleteNode(struct TreeNode *root, int key) {if (root == NULL) {return NULL;}if (key < root->val) {root->left = deleteNode(root->left, key);} else if (key > root->val) {root->right = deleteNode(root->right, key);} else {if (root->left == NULL) {struct TreeNode *temp = root->right;free(root);return temp;} else if (root->right == NULL) {struct TreeNode *temp = root->left;free(root);return temp;}struct TreeNode *temp = minValueNode(root->right);root->val = temp->val;root->right = deleteNode(root->right, temp->val);}return root;}struct TreeNode *minValueNode(struct TreeNode *node) { struct TreeNode *current = node;while (current && current->left != NULL) {current = current->left;}return current;}```4. 遍历二叉树```// 前序遍历void preorderTraversal(struct TreeNode *root) { if (root == NULL) {return;}printf('%d ', root->val);preorderTraversal(root->left);preorderTraversal(root->right);}// 中序遍历void inorderTraversal(struct TreeNode *root) { if (root == NULL) {return;}inorderTraversal(root->left);printf('%d ', root->val);inorderTraversal(root->right);}// 后序遍历void postorderTraversal(struct TreeNode *root) {if (root == NULL) {return;}postorderTraversal(root->left);postorderTraversal(root->right);printf('%d ', root->val);}```以上便是使用C语言实现二叉树的基本操作的代码。
二叉树的基本操作摘要：本次课程设计通过对二叉树的一系列操作主要练习了二叉树的建立、四种遍历方式：先序遍历、中序遍历、后序遍历和层序遍历以及节点数和深度的统计等算法。
增加了对二叉树这一数据结构的理解，掌握了使用c语言对二叉树进行一些基本的操作。
关键字：递归、二叉树、层序遍历、子树交换一、程序简介本程序名为“二叉树基本操作的实现”，其主要为练习二叉树的基本操作而开发，其中包含了建立、遍历、统计叶子结点和深度等一系列操作。
其中定义二叉链表来表示二叉树，用一个字符类型的数据来表示每一个节点中存储的数据。
由于没有进行图形界面的设计，用户可以通过程序中的遍历二叉树一功能来查看操作的二叉树。
二、功能模块2.1功能模块图2.2功能模块详解2.2.1建立二叉树输入要建立的二叉树的扩展二叉树的先序遍历序列，来建立二叉树，建立成功会给出提示。
2.2.2遍历二叉树执行操作之后会有四个选项可供选择：先序遍历、中序遍历、后序遍历、层序遍历。
输入对应的序号即可调动相关函数输出相应的遍历序列。
2.2.3统计叶子节点树执行之后输出叶子结点的个数。
2.2.4求二叉树深度执行之后输出二叉树的深度。
2.2.5子树交换交换成功则会给出提示，用户可通过遍历二叉树来观察子树交换之后的二叉树。
三、数据结构和算法设计3.1二叉链表的设计1.typedef struct BiNode {2.char data;3.struct BiNode* lchild; //左孩子4.struct BiNode* rchild; //右孩子5.}BiTree;用一个字符型保存节点数据，分别定义两个struct BiNode类型的指针来指向左孩子和右孩子。
在BiTree.h中实现相关的功能。
3.2队列的实现1.typedef struct {2. ElemType* data;3.int head;//队头指针4.int tail;//队尾指针5.} SqQueue;队列主要用于二叉树遍历过程中的层序遍历，从根节点开始分别将左右孩子放入队列，然后从对头开始输出。
⼆叉树基本操作/*计算机科学与技术九班 黄平 3105007170*//*头⽂件,包函⼆叉树所有的基本操作*/#include<stdio.h>#include<stdlib.h>#include<dos.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define MaxSize 100typedef int Status;typedef char TElemType;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree T;TElemType e;/*防问结点*/Status Visit(TElemType e){printf("%c ",e);return OK;}/*初始化⼆叉树*/Status InitBiTree(BiTree &T){T=(BiTree)malloc(sizeof(BiTNode));if(T) return OK;else return ERROR;}/*以三种⽅式建⽴⼆叉树:1为先序,2为中序,3为后序*/Status CreateBiTree(BiTree &T,int def){char ch;ch=getchar();switch(def){case 1://先序if (ch==' ') T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));T->data=ch;CreateBiTree(T->lchild,def);CreateBiTree(T->rchild,def);}return OK;break;case 2://中序if (ch==' ') T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));CreateBiTree(T->lchild,def);T->data=ch;CreateBiTree(T->rchild,def);}return OK;break;case 3://后序if (ch==' ') T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));CreateBiTree(T->lchild,def);CreateBiTree(T->rchild,def);T->data=ch;}return OK;break;default:return ERROR;}}/*删除⼆叉树⼀个结点,作为ClearBiTree的⼦函数*/ Status BinTreeDel(BiTree &T){if(T){BinTreeDel(T->lchild);BinTreeDel(T->rchild);free(T);}return OK;}/*清空⼆叉树*/Status ClearBiTree(BiTree &T){BinTreeDel(T);T = NULL;return OK;}/*销毁⼆叉树*/Status DestroyBiTree(BiTree &T){if(ClearBiTree(T)) return OK;else return ERROR;}/*判断⼆叉树是否为空,为空返回1,不为空返回0*/ Status BiTreeEmpty(BiTree T){if(T==NULL) return TRUE;else return FALSE;}/*求⼆叉树的深度*/int BiTreeDepth(BiTree T){int del,der;if(!T)return ERROR;else{del=BiTreeDepth(T->lchild);der=BiTreeDepth(T->rchild);if(del>der)return(del+1);elsereturn(der+1);}}/*求⼆叉树根结点的数值,不存在则返回空*/TElemType Root(BiTree T){if(T) return T->data;else return ' ';}/*e是指向T中某个结点的指针,返回e的数值*/TElemType Value(BiTree &T,BiTree e){return e->data;}/*如果T中存在e,则结点e的值改为v并返回1,如果不存在则返回0*/ Status Assign(BiTree &T,TElemType e,TElemType v){if(T->data==e){T->data=v;return OK;}else{if(T->lchild)if(Assign(T->lchild,e,v))return OK;if(T->rchild)if(Assign(T->rchild,e,v))return OK;return ERROR;}}/*如果⼆叉树T中存在结点e,则输出其双亲并返回1,否则返回0*/ Status Parent(BiTree T,TElemType e){if((T->lchild&&T->lchild->data==e)||(T->rchild&&T->rchild->data==e)) {Visit(T->data);return OK;}else{if(T->lchild)if(Parent(T->lchild,e))return OK;if(T->rchild)if(Parent(T->rchild,e))return OK;return ERROR;}}/*如果⼆叉树T中存在结点e,则输出其左孩⼦并返回1,否则返回0*/ Status LeftChild(BiTree T,TElemType e){if(T->data==e){if(T->lchild) Visit(T->lchild->data);else Visit(' ');return OK;}else{if(T->lchild)if(LeftChild(T->lchild,e))return OK;if(T->rchild)if(LeftChild(T->rchild,e))return OK;return ERROR;}}/*如果⼆叉树T中存在结点e,则输出其右孩⼦并返回1,否则返回0*/ Status RightChild(BiTree T,TElemType e){if(T->data==e){if(T->rchild) Visit(T->rchild->data);else Visit(' ');return OK;}else{if(T->lchild)if(RightChild(T->lchild,e))return OK;if(T->rchild)if(RightChild(T->rchild,e))return OK;return ERROR;}}/*如果⼆叉树T中存在结点e,则输出其左兄弟并返回1,否则返回0*/ Status LeftSib(BiTree T,TElemType e){if(T->rchild&&T->rchild->data==e){if(T->lchild) Visit(T->lchild->data);else Visit(' ');return OK;}else{if(T->lchild)if(LeftSib(T->lchild,e))return OK;if(T->rchild)if(LeftSib(T->rchild,e))return OK;return ERROR;}}/*如果⼆叉树T中存在结点e,则输出其右兄弟并返回1,否则返回0*/ Status RightSib(BiTree T,TElemType e){if(T->lchild&&T->lchild->data==e){if(T->rchild) Visit(T->rchild->data);else Visit(' ');return OK;}else{if(T->lchild)if(RightSib(T->lchild,e))return OK;if(T->rchild)if(RightSib(T->rchild,e))return OK;return ERROR;}}/*如果T中存在结点e,则LR为1时插⼊v为e的左孩⼦,LR为2时插⼊v为e的右孩⼦.如不存在则返回0*/ Status InsertChild(BiTree &T,TElemType e,int LR,TElemType v){BiTree p;if(T->data==e){if(LR==1) {InitBiTree(p);p->data=v;p->rchild=T->lchild;p->lchild=NULL;T->lchild=p;}if(LR==2) {InitBiTree(p);p->data=v;p->rchild=T->rchild;p->lchild=NULL;T->rchild=p;}return OK;}else{if(T->lchild)if(InsertChild(T->lchild,e,LR,v))return OK;if(T->rchild)if(InsertChild(T->rchild,e,LR,v))return OK;return ERROR;}}/*如T中存在结点e,则删除结点并返回1.如不存在则返回0*/Status DeleteChild(BiTree &T,TElemType e){if(T->data==e){free(T);T=NULL; return OK;}else{if(T->lchild)if(DeleteChild(T->lchild,e))return OK;if(T->rchild)if(DeleteChild(T->rchild,e))return OK;return ERROR;}}/*先序遍历⼆叉树*/Status PreOrderTraverse(BiTree T){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild)) if(PreOrderTraverse(T->rchild)) return OK;return ERROR;}else return OK;}/*中序遍历⼆叉树*/Status InOrderTraverse(BiTree T){if(T){if(InOrderTraverse(T->lchild))if(Visit(T->data))if(InOrderTraverse(T->rchild))return OK;return ERROR;}else return OK;}/*后序遍历⼆叉树*/Status PostOrderTraverse(BiTree T) {if(T){if(InOrderTraverse(T->lchild))if(InOrderTraverse(T->rchild))if(Visit(T->data))return OK;return ERROR;}else return OK;}/*层次遍历⼆叉树*/Status LevelTraverse(BiTree T){BiTree p,Queue[MaxSize];int front,rear;front = rear = 0; if(T != NULL){rear = (rear+1)%MaxSize; Queue[rear] = T;}while (front != rear) {front = (front+1)%MaxSize; p = Queue[front];Visit(p->data);if(p->lchild != NULL) {rear = (rear+1)%MaxSize;Queue[rear] = p->lchild;}if(p->rchild != NULL) {rear = (rear+1)%MaxSize;Queue[rear] = p->rchild;}}return OK; }。
#include "stdio.h"#include "stdlib.h" #include "string.h"#include "math.h"typedef char TElemType;//定义结点数据为字符型 typedef int Status;//定义函数类型为 int 型#define ERROR 0#define OK 1}BiTNode, *BiTree; Status NumJudge(char ch[20]){ //限制输入数据必须为大于零的整形 char ch1[20]; int num;while(1){scanf("%s",ch);num=atoi(ch); // 将字符串转换为整型itoa(num,ch1,10); //将整型转换为字符串型 if(strcmp(ch,ch1)==0&&num>0)break; else{printf(" 请输入一个大于零的整数 : ");} }return num; }//NumJudgeStatus InitBiTree(BiTree &T){//构造空二叉树 T if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);T->next=NULL;printf("\n\t 空二叉树构建成功 !\n\n");return OK;}//InitBiTreeStatus DestroyTree(BiTree &T,BiTree t){//销毁二叉树if(T){free(T);T=NULL; printf （"\t 二叉树销毁成功 !\n"）;} if(t){DestroyTree(T,t->lchild);DestroyTree(T,t->rchild);free(t);} return OK;}//DestroyTreeStatus ClearBiTree(BiTree &T,int sum,int &i){//清空二叉树 if(T){typedef struct BiTNode{ //定义结构体 TElemType data; // 结点数值 struct BiTNode *lchild; // 左孩子指针 struct BiTNode*rchild; // 右孩子指针 struct BiTNode *next;//下一结点指针//若申请空间失败则退出ClearBiTree(T->lchild,sum,i);ClearBiTree(T->rchild,sum,i);free(T);i++;} if(i==sum){printf("\t 二叉树清空成功!\n");T=NULL;} return OK;}//ClearBiTreeStatus CreateBiTree(BiTree &T,int i,int j,TElemType ch){ //按先序次序输入二叉树中结点的值(一个字符), 空格字符表示该结点为空//构造二叉链表示的二叉树T TElemType ch1;int k;char str[20];if(i==0){printf("\n 按先序顺序建立二叉树:请按提示输入相应的数据( 一个字符)，若提示结点数值为空，\n 请输入空格\n\n");printf("%5s 请输入树根: "," ");} if(i!=0&&i>=j){printf("%5s 请输入%c 的左孩子: "," ",ch);}if(j!=0&&j>i){printf("%5s 请输入%c 的右孩子: "," ",ch);} while(1){ //限制输入数据必须为字符型,否则重新输入fflush(stdin); for(k=0;k<20;k++){ str[k]=getchar(); if(str[k]=='\n')break;} if(k==0)printf("%5s 请输入一个字符后再按Enter 键: "," "); if(k==1)break;if(k>1)printf("%5s 您只能输入一个字符: "," ");}ch1=str[0]; // 获取输入的准确字符型数据if(ch1==' '){T=NULL;return ERROR;} // 输入空格则为根结点为空if(ch1!=' '){ if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(ERROR);T->data=ch1; // 生成根结点ch=T->data;i++;CreateBiTree(T->lchild,i,j,ch); // 构造左子树j=i;j++;CreateBiTree(T->rchild,i,j,ch); // 构造右子树}i=0;j=0;return OK;}//CreateBitreeStatus TreeDepth(BiTree T,int l,int &h){//若二叉树存在,返回其深度if(T){l=l+1;if(l>h)h=l;TreeDepth(T->lchild,l,h);TreeDepth(T->rchild,l,h);}return h;}//TreeDepthStatus GetRootElem(BiTree T){//获取根结点值printf(" 该二叉树的根结点值为: %c\n\n",T->data);return OK;}//GetRootElemStatus SaveElem(BiTree T,BiTree *Q,int i){〃根据完全二叉树中，若本节点位置序号为i,则其左孩子结点为2i,右孩子为2i+1的方法//保存二叉树的有效结点至指针数组Q 特定的位置if(T){Q[i]=T;SaveElem(T->lchild,Q,2*i); SaveElem(T->rchild,Q,2*i+1);}return OK;}//SaveElemStatus Lev_Traverse(BiTree T,int h){//按层次从上到下,每层从左到右的顺序显示树状二叉树if(T==NULL){printf("\n\t\t 二叉树目前为空树\n\n");return ERROR;}BiTree *Q;if(!(Q=(BiTree *)malloc(int(pow(2,h)+1) * sizeof(BiTNode))))exit(ERROR);int i,j,n=1,k=h;for(i=1;i<=int(pow(2,h)+1);i++){Q[i]=NULL;}SaveElem(T,Q,n); // 将目前有效结点按照满二叉树的序号存储printf(" 提示:规定下图中的有效结点的位置序号从 1 开始按从上到下,从左到右的顺序依次递增\n");for(i=1;i<=(pow(2,h)+1);i++){ // 树形显示二叉树if(int(pow(2,h))%i==0){printf("\n"); printf("\t\t"); for(j=0;j<pow(2,k-1)-1;j++){ printf(" ");} k--;} if(Q[i])printf("%c",Q[i]->data); if(!Q[i])printf(" ");for(j=0;j<pow(2,k+1)-1;j++){printf(" ");}}printf("\n\n");i=0;j=0;returnOK; }//Lev_TraverseStatus FirstPrint(BiTree T,int i){//按先序次序(递归)访问二叉树if(i==0)printf("\n 先序(递归)遍历结果如下:\n"); if(T){ i++;printf("%-5c",T->data); // 访问TFirstPrint(T->lchild,i); // 递归遍历左子树FirstPrint(T->rchild,i); // 递归遍历右子树} i=0;return OK;}//FirstPrintBiTreeStatus MiddlePrint(BiTree T,int i){//按中序次序(递归)访问二叉树if(i==0)printf("\n 中序(递归)遍历结果如下:\n"); if(T){i++;MiddlePrint(T->lchild,i); //递归遍历左子树printf("%-5c",T->data); // 访问TMiddlePrint(T->rchild,i); //递归遍历右子树}i=0;return OK;}//MiddlePrintStatus LastPrint(BiTree T,int i){//按后序次序(递归)访问二叉树if(i==0)printf("\n 后序(递归)遍历结果如下:\n"); if(T){i++;LastPrint(T->lchild,i); //递归遍历左子树LastPrint(T->rchild,i); //递归遍历右子树printf("%-5c",T->data); //访问T }i=0;return OK;}//LastPrintStatus PreOrderTraverse(BiTree T){//按先序(非递归)遍历二叉树TBiTree p,S,q;int flag=0; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S->next=NULL; //建立空栈Sp=T;printf("\n 先序(非递归) 遍历结果如下:\n");while(1){while(1){ //遍历存储并访问左子树直到根结点左孩子不存在printf("%-5c",p->data); q=S->next;S->next=p;p->next=q; if(p->lchild)p=p->lchild;else{break;}//当前结点进栈}while(1){ // 栈顶指针出栈,如果当前栈顶指针的右孩子存在则跳出循环p=S->next;S->next=p->next;if(!S->next&&!p->rchild){flag=1;break;} // 如果栈空并且当前结点右孩子不存在则遍历结束if(p->rchild){p=p->rchild;break;}}if(flag==1)break;}printf("\n\n");return OK; }//PreOrderTraverseStatus InOrderTraverse(BiTree T){// 中序遍历(非递归) 二叉树TBiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S->next=NULL; //建立空栈Sp=T;printf("\n 中序(非递归) 遍历结果如下:\n"); while(p||S->next){ if(p){q=S->next;S->next=p;p->next=q;p=p->lchild;} // 左孩子进栈else{ p=S->next;S->next=p->next;if(p)printf("%-5c",p->data); //输出栈中元素else{return ERROR;}p=p->rchild;}}printf("\n\n"); return OK;}//InOrderTraverseStatus PostOrderTraverse(BiTree T){//后序遍历(非递归)二叉树TBiTree p,S,q; if(!(S=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR);S->next=NULL; // 建立空栈Sp=T;printf("\n 后序(非递归) 遍历结果如下:\n");while(1){while(1){ //遍历左子树,若当前结点左右孩子都不存在则跳出q=S->next;S->next=p;p->next=q; //当前结点进栈if(p->lchild)p=p->lchild;else{if(p->rchild)p=p->rchild; else{break;}}}while(S->next){ p=S->next;S->next=p->next; printf("%-5c",p->data); if(!S->next)break;if(p==S->next->rchild)p=S->next; 续出栈 else{ if(S->next->rchild){右孩子后跳出循环p=S->next->rchild;break;}} } if(!S->next)break;//若栈空则跳出循环 } printf("\n\n");return OK; }//PostOrderTraverseStatus GetElemSum(BiTree T){//计算二叉树中总结点的个数BiTree p,*q;int l=0,h=0;if(!(q=(BiTree *)malloc(int(pow(2,TreeDepth(T,l,h))+1) * sizeof(BiTNode))))exit(ERROR); int head=1,tail=2;q[1]=T;while(head<tail){p=q[head++];if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;}return head-1;}//GetElemSumStatus LevelOrderPrint(BiTree T){//二叉树 T 存在 ,层序遍历二叉树//将二叉树中的结点按从上到下，从左到右的顺序存至指针数组 q,然后按次序输出 BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int head=1,tail=2;q[1]=T;printf("\n 层序 (非递归 ) 遍历结果如下 :\n");while(head<tail){p=q[head++];//栈顶指针出栈并访问//若栈空则跳出// 若当前结点为栈顶指针的右孩子 ,则继 // 栈顶指针右孩存在 ,指针移至栈顶指针的printf("%-5c",p->data);if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;}printf("\n\n");return OK;}//LevelOrderPrintStatus GetElemNum(BiTree T,TElemType e){//查找元素e在二叉树T中的个数及位置int j,i=0,num=0,*a;BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);if(!(a=(int *)malloc(GetElemSum(T) * sizeof(int))))exit(ERROR);int head=1,tail=2;q[1]=T;while(head<tail){p=q[head++];if(p->data==e){num++;a[i]=head-1;i++;}if(p->lchild)q[tail++]=p->lchild; if(p->rchild)q[tail++]=p->rchild;}printf("\n 元素%c 在二叉树中的个数为: %d\n",e,num); printf(" 元素%c 在二叉树中的位置序号为:",e); for(j=0;j<i;j++){printf("%-4d",a[j]);}printf("\n");return num;}//GetElemNumStatus GetLeafNum(BiTree T){//计算二叉树T 中叶子个数BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int num=0,head=1,tail=2;q[1]=T; while(head<tail){ p=q[head++]; if(!p->lchild&&!p->rchild)num++;if(p->lchild)q[tail++]=p->lchild; if(p->rchild)q[tail++]=p->rchild;} return num;}//GetLeafNumStatus LBrother(BiTree T,int sum){//求第num 个结点的左兄弟BiTree p,*q; if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int i,num,head=1,tail=2;char str[20];q[1]=T;printf(" 请输入要查找的位置序号: "); num=NumJudge(str);if(num>sum){printf(" 您输入的位置序号大于有效结点个数\n");return ERROR;};while(head<tail){ p=q[head++];if(num==tail-2)break; if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;} if(num==1)printf(" 位置%d 的%c 没有左兄弟\n",num,q[num]->data);else{ for(i=1;i<num;i++){ if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break;}if(q[i]->lchild==q[num])printf(" 位置%d 的%c 没有左兄弟\n",num,q[num]->data); 为: %c\n",num,q[num]->data,q[i]->lchild->data);if(q[i]->rchild==q[num])printf(" 位置%d 的%c 的左兄弟}return OK;}//LBrotherStatus RBrother(BiTree T,int sum){//求第num 个结点的右兄弟BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int i,num,head=1,tail=2;char str[20];q[1]=T;printf(" 请输入要查找的位置序号: ");num=NumJudge(str);if(num>sum){printf(" 您输入的位置序号大于有效结点个数\n");return ERROR;};while(head<tail){p=q[head++];if(num==tail-2)break;if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;} if(num==1)printf(" 位置%d 的%c 没有右兄弟\n",num,q[num]->data);else{for(i=1;i<num;i++){ if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break;} if(!q[i]->rchild||q[i]->rchild==q[num])printf(" 位置%d 的%c 没有右兄弟\n",num,q[num]->data);if(q[i]->rchild&&q[i]->lchild==q[num])printf(" 位置%d 的%c 的右兄弟为: %c\n",num,q[num]->data,q[i]->rchild->data);}return OK;}//RBrotherStatus Lchild(BiTree T,int sum){//求第num 个结点的左孩子BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int num,head=1,tail=2;char str[20];q[1]=T;printf(" 请输入要查找的位置序号: ");num=NumJudge(str);if(num>sum){printf(" 您输入的位置序号大于有效结点个数\n");return ERROR;}while(head<tail){ p=q[head++]; if(num==tail-2)break; if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;}if(q[num]->lchild)printf(" 位置%d 的%c 的左孩为: %c\n",num,q[num]->data,q[num]->lchild->data);else{printf(" 位置%d 的%c 的左孩子不存在\n",num,q[num]->data);} return OK;}//LchildStatus Rchild(BiTree T,int sum){//求第num 个结点的右孩子BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int num,head=1,tail=2;char str[20];q[1]=T;printf(" 请输入要查找的位置序号: ");num=NumJudge(str);if(num>sum){printf(" 您输入的位置序号大于有效结点个数\n");return ERROR;}while(head<tail){ p=q[head++]; if(num==tail-2)break; if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;}if(q[num]->rchild)printf(" 位置%d 的%c 的右孩为: %c\n",num,q[num]->data,q[num]->rchild->data);else{printf(" 位置%d 的%c 的右孩子不存在\n",num,q[num]->data);} return OK;}//RchildStatus Partents(BiTree T,int sum){//求第num 个结点的双亲BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int i,num,head=1,tail=2;char str[20];q[1]=T;printf(" 请输入要查找的位置序号: "); num=NumJudge(str);if(num>sum){printf(" 您输入的位置序号大于有效结点个数\n");return ERROR;}while(head<tail){p=q[head++]; if(num==tail-2)break;if(p->lchild)q[tail++]=p->lchild; if(p->rchild)q[tail++]=p->rchild;}if(num==1)printf(" 位置%d 的%c 没有双亲\n",num,q[num]->data);else{for(i=1;i<num;i++){ if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break;}printf(" 位置%d 的%c 的双亲为: %c\n",num,q[num]->data,q[i]->data);}return OK;}//PartentsStatus TreeDelete(BiTree &T,int sum){//删除第num 个结点BiTree p,p1,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int i,num,head=1,tail=2,a=0,b=0;char str[20];q[1]=T;printf(" 请输入要删除结点的位置序号: "); num=NumJudge(str);if(num>sum){printf("\n 您输入的位置序号大于有效结点个数\n\n");return ERROR;}if(num==1){printf("\t 对不起,您不能删除根结点,若想删除根结点,请选择销毁树\n\n");return ERROR;};while(head<tail){ p=q[head++];if(num==tail-2)break; if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;} for(i=1;i<num;i++){ if(q[i]->lchild==q[num]||q[i]->rchild==q[num])break;}printf("\n 您删除了如下子树:\n\n");Lev_Traverse(q[num],TreeDepth(q[num],a,b)); if(q[i]->lchild==q[num])q[i]->lchild=NULL;if(q[i]->rchild==q[num])q[i]->rchild=NULL;p1=NULL;DestroyTree(p1,q[num]);printf("\n 删除结点成功\n");return OK;}//TreeDeleteStatus TreeInsert(BiTree &T,int sum){//在第num 个生成子树BiTree p,p1,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int num,head=1,tail=2,a=0,b=0;char ch=' ',str[20];q[1]=T;printf(" 请输入要插入结点的位置序号: ");num=NumJudge(str);if(num>sum){printf("\n 您输入的位置序号大于有效结点个数\n\n");return ERROR;}while(head<tail){p=q[head++];if(num==tail-2)break;if(p->lchild)q[tail++]=p->lchild;if(p->rchild)q[tail++]=p->rchild;} if(q[num]->lchild&&q[num]->rchild){ printf(" 您输入的位置序号已有左子树和右子树, 无法再此位置插入\n\n");returnERROR;}if(q[num]->lchild&&!q[num]->rchild){printf(" 位置%d 的%c 处只能生成右子树,确定插入/退出(y/n):",num,q[num]->data);while(1){scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0)break; else{printf(" 选择错误,请重新输入: ");}}if(strcmp(str,"y")==0){ printf(" 请输入插入子树的信息: \n");CreateBiTree(p1,a,b,ch); if(p1){q[num]->rchild=p1;}} if(strcmp(str,"n")==0)return ERROR;} if(!q[num]->lchild&&q[num]->rchild){ printf(" 位置%d 的%c 处只能生成左子树,确定插入/退出(y/n): ",num,q[num]->data);while(1){scanf("%s",str); if(strcmp(str,"y")==0||strcmp(str,"n")==0)break; else{printf(" 选择错误,请重新输入: ");} } if(strcmp(str,"y")==0){ printf(" 请输入插入子树的信息:\n"); CreateBiTree(p1,a,b,ch); if(p1){q[num]->lchild=p1;}} if(strcmp(str,"n")==0)return ERROR;} if(!q[num]->lchild&&!q[num]->rchild){ printf(" 请输入插入子树的信息: \n");CreateBiTree(p1,a,b,ch);printf("\t\t你想把新建的树作为位置％d的％c处的：\n",num,q[num卜〉data);printf("\t\t [1] 左子树[2] 右子树\n");printf("\n\t\t 请输入你的选择： ");while(1){scanf("%s",str); if(strcmp(str,"1")==0||strcmp(str,"2")==0)break;else{printf(" 选择错误,请重新输入： ");}}if(strcmp(str,"1")==0){if(p1){q[num]->lchild=p1;}}if(strcmp(str,"2")==0){ if(p1){q[num]->rchild=p1;}}}printf(" 插入子树成功\n");return OK;}//TreeInsertStatus Modify(BiTree T,int sum,int &n){ //修改二叉树第num 个结点的值BiTree p,*q;if(!(q=(BiTree *)malloc(GetElemSum(T) * sizeof(BiTNode))))exit(ERROR);int k,num,head=1,tail=2;char str[20];q[1]=T;n=0;printf(" 请输入要修改结点的位置序号: ");num=NumJudge(str);if(num>sum){printf("\n 您输入的位置序号大于有效结点个数\n\n");return ERROR;}while(head<tail){p=q[head++];if(num==tail-2)break;if(p->lchild)q[tail++]=p->lchild; if(p->rchild)q[tail++]=p->rchild;}printf("%5s 请输入新的结点值: "," ");while(1){fflush(stdin);for(k=0;k<20;k++){ str[k]=getchar(); if(str[k]=='\n')break;}if(k==0)printf("%5s 请输入一个字符后再按Enter 键: "," "); if(k==1)break;if(k>1)printf("%5s 您只能输入一个字符: "," ");}q[num]->data=str[0];printf("\n 修改成功\n");n=1;return OK;}//Modifyint MainMenu(){ // 主菜单函数system("cls");int choose;char str[20];n； r-t4"F/H\ 次一次一次一次一次一次一次一次次一次一次一次次一次一次一次次一次一次一次次一次一次一次”'printf("\n\t\t\t 计本102 卢荣盼1018014052");printf （"\n\t\t\t [1] 建立空树 \n"）;printf （"\n\t\t\t [2] 构造二叉树 \n"）;printf （"\n\t\t\t [3] 显示树状二叉树\n"）;printf （"\n\t\t\t [4] 遍历二叉树 ->>进入子菜单 \n"）;printf （"\n\t\t\t [5] 查看二叉树信息 ->>进入子菜单 \n"）; printf （"\n\t\t\t[6]对二叉树进行操作 ->> 进入子菜单 \n"）;printf （"\n\t\t\t [0] 退出程序 "）;n ； r-t4"F/H \ 次一次一次一次一次一次一次一次次一次一次一次次一次一次一次次一次一次一次次一次一次一次”\・printf("\n\t\t\t 请输入你的选择 : "); while(1){ scanf("%s",str);if(strcmp(str,"0")==0||strcmp(str,"1")==0||strcmp(str,"2")==0||strcmp(str,"3")==0||strcmp(str,"4")==0||strcmp(str,"5")==0||strcmp(str,"6")==0){ choose=atoi(str);break;}else{printf("\t\t\t 选择错误请重新输入 : ");}}if(choose==0){printf("\n\n\t ---- --- 谢谢使用本程序---------------------------------- \n\n");}return choose;}//MainMenu()int Menu （）｛ //主菜单函数system （"cls"）;int choose;char str[20];n ； r-t4"F/H \ 次一次一次一次一次一次一次一次次一次一次一次次一次一次一次次一次一次一次次一次一次一次”'printf （"\n\t\t\t 请选择对应的选项按对应的方式遍历二叉树 "）;printf("\n\t\t\t\t[1] 按先序 (递归 )遍历二叉树 \n");printf("\n\t\t\t\t[2] 按中序 (递归 )遍历二叉树\n"); printf("\n\t\t\t\t[3] 按后序 (递归 )遍历二叉树 \n"); 按先序 （非递归 ）遍历二叉树 \n"）; 按中序 （非递归 ）遍历二叉树 \n"）; 按后序 （非递归 ）遍历二叉树 \n"）;按层次 （非递归 ）遍历二叉树 \n"）;printf("\n\t\t\t\t[0] 返回主菜单 ");printf("\t\t\t 请输入你的选择 : "); while(1){printf("\n\t\t\t* *一*一*一*一*一*一**一*一*一**一*一*一**一*一*一**一*一*, *n );printf("\n\t\t\t\t[4]printf("\n\t\t\t\t[5]printf("\n\t\t\printf("\n\t\t\t**一*一*一*一*一*一**一*一*一**一*一*一**一*一*一**一*一*, *\n");scanf("%s",str);if(strcmp(str,"0")==0||strcmp(str,"1")==0||strcmp(str,"2")==0||strcmp(str,"3")==0||strcmp(str,"4")==0||strcmp(str,"5")==0||strcmp(str,"6")==0||strcmp(str,"7")==0){choose=atoi(str);break;}else{printf("\t\t\t 选择错误请重新输入 : ");}}return choose;}//Menu()int Menu1(){//查看二叉树信息菜单 system("cls");int choose;char str[20],str1[20]; * 一* 一* 一* 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一*、* 一* 一* 一* 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一* 一** 一* 一*伙一*一*一*・ 111 /Jprintf("\n\t [1] 返回根结点值printf("\n\t [3] 二叉树的总结点个数printf("\n\t [5] 二叉树中度为 1 的结点个数printf("\n\t [7] 某一值的结点个数及位置printf("\n\t [9] 二叉树中某结点的右孩子printf("\n\t [11] 二叉树中某结点的右兄弟printf("\n\t [0] 返回主菜单 \n"); printf("\t*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=*=*=**=**=*=*=**=* *=*=*=*=*\n"); printf("\t\t 请输入你的选择 : ");while(1){ scanf("%s",str); choose=atoi(str);itoa(choose,str1,10);if(choose>0&&choose<=12&&strcmp(str,str1)==0||strcmp(str,"0")==0)break;else{printf("\t\t 选择错误请重新输入 : ");}printf("\n\t**一*“ );printf("\n\t请选择对应的选项查看当前二叉树的信息 "); [2] 二叉树的深度 \n"); [4]二叉树中度为 2 的结点个数 \n"); [6] 二叉树中叶子结点个数 \n");[8] 二叉树中某结点的左孩子 \n"); [10] 二叉树中某结点的左兄弟 \n"); [12] 二叉树中某结点的双亲 \n");} return choose;}//Menu1()int Menu2(){ //主菜单函数system("cls");int choose;char str[20];printf("\n\t\t\t *=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*");; printf("\n\t\t\t 请选择对应的选项对二叉树进行操作"); printf("\n\t\t\t *=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*");printf("\n\t\t\t\t[1] printf("\n\t\t\t\t[2] printf("\n\t\t\t\t[3] printf("\n\t\t\t\t[4]删除某一结点\n"); 对某一结点生成子树\n"); 修改某一结点值\n"); 清空二叉树\n"); 销毁二叉树\n");返回主菜单");*=*=*=*=*=*=*=**=*=*=**=*=*=**=*=*=*");printf("\n\t\t\t\t[5] printf("\n\t\t\t\t[0] printf("\n\t\t\tprintf("\n\t\t\t 请输入你的选择: "); while(1){scanf("%s",str);if(strcmp(str,"0")==0||strcmp(str,"1")==0||strcmp(str,"2")==0||strcmp(str,"3")==0||strcmp(str,"4")==0||strcmp(str,"5")==0){ choose=atoi(str);break;} else{printf("\t\t\t 选择错误请重新输入: ");} } return choose;}//Menu2() void main(){system("color e0");BiTree T=NULL;int num,l,h,choose,flag=0,i=0,j=0,n;TElemType ch;while((choose=MainMenu())!=0){switch(choose){case 1:if(flag==2){printf(" 您已清空了之前的二叉树,目前为空树, 无须再建立空树!\n\n");}else{ if(flag==0){InitBiTree(T);flag=1;} else{printf(" 您之前已经建过空树,若想重建,请先销毁当前的树!\n\n");}}system("pause");break;case 2:if(!T)printf(" 您还没有建树，请先建树!\n\n");else{if(T->next)printf(" 二叉树已存在，若想重建，请先清空当前的二叉树!\n\n");else{system("cls");CreateBiTree(T->next,i,j,ch);printf("\n\n 二叉树创建完成!\n\n");}}system("pause");break;case 3:if(!T)printf(" 您还没有建树，请先建树!\n\n");else{l=0;h=0;if(T->next){printf("\n 当前二叉树的树状图如下:\n\n");}Lev_Traverse(T->next,TreeDepth(T->next,l,h));}system("pause");break;case 4:if(!T){printf(" 您还没有建树，请先建树!\n\n");system("pause");}else{if(!T->next){printf(" 二叉树目前为空树，请创建非空树后再遍历!\n\n");system("pause");}else{while((choose=Menu())!=0){l=0;h=0;printf("\n 当前二叉树的树状图如下:\n\n");Lev_Traverse(T->next,TreeDepth(T->next,l,h));switch(choose){case 1:FirstPrint(T->next,i);printf("\n\n");system("pause");break;case 2:MiddlePrint(T->next,i);printf("\n\n");system("pause");break;case 3:LastPrint(T->next,i);printf("\n\n");system("pause");break;case 4:PreOrderTraverse(T->next);system("pause");break;case 5:InOrderTraverse(T->next);system("pause");break;case 6:PostOrderTraverse(T->next);system("pause");break;case 7:LevelOrderPrint(T->next);printf("\n\n");system("pause");break;default:exit(ERROR);}}}}break;case 5:if(!T){printf(" 您还没有建树，请先建树!\n\n");system("pause");}else{if(!T->next){printf(" 二叉树目前为空树，请创建非空树后再查看信息!\n\n");system("pause");}else{while((choose=Menu1())!=0){l=0;h=0;printf("\n 当前二叉树的树状图如下:\n\n");Lev_Traverse(T->next,TreeDepth(T->next,l,h));switch(choose){case 1:GetRootElem(T->next);system("pause");break;case 2:printf(" 当前二叉树的深度为: %d\n\n",TreeDepth(T->next,l,h));system("pause");break;case 3:printf("\n 二叉树中有效结点的个数为: %d\n\n",GetElemSum(T->next));system("pause");break;case 4:printf("\n 二叉树中度为 2 的结点个数为: %d\n\n",GetLeafNum(T->next)-1);system("pause");break;case 5:printf("\n 二叉树中度为1的结点个数为: %d\n\n",GetElemSum(T->next)-2*GetLeafNum(T->next)+1);system("pause");break;case 6:printf("\n 二叉树中叶子结点个数为: %d\n\n",GetLeafNum(T->next));system("pause");break;case 7:printf(" 请输入要统计的元素: ");fflush(stdin);scanf("%c",&ch);GetElemNum(T->next,ch);system("pause");break;case 8:Lchild(T->next,GetElemSum(T->next));system("pause");break;case 9:Rchild(T->next,GetElemSum(T->next));system("pause");break;case 10:LBrother(T->next,GetElemSum(T->next));system("pause");break;case 11:RBrother(T->next,GetElemSum(T->next));system("pause");break;case 12:Partents(T->next,GetElemSum(T->next));system("pause");break;default:exit(ERROR);}}}}break;case 6:if(!T){printf(" 您还没有建树，请先建树!\n\n");system("pause");}else{if(!T->next){printf(" 二叉树目前为空树，请创建非空树后再对树进行操作!\n\n");system("pause");}else{ while((choose=Menu2())!=0){ if(choose!=4&&choose!=5){system("cls");l=0;h=0;printf("\n 当前二叉树的树状图如下:\n\n");Lev_Traverse(T->next,TreeDepth(T->next,l,h));printf("\n 二叉树中有效结点的个数为: %d\n\n",GetElemSum(T->next));printf(" 当前二叉树的深度为: %d\n\n",h);} switch(choose){case 1:num=GetElemSum(T->next);TreeDelete(T->next,GetElemSum(T->next));if(num!=GetElemSum(T->next)){l=0;h=0;printf("\n 删除后二叉树的树状图如下:\n\n");Lev_Traverse(T->next,TreeDepth(T->next,l,h));printf("\n 二叉树中有效结点的个数为: %d\n\n",GetElemSum(T->next));printf(" 当前二叉树的深度为: %d\n\n",h);}system("pause");break;case 2:num=GetElemSum(T->next);TreeInsert(T->next,GetElemSum(T->next));if(num!=GetElemSum(T->next)){l=0;h=0;printf("\n 插入后二叉树的树状图如下:\n\n");Lev_Traverse(T->next,TreeDepth(T->next,l,h));printf("\n 二叉树中有效结点的个数为: %d\n\n",GetElemSum(T->next));printf(" 当前二叉树的深度为: %d\n\n",h);}system("pause");break;case 3:Modify(T->next,GetElemSum(T->next),n);if(n==1){l=0;h=0; printf("\n 修改后二叉树的树状图如下:\n\n");Lev_Traverse(T->next,TreeDepth(T->next,l,h));printf("\n 二叉树中有效结点的个数为: %d\n\n",GetElemSum(T->next));printf(" 当前二叉树的深度为: %d\n\n",h);}system("pause");break;case 4:h=0;ClearBiTree(T->next,GetElemSum(T->next),h);flag=2;break;case 5:DestroyTree(T,T->next);flag=0;break; default:exit(ERROR);}if(choose==4){printf("\n\t 您已清空了当前的二叉树,程序将退回到主菜单,请重新建树后再回本菜单操作!\n\n");system("pause");break;} if(choose==5){printf("\n\t 您已销毁了当前的二叉树,程序将退回到主菜单,请重新建树后再回本菜单操作!\n\n");system("pause");break;}}}}break;default:exit(ERROR);}。
