数据结构-实验五讲义(2)-二叉树的基本操作

数据结构实验报告实验五二叉树的操作班级：12卓越6班学号：***********名：***任课教师：***计算机与信息工程学院2014年5月13 日实验五二叉树的操作一、实验目的1．进一步掌握指针变量、动态变量的含义；2．掌握二叉树的结构特征，以及各种存储结构的特点及适用范围；3．掌握用指针类型描述、访问和处理二叉树的运算。

二、实验要求1．按实验内容编写实验的程序，主程序以菜单形式运行。

2．上机调试运行本程序。

3．保存和打印出程序的运行结果，并结合程序进行分析。

4．提交源程序和运行结果。

三、实验内容1．创建以二叉链表作存储结构的二叉树；2．按中序遍历二叉树；3．按层次遍历二叉树；4．计算二叉树的单枝结点数；5．交换二叉树的左右子树。

解：//声明类BiTree及定义结构BiNode,文件名为bitree.h#ifndef BITREE_H#define BITREE_H//int num;template <class T>struct BiNode //二叉树的结点结构{T data;BiNode<T> *lchild, *rchild;};template <class T>class BiTree{public:BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间BiNode<T>* Getroot(); //获得指向根结点的指针void PreOrder(BiNode<T> *root); //前序遍历二叉树void InOrder(BiNode<T> *root); //中序遍历二叉树void PostOrder(BiNode<T> *root); //后序遍历二叉树void LeverOrder(BiNode<T> *root); //层序遍历二叉树int depth(BiNode<T> *root); //求二叉树的深度void nodenum(BiNode<T> *root); //求二叉树的结点个数void leafnum(BiNode<T> *root); //求二叉树的叶子结点个数void empty( ); //判断二叉树是否为空int printnum( ); // 输出（全部、叶子或单分支）结点数void sbnodenum(BiNode<T> *root); //求二叉树的单分支结点个数void exchangetree(BiNode<T> *root); //交换二叉树的左右子树private:BiNode<T> *root; //指向根结点的头指针BiNode<T> *p;BiNode<T> *Creat( ); //有参构造函数调用void Release(BiNode<T> *root); //析构函数调用int num;};#endif//定义类中的成员函数，文件名为bitree.cpp#include<iostream>#include<string>#include"bietree.h"using namespace std;/**前置条件：二叉树不存在*输入：无*功能：构造一棵二叉树*输出：无*后置条件：产生一棵二叉树*/template<class T>BiTree<T>::BiTree( ){this->num=0;this->root = Creat( );}/**前置条件：二叉树已存在*输入：无*功能：释放二叉链表中各结点的存储空间*输出：无*后置条件：二叉树不存在*/template<class T>BiTree<T>::~BiTree(void){Release(root);}*前置条件：二叉树已存在*输入：无*功能：获取指向二叉树根结点的指针*输出：指向二叉树根结点的指针*后置条件：二叉树不变*/template<class T>BiNode<T>* BiTree<T>::Getroot( ){return root;}/**前置条件：二叉树已存在*输入：无*功能：前序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template<class T>void BiTree<T>::PreOrder(BiNode<T> *root) {if(root==NULL) return;else{cout<<root->data<<" ";PreOrder(root->lchild);PreOrder(root->rchild);}}*前置条件：二叉树已存在*输入：无*功能：中序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template <class T>void BiTree<T>::InOrder (BiNode<T> *root){if (root==NULL) return; //递归调用的结束条件else{InOrder(root->lchild); //中序递归遍历root的左子树cout<<root->data<<" "; //访问根结点的数据域InOrder(root->rchild); //中序递归遍历root的右子树}}/**前置条件：二叉树已存在*输入：无*功能：后序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template <class T>void BiTree<T>::PostOrder(BiNode<T> *root){if (root==NULL) return; //递归调用的结束条件else{PostOrder(root->lchild); //后序递归遍历root的左子树PostOrder(root->rchild); //后序递归遍历root的右子树cout<<root->data<<" "; //访问根结点的数据域}}/**前置条件：二叉树已存在*输入：无*功能：层序遍历二叉树*输出：二叉树中结点的一个线性排列*后置条件：二叉树不变*/template <class T>void BiTree<T>::LeverOrder(BiNode<T> *root){const int MaxSize = 100;int front = 0;int rear = 0; //采用顺序队列，并假定不会发生上溢BiNode<T>* Q[MaxSize];BiNode<T>* q;if (root==NULL) return;else{Q[rear++] = root;while (front != rear){q = Q[front++];cout<<q->data<<" ";if (q->lchild != NULL) Q[rear++] = q->lchild;if (q->rchild != NULL) Q[rear++] = q->rchild;}}}/**前置条件：空二叉树*输入：数据ch;*功能：初始化一棵二叉树,构造函数调用*输出：无*后置条件：产生一棵二叉树*/template <class T>BiNode<T>* BiTree<T>::Creat( ){BiNode<T>* root;T ch;cout<<"请输入创建一棵二叉树的结点数据"<<endl;cin>>ch;if (ch=="#") root = NULL;else{root = new BiNode<T>; //生成一个结点root->data=ch;root->lchild = Creat( ); //递归建立左子树root->rchild = Creat( ); //递归建立右子树}return root;}/**前置条件：二叉树已经存在*输入：无*功能：释放二叉树的存储空间，析构函数调用*输出：无*后置条件：二叉树不存在*/template<class T>void BiTree<T>::Release(BiNode<T>* root){if (root != NULL){Release(root->lchild); //释放左子树Release(root->rchild); //释放右子树delete root;}}/**前置条件：二叉树已经存在*输入：无*功能：求二叉树的深度*输出：二叉树的深度*后置条件：二叉树不变*/template<class T>int BiTree<T>::depth(BiNode<T> *root){int n,m;if(root==NULL) return 0;else{n=depth(root->lchild); //左子树的深度m=depth(root->rchild); //右子树的深度if (n>m)return n+1;elsereturn m+1;}}/**前置条件：二叉树已经存在*输入：无*功能：求二叉树的结点个数*输出：二叉树的结点个数*后置条件：二叉树不变*/template<class T>void BiTree<T>::nodenum(BiNode<T> *root){if(root==NULL) return;else{num++;nodenum(root->lchild); //左子树的结点个数nodenum(root->rchild); //右子树的结点个数}}*前置条件：二叉树已经存在*输入：无*功能：求二叉树2 的叶子结点个数*输出：二叉树的叶子结点个数*后置条件：二叉树不变*/template<class T>void BiTree<T>::leafnum(BiNode<T> *root){if(root==NULL) return;else{if(!(root->lchild) && !(root->rchild)) //判断是否为叶子结点num++;leafnum(root->lchild); //左子树中的叶子结点个数leafnum(root->rchild); //右子树中的叶子结点个数}}/*将全局变量num初始化为0*/template<class T>void BiTree<T>::empty( ){num=0;}输出全局变量num的值*/template<class T>int BiTree<T>::printnum( ){return num;}/**前置条件：二叉树已经存在*输入：无*功能：求二叉树的单分支结点个数*输出：二叉树的单分支结点个数*后置条件：二叉树不变*/template<class T>void BiTree<T>::sbnodenum(BiNode<T> *root){if(root==NULL) return;else{if((!(root->lchild) && (root->rchild))||((root->lchild) && !(root->rchild))) //判断是否为叶子结点num++;sbnodenum(root->lchild); //左子树中的叶子结点个数sbnodenum(root->rchild); //右子树中的叶子结点个数}}/**前置条件：二叉树已经存在*输入：无*功能：交换二叉树的左右子树*输出：无*后置条件：二叉树左右子树交换*/template<class T>void BiTree<T>::exchangetree(BiNode<T> *root){if(root==NULL) return;else{if((root->rchild)&&(root->lchild)) //判断左右叶子结点都存在{ p=root->lchild;root->lchild=root->rchild;root->rchild=p;}exchangetree(root->lchild); //左子树中的叶子结点个数exchangetree(root->rchild); //右子树中的叶子结点个数}}/* BiNode<T> * Q[20];BiNode<T> *q;int front=-1;int rear=-1;int n=0;int m=0;Q[++rear]=root;if(root==NULL)cout<<0;else{while(front!=rear){q=Q[++front];if(q->lchild==NULL && q->rchild!=NULL)m++;if(q->lchild!=NULL && q->rchild==NULL)n++;if(q->lchild!=NULL) Q[++rear]=q->lchild;if(q->rchild!=NULL) Q[++rear]=q->rchild;}}cout<<"单分支节点的个数为:"<<m+n<<endl;*///二叉树的主函数，文件名为bitreemain.cpp#include<iostream>#include<string>#include"bietree.cpp"using namespace std;void main(){BiTree<string> bt; //创建一棵树BiNode<string>* root = bt.Getroot( ); //获取指向根结点的指针int s=-1;while(s!=0){cout<<"1.前序遍历"<<endl;cout<<"2.中序遍历"<<endl;cout<<"3.后序遍历"<<endl;cout<<"4.层序遍历"<<endl;cout<<"5.树的深度"<<endl;cout<<"6.叶子节点个数"<<endl;cout<<"7.单分支结点个数"<<endl;cout<<"8.左右子树交换后的结果"<<endl;cout<<"0.退出"<<endl;cin>>s;switch(s){ case 1:bt.PreOrder(root);cout<<endl;break;case 2:bt.InOrder(root);cout<<endl;break;case 3:bt.PostOrder(root);cout<<endl;break;case 4:bt.LeverOrder(root);cout<<endl;break;case 5:cout<<"树的深度为："<<bt.depth(root)<<endl;break;case 6:bt.empty();bt.leafnum(root);cout<<"叶子结点个数为："<<bt.printnum()<<endl;break;case 7:bt.empty();bt.sbnodenum(root);cout<<"单分支结点个数为："<<bt.printnum()<<endl;break;case 8:bt.empty();bt.exchangetree(root);cout<<"左右子树交换后的结果：";bt.PreOrder(root);cout<<endl;break;case 0:exit(0);}}}。

