赞
踩
- //交换左右子树
-
- #include<iostream>
- #include<cstring>
- using namespace std;
- typedef struct BiTNode
- {
- char data;
- struct BiTNode *lchild,*rchild;
- }BiTNode,*BiTree;
- void CreateBiTree(BiTree &T,char S[],int &i)
- {//先序建立二叉树
- if(S[i]=='0')
- T=NULL;
- else
- {
- T=new BiTNode;
- T->data=S[i];
- CreateBiTree(T->lchild,S,++i);
- CreateBiTree(T->rchild,S,++i);
- }
- }
- void ChangeRL(BiTree &T)
- {//二叉树左右孩子的交换
- /**************begin************/
- if (T == 0) {
- return;
- }
- BiTNode *temp;
- temp=T->lchild;
- T->lchild=T->rchild;
- T->rchild=temp;
- ChangeRL(T->lchild);
- ChangeRL(T->rchild);
-
- /**************end************/
- }
- void PreOrderTraverse(BiTree T)
- {//先序遍历
- if(T)
- {
- cout<<T->data;
- PreOrderTraverse(T->lchild);
- PreOrderTraverse(T->rchild);
- }
- }
- int main()
- {
- char S[100];
- while(cin>>S)
- {
- if(strcmp(S,"0")==0) break;
- int i=-1;
- BiTree T;
- CreateBiTree(T,S,++i);
- ChangeRL(T);
- PreOrderTraverse(T);
- cout<<endl;
- }
- return 0;
- }

- #include<iostream>
- #include <string.h>
- using namespace std;
- typedef struct BiTNode
- {
- char data;
- struct BiTNode *lchild,*rchild;
- }BiTNode,*BiTree;
- void CreateBiTree(BiTree &T,char S[],int &i)
- {//先序建立二叉树
- if(S[i]=='0')
- T=NULL;
- else
- {
- T=new BiTNode;
- T->data=S[i];
- CreateBiTree(T->lchild,S,++i);
- CreateBiTree(T->rchild,S,++i);
- }
- }
- void DoubleTraverse(BiTree T)
- {//双序遍历二叉树T的递归算法
- /**************begin************/
- if (T==0) {
- return;
- }
-
- cout<<T->data;
- DoubleTraverse(T->lchild);
- cout<<T->data;
- DoubleTraverse(T->rchild);
- /**************end************/
- }
- int main()
- {
- char S[100];
- while(cin>>S)
- {
- if(strcmp(S,"0")==0) break;
- int i=-1;
- BiTree T;
- CreateBiTree(T,S,++i);
- DoubleTraverse(T);
- cout<<endl;
- }
- return 0;
- }

- #include <iostream>
- #include <string.h>
- #include <queue>
- #include <stdlib.h>
- using namespace std;
-
- typedef struct BiTNode
- {
- char data;
- struct BiTNode *lchild,*rchild;
- }BiTNode,*BiTree;
-
- BiTree CreateBiTree(int &pos, char *str)
- {// 先序建立二叉树
- char c=str[pos++];
- if(c=='0') return NULL;
- BiTree root=new BiTNode();
- root->data=c;
- root->lchild=CreateBiTree(pos,str);
- root->rchild=CreateBiTree(pos,str);
- return root;
- }
-
- int Width(BiTree T)
- {// 求二叉树T最大宽度
- /**************begin************/
- int max=0;
- queue <BiTree> q;
- if (T==0) {
- return 0;
- }
- if (T !=NULL)
- {
- q.push(T); //根节点进队列
- }
-
- while (q.empty() == false) //队列不为空判断
- {
- int size = q.size();
- while(size--)//遍历当前层的元素
- {
- BiTNode* temp=q.front();
- q.pop();
- if(temp->lchild) q.push(temp->lchild);
- if(temp->rchild) q.push(temp->rchild);
- }
- if(max<q.size())max=q.size();
- }
- return max;
- /**************end************/
- }
-
- int main()
- {
- char str[1000];
- while(cin>>str)
- {
- if(strcmp(str,"0")==0) break;
- int pos=0; // 标记字符串处理位置
- BiTree root=CreateBiTree(pos,str);
- cout<<Width(root)<<endl;
- }
- return 0;
- }

