当前位置：文档之家 › 表达式二叉树·实验代码

表达式二叉树·实验代码

  • 格式：doc
  • 大小：69.50 KB
  • 文档页数：6

实验：表达式二叉树实验要求：建立表达式二叉树，并打印（可逆时针旋转90度打印，也可尝试正向打印）以中缀表达式a*b+(c-d)/e-f 为例，建立以"-"号为根的表达式二叉树。

提示：若直接利用中缀表达式建立困难，可先将中缀表达式转化为后缀表达式（可利用栈中的中缀到后缀转化程序实现中缀表达式到后缀表达式的转换，再根据后缀表达式建立表达式二叉树，可参考栈中后缀表达式计算方法）。

实验代码：#include <iostream>#include <stack>#include <string>#include <queue>#include <vector>using namespace std;class tnode;void buildexptree(const string &exp);void printexptree();int judgerank(char ch);bool isoperator(char ch);void test();void setxy(tnode *tn, int y);int X = 0;int Y = 0;int depth = 0;vector<tnode*>vt;class tnode{public:char nodeValue;int x, y;tnode *left;tnode *right;tnode(){x = 0;y = 0;}tnode(char &item, tnode *lptr = NULL, tnode *rptr = NULL):nodeV alue(item), left(lptr), right(rptr){x = 0;y = 0;}};tnode *myNode;bool cmp(tnode *t1, tnode *t2){if(t1->y != t2->y)return (t1->y) > (t2->y);return (t1->x) < (t2->x);}class zpair{ //将operator和rank打包为一体,临时存储在stk2中public:char op;int rank;zpair(){}zpair(char _op, int _rank){op = _op;rank = _rank;}};int judgerank(char ch){if(ch == '(') return -1;if(ch == '+' || ch == '-') return 1;if(ch == '*' || ch == '/') return 2;return 0;}bool isoperator(char ch){if(ch == '(' || ch == ')' || ch == '+' || ch == '-' || ch == '*' || ch == '/') return true;elsereturn false;}void buildexptree(const string &exp){stack<tnode*>stk1;stack<zpair>stk2;int i;int len = exp.length();char ch;zpair tz;zpair ztop;for(i=0; i<len; i++){ch = exp[i];if(!isoperator(ch)){ //exp[i] is an operand, so create a tnode using exp[i] and push to stk1tnode *ptr1 = new tnode(ch);stk1.push(ptr1);}else {tz.op = ch;tz.rank = judgerank(ch);if(stk2.empty())stk2.push(tz);else if(ch == '(')stk2.push(tz);else if(ch == ')'){ztop = stk2.top();while(ztop.op != '('){tnode *ptr2 = stk1.top();stk1.pop();tnode *ptr3 = stk1.top();stk1.pop();tnode *ptr4 = new tnode(ztop.op, ptr3, ptr2);stk1.push(ptr4);stk2.pop();ztop = stk2.top();}stk2.pop();}else{ztop = stk2.top();while(tz.rank <= ztop.rank){tnode *ptr5 = stk1.top();stk1.pop();tnode *ptr6 = stk1.top();stk1.pop();tnode *ptr7 = new tnode(ztop.op, ptr6, ptr5);stk1.push(ptr7);stk2.pop();if(stk2.empty()) break;else ztop = stk2.top();}stk2.push(tz);}}}while(!stk2.empty()){tnode *ptr8 = stk1.top();stk1.pop();tnode *ptr9 = stk1.top();stk1.pop();tnode *ptr10 = new tnode(stk2.top().op, ptr9, ptr8);stk1.push(ptr10);stk2.pop();}myNode = stk1.top();}int main(){freopen("chris.txt","r",stdin);string exp;cout << "Please input an expression:" << endl;cin >> exp;buildexptree(exp);cout << "The expression tree is: " << endl;printexptree();return 0;}void test(){ //测试函数cout << "testing..." << endl;}void printexptree(){setxy(myNode, Y);sort(vt.begin(),vt.end(),cmp);int tmpY = 1;int tmpX = 0;for(int i=0; i<vt.size(); i++){if(vt[i]->y < tmpY){cout << endl;tmpX = 0;tmpY--;}cout << string(vt[i]->x - tmpX - 1 , ' ') << vt[i]->nodeValue;tmpX = vt[i]->x;}cout << endl;}void setxy(tnode *tn, int y){ //设定每一个节点的横坐标if(tn == NULL) return;setxy(tn->left, y-1);tn->x = ++X;tn->y = y;vt.push_back(tn);/* cout << "tn->nodeValue=" << tn->nodeValue << " " << "tn->x=" << tn->x << " " << "tn->y=" << tn->y << endl;*/setxy(tn->right,y-1);depth++;}实验截图：实验分析:通过类tnode构造了一个表达式二叉树，除了节点值nodeValue，左分支left 和右分支right，还引入了x，y作为标定的坐标，打印时使用。

