数据结构实验六二叉树操作代码实现

数据结构⼆叉树程序代码#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define MAX_TREE_SIZE 100//⼆叉树的最⼤结点#define TRUE 1#define FALSE 0#define OVERFLOW -2#define telemtype char#define selemtype chartypedef telemtype sqbitree[MAX_TREE_SIZE];//0号单元储存根结点sqbitree bt;typedef struct bitnode{telemtype data;struct bitnode *lchild,*rchild;}bitnode,*bitree;bitree T;typedef struct{bitree *base;bitree *top;int stacksize;}sqstack;sqstack s;void menu();//菜单void initstack(sqstack &s);//初始化void clearstack(sqstack &s);//置空栈void push(sqstack &s,bitnode e);//⼊栈void pop(sqstack &s,bitnode e);//出栈void gettop(sqstack &s);//取栈顶元素int stackempty(sqstack s);//判断栈是否为空void createbitree(bitree &T);//创建树void traversetree(bitree T);//遍历树void preordertraverse(bitree T);//先序遍历void inordertraverse(bitree T);//中序遍历void postordertraverse(bitree T);//后序遍历int treedepth(bitree T);//求树深度void treenature(bitree T);//---------------------主函数----------------------void main(){int a;initstack(s);for(;;){menu();printf("请输⼊要操作的数字\n");scanf("%d",&a);switch(a){case 1:createbitree(T);break;case 2:traversetree(T);break;case 3:treenature(T);break;case 4:exit(0);break;default:printf("please input a number again!");}}}//---------------------⼦函数----------------------------void menu()//菜单{printf("************菜单*************\n");printf("********1、树的创建*********\n");printf("********2、树的遍历*********\n");printf("********3、树的属性*********\n");printf("********4、退出*********\n");}void initstack(sqstack &s)//初始化{s.base=(bitree*)malloc(STACK_INIT_SIZE*sizeof(bitree));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;}void clearstack(sqstack &s)//置空栈{s.top=s.base;}void push(sqstack &s,bitree e)//⼊栈{if(s.top-s.base>=s.stacksize){s.base=(bitree*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(bitree)); if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;}void pop(sqstack &s,bitree &e)//出栈{if(s.top==s.base)printf("栈为空!\n");e=*--s.top;}void gettop(sqstack &s,bitree &e)//取栈顶元素{if(s.top==s.base)printf("栈为空!\n");e=*(s.top-1);}int stackempty(sqstack s)//判断栈为空{if(s.top==s.base)return TRUE;else return FALSE;}void createbitree(bitree &T)//创建树{telemtype ch;telemtype a;a=getchar();scanf("%c",&ch);if(ch=='#')T=NULL;else{if(!(T=(bitnode*)malloc(sizeof(bitnode))))exit(OVERFLOW);T->data=ch;createbitree(T->lchild);createbitree(T->rchild);}}void traversetree(bitree T)//遍历树{int n,i;for(i=0;i<4;i++){printf("************树的遍历************\n");printf("**********1、先序遍历***********\n"); printf("**********2、中序遍历***********\n"); printf("**********3、后序遍历***********\n"); printf("**********4、退出应⽤***********\n"); scanf("%d",&n);switch(n){case 1:preordertraverse(T);break;case 2:inordertraverse(T);break;case 3:postordertraverse(T);break;case 4:printf("树的遍历已退出!\n");break; default:printf("输⼊有误，请重新输⼊!\n");}}}/*void preordertraverse(bitree T)//递归先序遍历{if(T){printf("%c",T->data);preordertraverse(T->lchild); preordertraverse(T->rchild);}printf("\n");}*/void preordertraverse(bitree T)//⾮递归先序遍历{sqstack s;initstack(s);bitree p;p=T;while(p||!stackempty(s)){if(p){printf("%c",p->data);p=p->lchild;}else p=p->rchild;}printf("\n");}/*void inordertraverse(bitree T)//递归中序遍历{if(T){inordertraverse(T->lchild);printf("%c",T->data);inordertraverse(T->rchild);printf("\n");}}*/void inordertraverse(bitree T)//⾮递归中序遍历{sqstack s;initstack(s);bitree p;p=T;while(p||!stackempty(s)){if(p){ push(s,p);p=p->lchild;}else{pop(s,p);printf("%c",p->data);p=p->rchild;}}printf("\n");}/*void postordertraverse(bitree T)//递归后序遍历{if(T){postordertraverse(T->lchild); postordertraverse(T->rchild);printf("%c",T->data);printf("\n");}}*/void postordertraverse(bitree T)//⾮递归后序遍历{bitree p;initstack(s);p = T;int tag;while(p||!stackempty(s)){if(p){push(s,p);tag=0;p = p->lchild;}else{if(tag==1){pop(s,p);printf("%c",p->data);p = NULL;}else{gettop(s,p);tag=1;p = p->rchild;}}}printf("\n");}int treedepth(bitree T)//求树深度{int depthall,depthl,depthr;if(!T)depthall = 0;else{depthl=treedepth(T->lchild);depthr=treedepth(T->rchild);depthall=(depthl > depthr ? depthl:depthr)+1;}//printf("树的深度为：%d\n",depthall);return depthall;}void treenature(bitree T)//树的结点数，叶⼦数，⼀度结点数，树的深度等属性。