二叉树的基本操作二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点。

二叉树在计算机领域中得到广泛应用，它的基本操作包括插入、删除、查找、遍历等。

1.插入操作：二叉树的插入操作是将一个新的节点添加到已有的二叉树中的过程。

插入操作会按照一定规则将新节点放置在正确的位置上。

插入操作的具体步骤如下：-首先，从根节点开始，比较新节点的值与当前节点的值的大小关系。

-如果新节点的值小于当前节点的值，则将新节点插入到当前节点的左子树中。

-如果新节点的值大于当前节点的值，则将新节点插入到当前节点的右子树中。

-如果当前节点的左子树或右子树为空，则直接将新节点插入到该位置上。

-如果当前节点的左子树和右子树都不为空，则递归地对左子树或右子树进行插入操作。

2.删除操作：二叉树的删除操作是将指定节点从二叉树中删除的过程。

删除操作有以下几种情况需要考虑：-如果待删除节点是叶子节点，则直接将其从二叉树中删除即可。

-如果待删除节点只有一个子节点，则将其子节点替换为待删除节点的位置即可。

-如果待删除节点有两个子节点，则需要找到其左子树或右子树中的最大节点或最小节点，将其值替换为待删除节点的值，然后再删除最大节点或最小节点。

3.查找操作：二叉树的查找操作是在二叉树中查找指定值的节点的过程。