- #include<iostream>
- #include<vector>
- #include<queue>
- #define MAXSIZE 100
- using namespace std;
- typedef struct BiTNode
- {
- char data;
- struct BiTNode *lchild,*rchild;
- }BiTNode,*BiTree;
- void CreateBiTree(BiTree &T,char S[],int &i)
- {//程序生成器
- if(S[i]=='0')
- T=NULL;
- else
- {
- T=new BiTNode;
- T->data=S[i];
- CreateBiTree(T->lchild,S,++i);
- CreateBiTree(T->rchild,S,++i);
- }
- }
- void LongestPath(BiTree T)
- {
- if (T == nullptr)
- {
- cout << "The tree is empty." << endl;
- return;
- }
-
- vector<char> currentPath;
- vector<char> longestPath;
-
- queue<pair<BiTree, vector<char>>> q;
- q.push({T, {T->data}});
-
- while (!q.empty())
- {
- auto current = q.front();
- q.pop();
-
- BiTree node = current.first;
- vector<char> currentPath = current.second;
-
- if (node->lchild == nullptr && node->rchild == nullptr)
- {
- if (currentPath.size() > longestPath.size())
- {
- longestPath = currentPath;
- }
- }
-
- if (node->lchild != nullptr)
- {
- vector<char> newPath = currentPath;
- newPath.push_back(node->lchild->data);
- q.push({node->lchild, newPath});
- }
-
- if (node->rchild != nullptr)
- {
- vector<char> newPath = currentPath;
- newPath.push_back(node->rchild->data);
- q.push({node->rchild, newPath});
- }
- }
- cout << longestPath.size() << endl;
- for (char node : longestPath)
- {
- cout << node;
- }
- cout << endl;
-
- }
- int main()
- {
- char S[100];
- while(cin>>S&&S[0]!='0')
- {
- int i=-1;
- BiTree T;
- CreateBiTree(T,S,++i);
- LongestPath(T);
- }
- return 0;
- }

- #include<iostream>
- using namespace std;
- char path[100]; //路径数组,存储路径上每个结点的值
- typedef struct BiTNode
- {
- char data;
- struct BiTNode *lchild,*rchild;
- }BiTNode,*BiTree;
- void CreateBiTree(BiTree &T,char S[],int &i)
- {//先序建立二叉树
- if(S[i]=='0')
- T=NULL;
- else
- {
- T=new BiTNode;
- T->data=S[i];
- CreateBiTree(T->lchild,S,++i);
- CreateBiTree(T->rchild,S,++i);
- }
- }
- void AllPath(BiTree T,char path[],int pathlen)
- {//二叉树叶子结点到根结点的路径的求解
- /**************begin************/
- if (T==0) {
- return;
- }
- path [pathlen]=T->data;
- pathlen++;
- if (T->lchild==0&&T->rchild==0) {
- //叶子结点
- for(int i=0;i<pathlen;i++){
- cout<<path[pathlen-i-1];
- }
- cout<<endl;
- }
- else{
- AllPath(T->lchild,path,pathlen);
- AllPath(T->rchild,path,pathlen);
- }
-
- /**************end************/
- }
- int main()
- {
- char S[100];
- while(cin>>S&&S[0]!='0')
- {
- int i=-1;
- BiTree T;
- CreateBiTree(T,S,++i);
- int pathlen=0; //初始化路径到根结点的长度为0
- AllPath(T,path,pathlen);
- }
- return 0;
- }