实验名称二叉树的基本操作实验日期实验成绩1、实验目的：1. 掌握二叉树链表的结构和二叉树的建立过程2. 掌握用递归方法实现二叉树遍历的操作2、实验内容：1、编写一个程序实现二叉树的各种运算，并完成如下功能：（1）输出二叉树b；（b为下图所示的二叉树）（2）输出H节点的左、右孩子节点值；（3）输出二叉树b的深度；（4）输出二叉树b的节点个数；（5）输出二叉树b的叶子节点个数；（6）释放二叉树b。

2、编写一个程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归算法。

并以第1题图所示的二叉树b给出求解结果。

3、核心算法或代码片段：代码一：#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);void DispBTNode(BTNode *b);BTNode *FindNode(BTNode *b, ElemType x);BTNode *LchildNode(BTNode *p);BTNode *RchildNode(BTNode *p);int BTNodeDepth(BTNode *b);int Nodes(BTNode *b);int LeafNodes(BTNode *b);void DestroyBTNode(BTNode *&b);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];}}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(")");}}}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);//求左子树的高度为lchilddeprchilddep = BTNodeDepth(b->rchild);//求右子树的高度为rchilddepreturn (lchilddep>rchilddep) ? (lchilddep + 1) : (rchilddep + 1);}}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);}}void DestroyBTNode(BTNode *&b) //摧毁树{if (b != NULL){DestroyBTNode(b->lchild);DestroyBTNode(b->rchild);free(b);}}int 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", Nodes(b));printf(" (5)二叉树b的叶子节点个数:%d\n", LeafNodes(b));printf(" (6)释放二叉树b\n");DestroyBTNode(b);return 0;}代码二：#include<iostream>#define maxsize 50using namespace std;class node{private:char data;node* lchild;node* rchild;public:void createnode(node *&,char *);//先序遍历void fnode(node* b){if(b!=NULL){cout << b->data ;fnode(b->lchild);fnode(b->rchild);}}//中序遍历void mnode(node* b){if(b!=NULL){mnode(b->lchild);cout << b->data ;mnode(b->rchild);}}//后序遍历void lnode(node* b){if(b!=NULL){lnode(b->lchild);lnode(b->rchild);cout << b->data ;}}void fnode1(node *);void mnode1(node *);void lnode1(node *);void all(node *);};void node::createnode(node* &b,char* a) {node *st[maxsize],*p;int top=-1,k,j=0;char ch;b=NULL;ch=a[j];while(ch!='\0'){switch(ch){case '(':top++;st[top]=p;k=1;break;case ')':top--;break;case ',':k=2;break;default:p=new node;p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL){b=p;}else{switch(k){case 1:st[top]->lchild=p;break;case 2:st[top]->rchild=p;break;}}}j++;ch=a[j];}}int main(){node *b;char a[]="A(B(D,E(H(J,K(L,M(,N))),)),C(F,G(,I)))";b->createnode(b,a);cout << "递归先序编历：";b->fnode(b);cout << endl ;cout << "递归中序编历：";b->mnode(b);cout << endl ;cout << "递归后序编历：";b->lnode(b);cout << endl ;cout << endl ;}一：二:总结体会：在第一个实验对树的操作，利用树广义表的表示法输入一个str，对str进行遍历，通过对括号和字母的判断创建二叉树CreateBTNode()，输出二叉树DispBTNode()同样采用广义表表示法，在找寻某一结点的左右孩子结点首先FindNode()对是否存在左右孩子,由于该二叉树存储采用的二叉链表所以通过指针指向输出左右孩子，在输出二叉树DispBTNode(),找左右孩子FindNode()，计算深度BTNodeDepth(),计算结点数Nodes(),都采用了函数的递归，都是利用左右孩子指针进行操作，进行对整个数的遍历。