查找操作的具体步骤如下：-从根节点开始，将待查找值与当前节点的值进行比较。

-如果待查找值等于当前节点的值，则返回该节点。

-如果待查找值小于当前节点的值，则在当前节点的左子树中继续查找。

-如果待查找值大于当前节点的值，则在当前节点的右子树中继续查找。

-如果左子树或右子树为空，则说明在二叉树中找不到该值。

4.遍历操作：二叉树的遍历操作是按照一定规则依次访问二叉树中的每个节点。

有三种常用的遍历方式：- 前序遍历（Preorder Traversal）：先访问根节点，然后递归地前序遍历左子树和右子树。

- 中序遍历（Inorder Traversal）：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

实验二二叉树操作
（一）实验内容
二叉树的建立和遍历。

（二）实验目的
1.进一步掌握指针变量的使用。

2.掌握二叉树的结构特征以及各种存储结构的特点及使用范围。

3.掌握用指针类型描述、访问和处理二叉树的运算。

4.掌握栈或队列的使用。

（三）实验题目
本实验要求实现以下功能：
1.按前序次序建立一棵二叉树，以‘＃’表示空。

2.中序、后序遍历该二叉树，输出遍历序列。

3.求出该二叉树的深度并输出，或求出该二叉树的叶子数目并输出。