- #include<iostream>
- #define MAXSIZE 100
- using namespace std;
- typedef struct BiTNode
- {//二叉树的双链表存储表示
- double data; //结点数据域
- bool ischaracter; //判断结点是否为字符
- struct BiTNode *lchild,*rchild; //左右孩子指针
- }BiTNode,*BiTree;
- typedef struct
- {//字符栈的存储结构
- char *base; //栈底指针
- char *top; //栈顶指针
- int stacksize; //栈可用的最大容量
- }SqStack1;
- typedef struct
- {//结点栈的存储结构
- BiTree *base;
- BiTree *top;
- int stacksize;
- }SqStack2;
- void InitStack1(SqStack1 &s)
- {//字符栈的初始化
- s.base=new char[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
- s.top=s.base; //初始为空栈
- s.stacksize=MAXSIZE; //置栈的最大容量为MAXSIZE
- }
- void InitStack2(SqStack2 &s)
- {//结点栈的初始化
- s.base=new BiTree[MAXSIZE];
- s.top=s.base;
- s.stacksize=MAXSIZE;
- }
- void Push1(SqStack1 &s,char ch)
- {//字符入栈操作
- if(s.top-s.base==s.stacksize) //栈满
- return;
- *s.top=ch; //元素ch压入栈顶
- s.top++; //栈顶指针加1
- }
- void Push2(SqStack2 &s,BiTree t)
- {//结点入栈操作
- if(s.top-s.base==s.stacksize)
- return;
- *s.top=t;
- s.top++;
- }
- void Pop1(SqStack1 &s,char &ch)
- {//字符出栈操作
- if(s.top==s.base) //栈空
- return;
- else
- {
- s.top--; //栈顶指针减1
- ch=*s.top; //将栈顶元素赋给ch
- }
- }
- void Pop2(SqStack2 &s,BiTree &t)
- {//结点出栈操作
- if(s.top==s.base)
- return;
- else
- {
- s.top--;
- t=*s.top;
- }
- }
- char GetTop(SqStack1 s)
- {//取字符栈的栈顶元素
- if(s.base==s.top) //栈空
- return -1;
- else
- return *(s.top-1); //返回栈顶元素的值,栈顶指针不变
- }
- bool EmptyStack(SqStack1 s)
- {//栈的判空操作
- if(s.base==s.top) //栈空返回true
- return true;
- else
- return false; //栈非空返回false
- }
- char Precede(char a,char b)
- {//判断符号的优先级
- if(a=='+'||a=='-')
- {
- if(b=='+'||b=='-'||b==')'||b=='=')
- return '>'; //>代表a的优先级高于b
- else
- return '<';
- }
- else if(a=='*'||a=='/')
- {
- if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='=')
- return '>';
- else
- return '<';
- }
- else if(a=='(')
- {
- if(b==')')
- return '=';
- else
- return '<';
- }
- else if(a==')')
- return '>';
- else
- {
- if(b=='=')
- return '=';
- else
- return '<';
- }
- }
- double Operate(double a,char ch,double b)
- {//运算操作,返回相应的数值结果
- if(ch=='+')
- return a+b;
- else if(ch=='-')
- return a-b;
- else if(ch=='*')
- return a*b;
- else
- return a/b;
- }
- bool IsCharacter(char ch)
- {//判断ch是否为+、-、*、/、(、)、= 这类的字符,是则返回true
- if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='=')
- return true;
- else
- return false;
- }
- double InOrder(BiTree T) {
- if (T != nullptr) {
- if (T->ischaracter) {
- double ans1 = InOrder(T->lchild);
- double ans2 = InOrder(T->rchild);
- return Operate(ans1, T->data, ans2);
- } else {
- return T->data;
- }
- }
- return 0.0;
- }
-
- void CreateBT(char ch[],BiTree &t,SqStack1 optr,SqStack2 expt)
- {//创建二叉树
-
- int i=0;
- char opr,c[2]; //辅助数组c
- BiTree t1,t2;
- double num;
- while(ch[i]!='\0'||!EmptyStack(optr))
- {
- if(!IsCharacter(ch[i])) //当前遍历的不是运算符元素
- {
- c[0]=ch[i];
- c[1]='\0';
- BiTree q=new BiTNode; //生成一个新结点*q
- num=strtod(c,NULL); //将字符数组c转换成浮点数,赋给num
- q->ischaracter=false; //结点*q不为运算符
- q->data=num; //结点数据域置为num
- q->lchild=NULL; //左右孩子置为NULL
- q->rchild=NULL;
- Push2(expt,q); //将结点q压入数字栈
- i++; //指针i加1
- }//if
- else //当前遍历的是运算符元素
- {
- switch(Precede(GetTop(optr),ch[i])) //比较栈顶元素和当前遍历字符的优先级
- {
- case '<': //栈顶元素优先级小于当前运算符
- Push1(optr,ch[i]); //将当前运算符入栈
- i++; //指针i加1
- break;
- case '>': //栈顶元素优先级大于当前运算符
- Pop1(optr,opr); //运算符栈的元素出栈
- Pop2(expt,t2); //数字栈的栈顶元素出栈
- Pop2(expt,t1);
- t=new BiTNode; //生成新结点*t
- t->ischaracter=true; //结点*t为运算符
- t->data=opr; //结点数据域置为opr
- t->lchild=t1; //左孩子指向t1
- t->rchild=t2; //右孩子指向t2
- Push2(expt,t); //将结点t压入数字栈
- break;
- case '=': //栈顶元素优先级等于当前运算符
- Pop1(optr,opr); //运算符栈的元素出栈
- i++; //指针i加1
- break;
- }//switch
- }//else
- }//while
- }
- int main()
- {
- char ch[MAXSIZE];
- while(cin>>ch)
- {
- if(ch[0]=='=') break;
- BiTree t;
- SqStack1 optr; //运算符栈optr
- SqStack2 expt; //数字栈expt
- InitStack1(optr); //初始化栈
- InitStack2(expt); //初始化栈
- Push1(optr,'='); //先在运算符栈底放入一个'='
- CreateBT(ch,t,optr,expt); //创建二叉树
- double answer=InOrder(t);
- cout<<answer<<endl;
- }
- return 0;
- }

- #include<iostream>
- using namespace std;
- typedef struct BiTNode
- {
- int weight;
- struct BiTNode *left,*right;
- }BiTNode,*BiTree;
- void CreateBiTree(BiTree &T)
- {//先序建立二叉树
- int x;
- cin>>x;
- if(x==0) T=NULL;
- else
- {
- T=new BiTNode;
- T->weight=x;
- CreateBiTree(T->left);
- CreateBiTree(T->right);
- }
- }
- int WPL(BiTree T, int d) {
- if (T == nullptr) {
- return 0;
- } else if (T->left == 0 && T->right ==0) {
- return T->weight * d;
- } else {
- int wplLeft = WPL(T->left, d + 1);
- int wplRight = WPL(T->right, d + 1);
- return wplLeft + wplRight;
- }
- }
- int main()
- {
- while(1)
- {
- BiTree T;
- CreateBiTree(T);
- if(!T) break;
- int d=0; //调用时T指向二叉树的根结点,d为0
- cout<<WPL(T,d)<<endl;
- }
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。