数据结构二叉树的基本操作代码x#include<iostream>using namespace std;//二叉树的结构struct TreeNode{int data;//节点的值TreeNode *left;//指向左子树TreeNode *right;//指向右子树};//插入节点void insert(TreeNode *&tree, int val){if(tree == NULL){tree = new TreeNode;tree->data = val;tree->left = tree->right = NULL;}else if(val<=tree->data)//小于根节点的值则插入到左子树 insert(tree->left, val);else if(val>tree->data)//大于根节点的值则插入到右子树 insert(tree->right,val);}//查找节点TreeNode* find(TreeNode *tree,int val){if (tree == NULL)//树为空，无法查找return NULL;else if (val == tree->data)//值和节点的值相等，返回该节点return tree;else if (val < tree->data)//值小于节点的值，查找左子树 return find(tree->left,val);else if (val > tree->data)//值大于节点的值，查找右子树 return find(tree->right,val);elsereturn NULL;//无法查找}//遍历二叉树//先序遍历void preOrder(TreeNode *tree){if(tree != NULL){cout<< tree->data <<'t'; //先访问根节点preOrder(tree->left); //再遍历左子树 preOrder(tree->right); //最后遍历右子树 }}//中序遍历void inOrder(TreeNode *tree){if(tree != NULL){inOrder(tree->left); //先遍历左子树 cout<< tree->data <<'t'; //再访问根节点inOrder(tree->right); //最后遍历右子树 }}//后序遍历void postOrder(TreeNode *tree){if(tree != NULL){postOrder(tree->left); //先遍历左子树 postOrder(tree->right); //再遍历右子树 cout<< tree->data <<'t'; //最后访问根节点 }}//查找最大值TreeNode* findMax(TreeNode *tree){if(tree == NULL)return NULL;else if(tree->right == NULL)return tree;elsereturn findMax(tree->right);}//查找最小值TreeNode* findMin(TreeNode *tree){if(tree == NULL)return NULL;else if(tree->left == NULL)return tree;elsereturn findMin(tree->left);}//删除节点void remove(TreeNode *&tree, int val){if(tree == NULL)return;else if(val < tree->data)remove(tree->left, val);else if(val > tree->data)remove(tree->right, val);else//找到要删除的节点{if(tree->left != NULL && tree->right != NULL)//左右子树均不为空{TreeNode *temp = tree;TreeNode *max = findMax(tree->left);//查找左子树的最大结点tree->data = max->data;//将最大结点的值替换到要删除的节点remove(temp->left, max->data);//将最大结点删掉}else//只有一边的子节点不为空或者左右节点都为空{TreeNode *temp = tree;if(tree->left == NULL)//如果左节点为空，就将右节点提升 tree = tree->right;else if(tree->right == NULL)//如果右节点为空，就将左节点提升tree = tree->left;delete temp;//删掉要删除的节点}}}int main(){TreeNode *tree = NULL; //声明一个空树int arr[10] = {12, 3, 4, 6, 7, 9, 10, 5, 2, 8};for(int i=0; i<10; i++){insert(tree, arr[i]);//把数组元素插入到树当中}cout<<'先序遍历：';preOrder(tree);cout<<endl;cout<<'中序遍历：';inOrder(tree);cout<<endl;cout<<'后序遍历：';postOrder(tree);cout<<endl;cout<<'查找节点数据：4';TreeNode *findNode = find(tree, 4);if(findNode != NULL)//如果节点存在cout<<'找到了，节点的值是：'<<findNode->data;else//如果节点不存在cout<<'没有找到';cout<<endl;cout<<'查找树的最大值：'<<findMax(tree)->data<<endl; cout<<'查找树的最小值：'<<findMin(tree)->data<<endl; cout<<'删除节点：。

二叉搜索树操作算法及代码实现二叉搜索树（Binary Search Tree，简称BST）是一种常见的数据结构，它具有快速插入、删除、查找等特点。

本文将介绍二叉搜索树的相关操作算法，并提供相应的代码实现。

一、二叉搜索树简介二叉搜索树是一种有序的二叉树，它具有以下特点：1. 每个节点的值大于其左子树中的所有节点的值，小于其右子树中的所有节点的值；2. 左右子树都是二叉搜索树。