4.试以栈为辅助存储结构实现二叉树的前序非递归算法或以队列为辅
助存储结构实现二叉树的层次遍历算法。

（四）实验仪器设备
1.学生每个一台PC机
2.已安装环境。

⼆叉树的基础操作⼆叉树 ⼀：创建以及初始化赋值：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即可。

二叉树基本操作实验报告实验名称二叉树基本操作实验目的1.熟悉二叉树结点的结构和二叉树的基本操作；2.掌握二叉树每种操作的具体实现；3.学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法；4.在二叉树基本操作的基础上掌握对二叉树的一些其它操作的具体实现方法；5.掌握构造哈夫曼树以及哈夫曼编码的方法。

实验内容编制一个演示二叉树创建、遍历、计算等操作的程序。

问题描述用数据结构相关知识，实现二叉树的定义和操作。

该程序包括二叉树结构类型以及对二叉树操作的具体的函数定义（包括：初始化二叉树、清空二叉树、检查二叉树是否为空、遍历二叉树（先序、后序、中序、层次）、求二叉树的深度、求二叉树所有节点数）。

问题分析该实验是基于C语言和数据结构知识基础的对二叉树的基本操作的检验，无需设计复杂的算法，程序语句也相对简单。

因此，我直接按要求定义了对二叉树操作的具体函数，并于主函数中实现对应的功能调用，其中，功能选择靠switch语句实现。

实验步骤1．需求分析本演示程序用VC++编写，完成二叉树的生成、遍历、计算等基本操作。

①输入的形式和输入值的范围：以字符（其中‘#’表示虚节点）的形式输入，以创建二叉树；在输入二叉树节点前，必须先确定该序列能正确创建二叉树。

②输出的形式：在所有三种操作中都显示操作是否正确以及操作后二叉树的内容。

③程序所能达到的功能：完成二叉树的生成、遍历（包括先序、后序、中序、层次四种方式）、计算等基本操作。

④测试数据：创建操作中依次输入a,b,d,#,g,#,#,#,c,e,#,#,f,#,#生成一个二叉树。