首先完成infix2postfix，这其中使用了stk1，stk2两个栈分别存储子树和zpair量，zpair是将operator与其优先级打包的一个整体，然后通过比较优先级，调整stk1中的元素，构造了后缀表达式。

打印过程中，先调用setxy（）方法来设定每个节点的坐标值，使用的是中序遍历，同时声明了存储各个节点的向量vt，将所有节点压入vt后先按y再按x排序，然后按格式输出表达式二叉树。

合集下载

二叉查找树实现代码及运行结果

二叉查找树实现代码及运行结果

scanf(" %d",&keyword); //输入要查找元素的关键字
temp=SearchBST(T,keyword,NULL,p);//查找
if(!temp) printf("%d isn't existed!\n",keyword); //没有找到
else printf("%d has been found!\n",keyword); //成功找到
}
else return 0; //树中已存在关键字为e的数据元素
}
int DeleteBST(BiTree &T,int key)
{//若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点
//并返回1,否则返回0
int tmp1,tmp2;
tmp1=tmp2=0;
if(!T) return 0; //不存在关键字等于key的数据元素
//则指针p指向该数据元素，并返回1,否则指针指向查找路径上访问的最后一
//个结点并返回0,指针f指向T的双亲，其初始调用值为NULL
int tmp1,tmp2;
tmp1=tmp2=0;
if(!T) {p=f;return 0;} //查找不成功
else if(key==T->data) {p=T;return 1;} //查找成功
scanf("%d",&n);
printf("Please input every node:\n");
for(int i=0;i<n;i++)//输入树的结点个数
scanf("%d",&A[i]);
二叉树实现源代码

二叉树实现源代码

二叉树实现源代码如下：#include <conio.h>#include <stdio.h>#include <stdlib.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -2typedef int status;typedef struct BiNode{char Data;struct BiNode* lChild;struct BiNode* rChild;}BiNode,*pBiNode;status CreateTree(BiNode** pTree);status PreOrderTraval(BiNode* pTree);status Visit(char Data);status Display(BiNode* pTree,int Level);status Clear(BiNode* pTree);BiNode *pRoot=NULL;main(){clrscr();CreateTree(&pRoot);printf("\nPreOrder:");PreOrderTraval(pRoot);printf("\n");printf("\nInOrder:");InOrderTraval(pRoot);printf("\n");printf("\nPostOrder:");PostOrderTraval(pRoot);printf("\n");printf("\nShowLeaves:");ShowLeaves(pRoot);printf("\n-----------------------\n");printf("\n");Display(pRoot,0);printf("\n");printf("\nDeleting Tree:\n");DelTree(pRoot);printf("BiTree Deleted.");getch();}status CreateTree(BiNode** pTree) /*Input Example: abd##e##cf##g##*/ {char ch;scanf("%c",&ch);if(ch==‘#‘){(*pTree)=NULL;}else{if(!((*pTree)=(BiNode*)malloc(sizeof(BiNode)))) {exit(OVERFLOW);}(*pTree)->Data=ch;CreateTree(&((*pTree)->lChild));CreateTree(&((*pTree)->rChild));}return OK;}status PreOrderTraval(BiNode* pTree){if(pTree){if(Visit(pTree->Data)){if(PreOrderTraval(pTree->lChild)){if(PreOrderTraval(pTree->rChild)){return OK;}}}return ERROR;}else{return OK;}}status InOrderTraval(BiNode* pTree){if(pTree){if(InOrderTraval(pTree->lChild)){if(Visit(pTree->Data)){if(InOrderTraval(pTree->rChild)){return OK;}}return ERROR;}return ERROR;}else{return OK;}}status PostOrderTraval(BiNode* pTree){if(pTree){if(PostOrderTraval(pTree->lChild)){if(PostOrderTraval(pTree->rChild)){if(Visit(pTree->Data)){return OK;}return ERROR;}}return ERROR;}else{return OK;}}status Visit(char Data){printf("%c",Data);return OK;}status Display(BiNode* pTree,int Level){int i;if(pTree==NULL) return;Display(pTree->lChild,Level+1);for(i=0;i<Level-1;i++){printf(" ");}if(Level>=1){printf("--");}printf("%c\n",pTree->Data);Display(pTree->rChild,Level+1);}status ShowLeaves(BiNode* pTree){if(pTree){if(ShowLeaves(pTree->lChild)){if(ShowLeaves(pTree->rChild)){if((pTree->lChild==NULL)&&(pTree->rChild==NULL)) {if(!Visit(pTree->Data)){return ERROR;}}return OK;}}return ERROR;}else{return OK;}}status DelTree(BiNode* pTree){if(pTree){if(DelTree(pTree->lChild)){if(DelTree(pTree->rChild)){printf("Deleting %c\n",pTree->Data); free((void*)pTree);return OK;}}return ERROR;}else{return OK;}}。

数据结构实验二叉树C完整代码

数据结构实验二叉树C完整代码

#include<iostream>using namespace std;const int MAXSIZE = 100 ;template <class T > struct BiNode //二叉链表结点{T data;//数据域BiNode<T>* lch;//左指针域BiNode<T>* rch;//右指针域};template <class T> class BiTree //二叉树的实现{public:void Create (BiNode<T> * &R,T data[] ,int i);//创建二叉树void Release(BiNode<T> *R); //释放二叉树BiNode<T> *root; //根节点BiTree(T a[]){Create(root,a,1);};//构造函数BiNode<T> * Getroot(){return root;};//根节点地址返回void PrintWay(T data, T a[]);void PreOrder(BiNode<T> *R); //前序遍历void InOrder(BiNode<T> *R); //中序遍历void LevelOrder(BiNode<T> *R);//层序遍历void PostOrder(BiNode<T> *R); //后序遍历~BiTree();//析构函数int GetDepth(BiNode<T> *R,int d);//求二叉树深度void GetPath(T x,BiNode<T>*R);//求指定结点到根结点的路径};template <class T> void BiTree <T>::Create (BiNode<T> * &R,T data[] ,int i)//顺序结构存储二叉链表{//i表示位置，从1开始if(data[i-1]!=0){R=new BiNode<T>;//创建根节点R->data=data[i-1];Create(R->lch,data,2*i);//创建左子树Create(R->rch,data,2*i+1);//创建右子树}elseR=NULL;}template <class T> void BiTree <T>::PreOrder(BiNode<T> *R)//前序遍历的实现{if(R!=NULL){cout<<R->data;//访问结点PreOrder(R->lch);//遍历左子树PreOrder(R->rch);//遍历右子树}}template <class T> void BiTree <T>::InOrder(BiNode<T> *R)//中序遍历的实现{if(R!=NULL){PreOrder(R->lch);//遍历左子树cout<<R->data;//访问结点PreOrder(R->rch);//遍历右子树}}template <class T> void BiTree <T>::PostOrder(BiNode<T> *R)//后序遍历的实现{if(R!=NULL){PreOrder(R->lch);//遍历左子树PreOrder(R->rch);//遍历右子树cout<<R->data;//访问结点}}template <class T> void BiTree <T>::LevelOrder(BiNode<T> *R)//层序遍历的实现{BiNode<T> * queue[MAXSIZE];//利用队列实现层序遍历int f = 0,r = 0;//初始化空队列if(R!=NULL)queue[++r] = R;while(f!=r){BiNode<T> *p=queue[++f];//队头元素出列cout<<p->data;if(p->lch!=NULL)queue[++r]=p->lch;if(p->rch!=NULL)queue[++r]=p->rch;}}template <class T> void BiTree<T>::Release(BiNode<T> *R)//释放二叉树{if (R!=NULL){Release(R->lch);Release(R->rch);delete R;}}template <class T> BiTree<T>::~BiTree() //调用Release函数{Release(root);}template <class T> int BiTree<T>::GetDepth(BiNode<T> *R,int d) //求二叉树的深度{if (R==NULL) return d;if ((R->lch==NULL) && (R->rch==NULL))return d+1;else{int m = GetDepth(R->lch,d+1);int n = GetDepth(R->rch,d+1);return n>m? n:m;}}template<class T> void BiTree<T>::PrintWay(T data, T a[])//打印路径{int x;for(int i=1;i<100;i++){if(a[i-1]==data)//数组中各元素和指定元素比较、查找所在位置i{x=i;break;}}cout<<"该结点到根结点的路径为:"<<endl;while(x!=0){cout<<a[x-1]<<endl;x/=2;//子节点对应父节点编号}}void main(){char buf[MAXSIZE]={'j','u','s','t','l','o','v','e','u','f','o','r','e','v','e','r'};BiTree <char> Test(buf);BiNode<char> * A = Test.Getroot();cout<<"前序遍历：";Test.PreOrder(A);cout<<endl;cout<<"中序遍历：";Test.InOrder(A);cout<<endl;cout<<"后续遍历：";Test.PostOrder(A);cout<<endl;cout<<"层序遍历：";Test.LevelOrder(A);cout<<endl;int depth=0;cout<<"深度为";cout<<Test.GetDepth(A,depth)<<endl;cout<<endl;Test.PrintWay('f',buf);}。

c语言二叉树代码

c语言二叉树代码

c语言二叉树代码以下是一个简单的C语言二叉树代码，包括二叉树的创建、插入、遍历、删除等操作：```#include<stdio.h>#include<stdlib.h>//定义二叉树节点类型typedef struct node{int data;struct node *left;struct node *right;}Node;//创建二叉树Node* create_tree(){int value;printf('请输入节点的值（-1表示结束）：');scanf('%d', &value);if(value == -1){return NULL;}else{Node *p = (Node*)malloc(sizeof(Node));p->data = value;printf('请输入%d的左子节点：', value);p->left = create_tree();printf('请输入%d的右子节点：', value);p->right = create_tree();return p;}}//插入节点Node* insert_node(Node *root, int value){if(root == NULL){Node *p = (Node*)malloc(sizeof(Node));p->data = value;p->left = NULL;p->right = NULL;return p;}else if(value < root->data){root->left = insert_node(root->left, value);}else if(value > root->data){root->right = insert_node(root->right, value); }return root;}//先序遍历void preorder_traversal(Node *root){if(root != NULL){printf('%d ', root->data);preorder_traversal(root->left);preorder_traversal(root->right);}}//中序遍历void inorder_traversal(Node *root){if(root != NULL){inorder_traversal(root->left);printf('%d ', root->data);inorder_traversal(root->right);}}//后序遍历void postorder_traversal(Node *root){if(root != NULL){postorder_traversal(root->left);postorder_traversal(root->right);printf('%d ', root->data);}}//查找节点Node* search_node(Node *root, int value){ if(root == NULL){return NULL;}else if(root->data == value){return root;}else if(value < root->data){return search_node(root->left, value);}else{return search_node(root->right, value); }}//删除节点Node* delete_node(Node *root, int value){if(root == NULL){return NULL;}else if(value < root->data){root->left = delete_node(root->left, value); }else if(value > root->data){root->right = delete_node(root->right, value); }else{//情况一：被删除节点没有子节点if(root->left == NULL && root->right == NULL){ free(root);root = NULL;}//情况二：被删除节点只有一个子节点else if(root->left == NULL){Node *temp = root;root = root->right;free(temp);}else if(root->right == NULL){Node *temp = root;root = root->left;free(temp);}//情况三：被删除节点有两个子节点else{Node *temp = root->right;while(temp->left != NULL){temp = temp->left;}root->data = temp->data;root->right = delete_node(root->right, temp->data); }}return root;}//主函数int main(){Node *root = NULL;int choice, value;while(1){printf('请选择操作： ');printf('1.创建二叉树 ');printf('2.插入节点');printf('3.遍历二叉树 ');printf('4.查找节点');printf('5.删除节点');printf('6.退出程序');scanf('%d', &choice); switch(choice){case 1:root = create_tree(); break;case 2:printf('请输入要插入的节点值：');scanf('%d', &value);root = insert_node(root, value);break;case 3:printf('先序遍历：');preorder_traversal(root);printf('中序遍历：');inorder_traversal(root);printf('后序遍历：');postorder_traversal(root);printf('');break;case 4:printf('请输入要查找的节点值：');scanf('%d', &value);Node *result = search_node(root, value);if(result != NULL){printf('找到节点：%d', result->data);}else{printf('未找到节点：%d', value);}break;case 5:printf('请输入要删除的节点值：');scanf('%d', &value);root = delete_node(root, value); break;case 6:printf('程序已退出。