二、二叉搜索树的操作算法1. 插入操作插入操作用于将一个新节点插入到二叉搜索树中，并保持树的有序性。

具体算法如下：（1）若树为空，则将新节点作为根节点；（2）若树不为空，则从根节点开始比较新节点的值与当前节点的值的大小关系，若新节点的值小于当前节点的值，则递归地将新节点插入当前节点的左子树中；若新节点的值大于当前节点的值，则递归地将新节点插入当前节点的右子树中；（3）重复（2）直到找到一个空位置，将新节点插入该位置。

2. 删除操作删除操作用于从二叉搜索树中删除指定节点，并保持树的有序性。

具体算法如下：（1）若要删除的节点为叶子节点，则直接删除该节点；（2）若要删除的节点只有左子树或右子树，则将其子树连接到其父节点的相应位置上；（3）若要删除的节点既有左子树又有右子树，则找到该节点右子树中最小的节点（即右子树的最左叶子节点），用该最小节点的值替换要删除的节点的值，然后再删除该最小节点。

3. 查找操作查找操作用于在二叉搜索树中查找指定值的节点。

具体算法如下：（1）从根节点开始，将指定值与当前节点的值进行比较；（2）若指定值等于当前节点的值，则返回该节点；（3）若指定值小于当前节点的值，则递归地在当前节点的左子树中查找；（4）若指定值大于当前节点的值，则递归地在当前节点的右子树中查找；（5）若没有找到匹配的节点，则返回空。

三、二叉搜索树的代码实现下面是用Python语言实现二叉搜索树的代码：```pythonclass Node:def __init__(self, key):self.left = Noneself.right = Noneself.val = keydef insert(root, key):if root is None:return Node(key)else:if root.val == key:return rootelif root.val < key:root.right = insert(root.right, key)else:root.left = insert(root.left, key)return rootdef delete(root, key):if root is None:return rootif key < root.val:root.left = delete(root.left, key)elif key > root.val:root.right = delete(root.right, key)else:if root.left is None:return root.rightelif root.right is None:return root.leftroot.val = minValue(root.right)root.right = delete(root.right, root.val) return rootdef minValue(root):current = rootwhile current.left is not None:current = current.leftreturn current.valdef search(root, key):if root is None or root.val == key:return rootif root.val < key:return search(root.right, key)return search(root.left, key)```以上代码包含了二叉搜索树的插入、删除和查找三个操作的实现。