2．概要设计1）为了实现上述程序功能，需要定义二叉树的抽象数据类型：ADT BitTree {数据对象：由一个根节点和两个互不相交的左右子树构成数据关系：结点具有相同的数据类型及层次结构基本操作：Void BinTreeInit(BitTree *T)初始条件：无操作结果：初始化一棵二叉树Void BinTreeCreat(BitTree *T)初始条件：二叉树T已存在操作结果：按先序次序创建一棵二叉树2）本程序包含7个函数：①主函数main() ②初始化二叉树函数BinTreeInit() ③建立一棵二叉树函数BinTreeCreat() ④先序遍历函数PreOrderTraverse() ⑤中序遍历函数InOrderTraverse()⑥后序遍历函数PostOrderTraverse()⑦层次遍历函数LevelOrderTraverse()⑧求二叉树深度函数Countlevel()⑨检验空树函数BinTreeEmpty()⑩求节点数函数 Countnode()函数说明#include<stdio.h>#include<stdlib.h>typedef char Datatype;typedef struct NodeType{Datatype data;struct NodeType *lchild;struct NodeType *rchild;}BiTNode;typedef BiTNode * BinTree;//初始化二叉树。

实验五：二叉树的定义及基本操作（必做：基本2学时，扩展4学时）一、实验目的：.熟练掌握二叉树的二叉链表存储结构.掌握二叉树的非线性和递归性特点.熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现.掌握线索二叉树的定义和基本操作.加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力二、实验内容:（一）基本实验内容：.定义二叉树的链式存储结构；.实现二叉树的基本操作：建空树、销毁二叉树、生成二叉树(先序,中序或后序)、判二叉树是否为空、求二叉树的深度、求二叉树的根等基本算法；.实现二叉树的递归(先序、中序或后序)遍历算法；1．问题描述：利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作：.创建一棵空二叉树；.对一棵存在的二叉树进行销毁；.根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树；.判断某棵二叉树是否为空；.求二叉树的深度；.求二叉树的根结点，若为空二叉树，则返回一特殊值；.二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被访问一次；.编写主程序，实现对各不同的算法调用；其他算法的描述省略，参见实现要求说明。

2．实现要求：.“构造空二叉树算法”操作结果：构造一个空二叉树T；.“销毁二叉树算法”初始条件:二叉树T存在；操作结果:销毁二叉树T；.“创建二叉树算法”初始条件:可以根据先序、中序和后序输入二叉树中结点的值（可为字符型或整型）；操作结果:以选择的某种次序建立二叉树T；.“判二叉树是否为空算法”初始条件:二叉树T存在；操作结果:若T为空二叉树,则返回TRUE,否则FALSE；.“求二叉树的深度算法”初始条件:二叉树T存在；操作结果:返回T的深度；.“求二叉树的根算法”初始条件:二叉树T存在；操作结果:返回T的根；.“先序递归遍历算法”初始条件:二叉树T存在,Visit是对结点操作的应用函数；操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次；.“中序递归遍历算法”初始条件:二叉树T存在,Visit是对结点操作的应用函数；操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次；.“后序递归遍历算法”初始条件:二叉树T存在,Visit是对结点操作的应用函数；操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次；（二）扩展实验内容：利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作：.求某一个结点的双亲结点,求某一个结点的左孩子（或右孩子）结点；求某一个结点的左兄弟（或右兄弟）算法；.利用栈，实现二叉树的非递归(先序、中序或后序)遍历算法；.利用队列，实现层序递归遍历二叉树；.定义线索二叉树的链式存储结构，建立线索二叉树，实现线索二叉树的插入和删除操作；1．问题描述：.求二叉树中某个指定结点的父结点，当指定结点为根时，返回一特殊值；.求二叉树中某个指定结点的左孩子结点，当指定结点没有左孩子时，返回一特殊值；.求二叉树中某个指定结点的右孩子结点，当指定结点没有右孩子时，返回一特殊值；.实现中序非递归遍历二叉树算法一定采用二叉链表存储结构，并且仿照递归算法执行过程中递归工作栈的状态变化状况直接实现栈的操作，写出相应的非递归算法；中序和后序类似；.编写主程序，实现对各不同的算法调用。

c语言数据结构二叉树的基本操作-回复C语言数据结构：二叉树的基本操作概述：二叉树是一种常用的数据结构，在计算机科学中广泛应用于各种算法和问题的解决方案中。

它的特点是每个节点至多有两个子节点，即左子节点和右子节点，且子节点的顺序不能颠倒。

本文将介绍常见的二叉树基本操作，包括创建二叉树、插入节点、删除节点、查找节点、遍历等。

1. 创建二叉树：创建一个二叉树的方法是从根节点开始，逐个插入子节点。

首先定义一个二叉树的结构体，包含一个值和指向左右子节点的指针。

然后使用malloc 函数分配内存空间，并将值赋给根节点的指针。

接着创建左子节点和右子节点，将子节点的指针分别赋给根节点的左右指针。

这样就完成了一个简单的二叉树的创建。

2. 插入节点：插入节点是在现有的二叉树上新增一个节点。

首先找到插入节点的位置，可以从根节点开始逐级比较。

如果插入节点的值小于当前节点，则向左子树查找，否则向右子树查找，直到找到合适的位置。

然后创建一个新节点，并将新节点的指针赋给找到位置的节点的左或右指针。

3. 删除节点：删除节点是将现有的二叉树中的一个节点删除。

首先找到要删除的节点位置，可以通过比较节点的值进行查找，直到找到要删除的节点。

然后根据删除节点的情况分三种情况考虑：若删除节点为叶子节点，直接删除即可；若删除节点只有一个子节点，将子节点的指针赋给删除节点的父节点，然后删除删除节点；若删除节点有两个子节点，需要找到删除节点的左子树中的最大节点或右子树中的最小节点，将其值赋给删除节点，然后删除此最大或最小节点。

4. 查找节点：查找节点是在现有的二叉树中寻找一个特定的节点。

与插入和删除类似，从根节点开始比较节点的值，若要查找的节点值小于当前节点，则继续向左子树查找，否则向右子树查找，直到找到要查找的节点。

若找到了节点，返回此节点的指针；若未找到，返回空指针。

5. 遍历：遍历二叉树是按照一定的顺序访问树中的所有节点。

常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。

实验五二叉树的存储表示和基本操作实验内容1. 二叉树的二叉链表的存储结构—————二叉树的二叉链表存储表示————————typedef struct node{ElemType data; /*数据元素*/struct node *lchild; /*指向左孩子*/struct node *rchild; /*指向右孩子*/} BTNode;2. 二叉树的基本操作（1）创建操作：创建一棵二叉树。

（2）查找操作：查找二叉树中值为x的结点。

（3）查找左孩子操作：查找二叉树中值为x的结点的左孩子。

（4）查找右孩子操作：查找二叉树中值为x的结点的右孩子。

（5）求深度操作：求二叉树的深度。

（6）求宽度操作：求二叉树的宽度。

（7）求结点个数操作：求二叉树的结点个数。

（8）求叶子结点个数操作：求二叉树的叶子结点个数。

（9）输出操作：以括号表示法输出二叉树。

3. 链式队列操作实现的步骤（1）实现将链式队列的存储结构和基本操作程序代码。

（2）实现main主函数。

4.程序代码完整清单#include <stdio.h>#include <malloc.h>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data; /*数据元素*/struct node *lchild; /*指向左孩子*/struct node *rchild; /*指向右孩子*/} BTNode;//基本操作函数声明void CreateBTNode(BTNode *&b,char *str); /*创建一棵二叉树*/ BTNode *FindNode(BTNode *b,ElemType x); /*查找二叉树的结点*/ BTNode *LchildNode(BTNode *p); /*查找二叉树结点的左孩子*/ BTNode *RchildNode(BTNode *p); /*查找二叉树结点的右孩子*/ int BTNodeDepth(BTNode *b); /*求二叉树的深度*/void DispBTNode(BTNode *b); /*输出二叉树*/int BTWidth(BTNode *b); /*求二叉树的宽度*/int Nodes(BTNode *b); /*求二叉树结点个数*/int LeafNodes(BTNode *b); /*求二叉树叶子结点个数*/void main(){BTNode *b,*p,*lp,*rp;;CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");printf("\n");printf("(1)输出二叉树:");DispBTNode(b);printf("\n");printf("(2)'H'结点:");p=FindNode(b,'H');if (p!=NULL){lp=LchildNode(p);if (lp!=NULL)printf("左孩子为%c ",lp->data);elseprintf("无左孩子");rp=RchildNode(p);if (rp!=NULL)printf("右孩子为%c",rp->data);elseprintf("无右孩子");}printf("\n");printf("(3)二叉树b的深度:%d\n",BTNodeDepth(b));printf("(4)二叉树b的宽度:%d\n",BTWidth(b));printf("(5)二叉树b的结点个数:%d\n",Nodes(b));printf("(6)二叉树b的叶子结点个数:%d\n",LeafNodes(b));printf("\n");}void CreateBTNode(BTNode *&b,char *str) /*由str串创建二叉链*/{BTNode *St[MaxSize],*p=NULL;int top=-1,k,j=0;char ch;b=NULL; /*建立的二叉树初始时为空*/ch=str[j];while (ch!='\0') /*str未扫描完时循环*/{switch(ch){case '(':top++;St[top]=p;k=1; break; /*为左结点*/case ')':top--;break;case ',':k=2; break; /*为右结点*/default:p=(BTNode *)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if (b==NULL) /*p指向二叉树的根结点*/b=p;else /*已建立二叉树根结点*/{switch(k){case 1:St[top]->lchild=p;break;case 2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode *FindNode(BTNode *b,ElemType x) /*查找二叉树的结点操作结果：返回data*/ { /* 域为x的结点指针*/BTNode *p;if (b==NULL)return NULL;else if (b->data==x)return b;else{p=FindNode(b->lchild,x);if (p!=NULL)return p;elsereturn FindNode(b->rchild,x);}}BTNode *LchildNode(BTNode *p) /*查找二叉树结点的左孩子操作结果：返回*p*/{ /*结点的左孩子结点指针*/return p->lchild;}BTNode *RchildNode(BTNode *p) /*查找二叉树结点的右孩子操作结果：返回*p结*/ { /*点的右孩子结点指针*/return p->rchild;}int BTNodeDepth(BTNode *b) /*求二叉树b的深度*/{int lchilddep,rchilddep;if (b==NULL)return(0); /*空树的高度为0*/ else{lchilddep=BTNodeDepth(b->lchild); /*求左子树的高度为lchilddep*/rchilddep=BTNodeDepth(b->rchild); /*求右子树的高度为rchilddep*/return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1);}}void DispBTNode(BTNode *b) /*以括号表示法输出二叉树*/{if (b!=NULL){printf("%c",b->data);if (b->lchild!=NULL || b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if (b->rchild!=NULL) printf(",");DispBTNode(b->rchild);printf(")");}}}int BTWidth(BTNode *b) /*求二叉树b的宽度*/{struct{int lno; /*结点的层次编号*/BTNode *p; /*结点指针*/} Qu[MaxSize]; /*定义顺序非循环队列*/int front,rear; /*定义队首和队尾指针*/ int lnum,max,i,n;front=rear=0; /*置队列为空队*/if (b!=NULL){rear++;Qu[rear].p=b; /*根结点指针入队*/Qu[rear].lno=1; /*根结点的层次编号为1*/while (rear!=front) /*队列不为空*/{front++;b=Qu[front].p; /*队头出队*/lnum=Qu[front].lno;if (b->lchild!=NULL) /*左孩子入队*/{rear++;Qu[rear].p=b->lchild;Qu[rear].lno=lnum+1;}if (b->rchild!=NULL) /*右孩子入队*/{rear++;Qu[rear].p=b->rchild;Qu[rear].lno=lnum+1;}}max=0;lnum=1;i=1;while (i<=rear){n=0;while (i<=rear && Qu[i].lno==lnum){n++;i++;}lnum=Qu[i].lno;if (n>max) max=n;}return max;}elsereturn 0;}int Nodes(BTNode *b) /*求二叉树b的结点个数*/{int num1,num2;if (b==NULL)return 0;else if (b->lchild==NULL && b->rchild==NULL)return 1;else{num1=Nodes(b->lchild);num2=Nodes(b->rchild);return (num1+num2+1);}}int LeafNodes(BTNode *b) /*求二叉树b的叶子结点个数*/{int num1,num2;if (b==NULL)return 0;else if (b->lchild==NULL && b->rchild==NULL)return 1;else{num1=LeafNodes(b->lchild);num2=LeafNodes(b->rchild);return (num1+num2);}}5. 运行结果清单(1)输出二叉树：A ( B( D , E ( H ( J , K ( L , M ( , N ) ) ) ) ), C ( F , G ( , I ) ) )(2)’H’结点：左结点为J 右结点为K(3)二叉树b的深度：7(4)二叉树b的宽度：4(5)二叉树b的结点个数：14(6) 二叉树b的叶子结点个数：6。