（数据结构）二叉树实验源代码#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INEEASLIBE -1#define OVERFLOW -2typedefint status;typedef char elemtype;typedefstruct tree{elemtype data;struct tree *rchild,*lchild;}tree,*bitree;typedefbitreeselemtype;typedefbitreeqelemtype;typedefstruct list{selemtype data;struct list *next;}list,*plist;typedefstruct stack{plist top;plist head;}stack;typedefstruct node{qelemtype data;struct node *next;}node,*queueptr;typedefstruct{queueptr front;queueptr rear;}linkqueue;#include"header.h"statuscreatbitree(bitree&T){elemtype e;printf("请按先序输入二叉树：\n");scanf("%c",&e);getchar();if(e=='#')T=NULL;else{T=(bitree)malloc(sizeof(tree));if(!T){exit(0);}T->data=e;creatbitree(T->lchild);creatbitree(T->rchild);}return OK;}statuspretraverse(bitree T){if(T==NULL)return OK;else{printf("\t%c",T->data);pretraverse(T->lchild);pretraverse(T->rchild);}}statuscentertraverse(bitree T){if(T==NULL)return OK;else{centertraverse(T->lchild);printf("\t%c",T->data);centertraverse(T->rchild);}}statusnexttraverse(bitree T){if(T==NULL)return OK;else{nexttraverse(T->lchild);nexttraverse(T->rchild);printf("\t%c",T->data);}}statusinitstack(stack &s){s.head=(plist)malloc(sizeof(list));if(s.top==NULL)return ERROR;s.top=s.head;s.top->next=NULL;return OK;}status push(stack &s,selemtype e) {plist p;p=(plist)malloc(sizeof(list));p->data=e;p->next=s.head->next;s.head->next=p;s.top=p;return OK;}status pop(stack &s,selemtype&e){if(s.top==s.head){printf("the stack is no elemt\n");return ERROR;}e=s.top->data;s.head->next=s.top->next;plist p;p=s.top;if(p->next==NULL)s.top=s.head;elses.top=s.head->next;free(p);return OK;}statusstackemtpy(stack s){if(s.top==s.head){return OK;}else{return ERROR;}}statusgettop(stack s,selemtype&p){if(s.head==s.top)return ERROR;elsep=s.top->data;return OK;}statuscenterstrack(bitree T){stack s;initstack(s);push(s,T);bitree c;while(!stackemtpy(s)){while(gettop(s,c)&&c){push(s,c->lchild);}pop(s,c);if(!stackemtpy(s)){pop(s,c);printf("\t%c",c->data);push(s,c->rchild);}}return OK;}statusinitqueue(linkqueue&q){q.front=q.rear=(queueptr)malloc(sizeof(node));if(!q.front)return ERROR;q.front->next=NULL;return OK;}statusenqueue(linkqueue&q,qelemtype e) {queueptr p;p=(queueptr)malloc(sizeof(node));if(!p)return ERROR;p->data=e;p->next=NULL;q.rear->next=p;q.rear=p;return OK;}statusdequeue(linkqueue&q,qelemtype&e) {if(q.front==q.rear){printf("该队列中没有数据元素\n");return ERROR;}e=q.front->next->data;queueptr p;p=q.front->next;if(p==q.rear){q.rear=q.front;q.rear->next=NULL;}elseq.front->next=p->next;free(p);return OK;}statuslayertraverse(bitree T){linkqueue queue;initqueue(queue);if(T==NULL)return ERROR;bitree c=T;enqueue(queue,c);while(1)dequeue(queue,c);printf("\t%c",c->data);if(c->lchild!=NULL)enqueue(queue,c->lchild);if(c->rchild!=NULL)enqueue(queue,c->rchild);if(queue.front==queue.rear)break;}return OK;}statusleafcout(bitree T){if(T==NULL)return 0;else if(T->lchild==NULL&&T->rchild==NULL)return 1;else{returnleafcout(T->rchild)+leafcout(T->lchild);}}statusbranchcout(bitree T){if(T==NULL||(T->rchild==NULL&&T->lchild==NULL))return 0;elsereturnbranchcout(T->rchild)+branchcout(T->lchild)+1;}statussinglebranchcout(bitree T){if(T==NULL||(T->rchild==NULL&&T->lchild==NULL))return 0;if(T->rchild!=NULL&&T->lchild!=NULL)returnsinglebranchcout(T->rchild)+singlebranchcout(T->lchild);returnsinglebranchcout(T->rchild)+singlebranchcout(T->lchild)+1;}statusdoublebranchcout(bitree T){if(T==NULL||(T->rchild==NULL&&T->lchild==NULL))return 0;if(T->rchild!=NULL&&T->lchild!=NULL)returndoublebranchcout(T->rchild)+doublebranchcout(T->lchild)+1;elsereturndoublebranchcout(T->rchild)+doublebranchcout(T->lchild);}statusnodecout(bitree T){if(T==NULL)return 0;if(T->rchild==NULL&&T->lchild==NULL)return 1;elsereturnnodecout(T->lchild)+nodecout(T->rchild)+1;}statustreedepth(bitree T){if(T==NULL)return 0;if(T->rchild==NULL&&T->lchild==NULL)return 1;elsereturn(treedepth(T->lchild)>treedepth(T->rchild)?treedepth(T->lchild):treedepth(T->rchild))+1; }void main(){bitree T;creatbitree(T);printf("先序遍历为:");pretraverse(T);printf("\n");printf("\n\n中序遍历为:");centertraverse(T);printf("\n");printf("\n\n后序序遍历为:");nexttraverse(T);printf("\n");printf("\n\n非递归中序遍历为:\n\t");centerstrack(T);printf("\n");printf("\n\n按层次遍历为:\n\t");layertraverse(T);printf("\n");printf("\n\n该树的结点数目为:%d\n\n",nodecout(T));printf("该树的叶子结点数目为:%d\n\n",leafcout(T));printf("该树的分枝数目为:%d\n\n",branchcout(T));printf("该树的单分枝数目为:%d\n\n",singlebranchcout(T));printf("该树的双分枝数目为:%d\n\n",doublebranchcout(T));printf("该树的深度为:%d\n\n",treedepth(T));}。

《数据结构》第六次实验报告学生姓名学生班级学生学号指导老师一、实验内容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

2) 输出树的深度，最大元，最小元。

二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。

递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。

直到递归全部结束。

下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。

具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。

再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。

具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。

如此循环直至结点指针和栈均为空，遍历结束。

最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。

目录实验一线性表基本操作的编程实现 (201)实验二堆栈或队列基本操作的编程实现 (49)实验四二维数组基本操作的编程实现 (18)实验五二叉树基操作的编程实现 (20)实验六图基本操作的编程实现 (45)（特别提示：程序设计包含两个方面的错误。

其一是错误，其二是能错误。

为了提高学生的编程和能力，本指导书给出的程序代码并的两种错误。

并且也不保证程序的完整性，有一些语句已经故意删除，就是要求学生自己编制完成，这样才能达到我们的要求。

希望大家以自己所学高级语言的基本功和点为基础，不要过于依赖给出的参考代码，这样才能有所进步。

如果学生能够根据要求完全自己编制，那就不好了。

）实验一线性表基本操作的编程实现【实验目的】线性表基本操作的编程实现要求：线性表基本操作的编程实现（2学时，验证型），掌握线性表的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找、逆序、排序等操作，存储结构可以在顺序结构或链表结分主要功能，也可以用菜单进行管理完成大部分功能。

还鼓励学生利用基本操作进行一些更实际的应用型程序设计。

【实验性质】【实验内容】把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。

建议实现键盘输入数据以实现程序的通据的函数。

【注意事项】【思考问题】1.线性表的顺序存储和链表存储的差异？优缺点分析？2.那些操作引发了数据的移动？3.算法的时间效率是如何体现的？4.链表的指针是如何后移的？如何加强程序的健壮性？【参考代码】（一）利用顺序表完成一个班级学生课程成绩的简单管理1、预定义以及顺序表结构类型的定义(1)#define ListSize //根据需要自己设定一个班级能够容纳的最大学生数(2)typedef struct Stu{int num; //学生的学号char name[10]; //学生的姓名float wuli; //物理成绩float shuxue; //数学成绩float yingyu; //英语成绩}STUDENT; //存放单个学生信息的结构体类型typedef struct List{stu[ListSize]; //存放学生的数组定义，静态分配空间int length; //记录班级实际学生个数}LIST; //存放班级学生信息的顺序表类型2、建立班级的学生信息void listcreate(LIST *Li,int m) //m为该班级的实际人数{int i;Li->length=0;for(i=0;i<m;i++) //输入m个学生的所有信息{printf("please input the %dth student's information:\n",i+1);printf("num=");scanf("%d", ); //输入第i个学生的学号printf("name=");scanf("%s", ); //输入第i个学生的姓名printf("wuli=");scanf("%f", ); //输入第i个学生的物理成绩printf("shuxue=");scanf("%f", ); //输入第i个学生的数学成绩printf("yingyu=");scanf("%f", ); //输入第i个学生的英语成绩Li->length++; //学生人数加1}}3、插入一个学生信息int listinsert(LIST *Li,int i) //将学生插入到班级Li的第i个位置。

二叉树的基本操作实验代码二叉树的基本操作实验代码介绍二叉树是一种非常常见的数据结构，它具有以下特点：1. 每个节点最多有两个子节点；2. 左子节点比父节点小，右子节点比父节点大；3. 左右子树也是二叉树。

在本篇文章中，我们将介绍二叉树的基本操作，并提供相应的实验代码。

创建二叉树创建一个二叉树需要两个步骤：首先创建一个空的根节点，然后逐个添加子节点。

下面是创建一个简单的二叉树的示例代码：```c++#include <iostream>using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {} };TreeNode* createTree() {TreeNode* root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);return root;}int main() {TreeNode* root = createTree();}```遍历二叉树遍历二叉树有三种方式：前序遍历、中序遍历和后序遍历。

下面是三种遍历方式的示例代码：前序遍历：```c++void preorderTraversal(TreeNode* root) {if (!root) return;cout << root->val << " ";preorderTraversal(root->left);preorderTraversal(root->right);}```中序遍历：```c++void inorderTraversal(TreeNode* root) {if (!root) return;inorderTraversal(root->left);cout << root->val << " ";inorderTraversal(root->right);}```后序遍历：```c++void postorderTraversal(TreeNode* root) {if (!root) return;postorderTraversal(root->left);postorderTraversal(root->right);cout << root->val << " ";}```查找二叉树查找二叉树需要递归地遍历每个节点，直到找到目标节点。