(12条消息) 食用前须知(阅读并同意后在食用其他部分)_lxrrrrrrrr的博客-CSDN博客
目录
问题 L: 静态链表存储的二叉树的非递归遍历算法-附加代码模式
- #include
- using namespace std;
-
- struct BiNode
- {
- string data;
- BiNode *lchild, *rchild;
- };
- typedef BiNode *BiTree;
- int InitBiTree(BiTree &T)
- {
- T = NULL;
- return 0;
- }
- string PreTraverse_nonRec(BiTree T)
- {
- stack
q; - string result = "";
- BiTree temp;
- if (T!=NULL) q.push(T);
- while(!q.empty())
- {
- temp=q.top();
- q.pop();
- result=result+temp->data;
- if(temp->rchild!=NULL) q.push(temp->rchild);
- if(temp->lchild!=NULL) q.push(temp->lchild);
- }
- return result;
- }
- char *CreateBiTree(BiTree &T, char *str)
- {
- if (*str == '#')
- {
- T = NULL;
- return str + 1;
- }
- T = new BiNode;
- T->data = *str;
-
- // 继续输入并构造左子树和右子树
- char * strAfterLeft = CreateBiTree(T->lchild, str + 1);
- char * strAfterRight = CreateBiTree(T->rchild, strAfterLeft);
- return strAfterRight;
- }
-
- int PreTraverse(BiTree T){
- if (T == NULL) return 0;
- cout << T->data;
- PreTraverse(T->lchild);
- PreTraverse(T->rchild);
- return 0;
- }
-
- int DestroyBiTree(BiTree &T){
- if (T == NULL) return 0;
- DestroyBiTree(T->lchild);
- DestroyBiTree(T->rchild);
- delete T;
- T = NULL;
- return 0;
- }
- #include
- using namespace std;
- struct BiNode
- {
- string data;
- BiNode* lchild, * rchild;
- };
- typedef BiNode* BiTree;
- int InitBiTree(BiTree& T)
- {
- T = NULL;
- return 0;
- }
- string InTraverse_nonRec(BiTree T)
- {
- string result = "";
- stack
s; - BiTree p = T;
- while (p != NULL || !s.empty())
- {
- while (p != NULL)
- {
- s.push(p);
- p = p->lchild;
- }
- if (!s.empty())
- {
- p = s.top();
- result += p->data;
- s.pop();
- p = p->rchild;
- }
- }
- return result;
- }
- char* CreateBiTree(BiTree& T, char* str)
- {
- if (*str == '#')
- {
- T = NULL;
- return str + 1;
- }
- T = new BiNode;
- T->data = *str;
- char* strAfterLeft = CreateBiTree(T->lchild, str + 1);
- char* strAfterRight = CreateBiTree(T->rchild, strAfterLeft);
-
- return strAfterRight;
- }
-
- int InTraverse(BiTree T) {
- if (T == NULL) return 0;
- InTraverse(T->lchild);
- cout << T->data;
- InTraverse(T->rchild);
- return 0;
- }
-
- int DestroyBiTree(BiTree& T) {
- if (T == NULL) return 0;
- DestroyBiTree(T->lchild);
- DestroyBiTree(T->rchild);
- delete T;
- T = NULL;
- return 0;
- }
- #include
- using namespace std;
- struct BiNode
- {
- string data;
- BiNode* lchild, * rchild;
- };
- typedef BiNode* BiTree;
-
- int InitBiTree(BiTree& T)
- {
- T = NULL;
- return 0;
- }
-
- string SucTraverse_nonRec(BiTree T)
- {
- string result="";
- stack
s; - BiTree cur=T;
- BiTree prev=NULL;
- while(cur!=NULL || !s.empty()){
- while(cur!=NULL){
- s.push(cur);
- cur=cur->lchild;
- }
- BiTree top=s.top();
- if(top->rchild==NULL || top->rchild==prev){
- result+=top->data;
- s.pop();
- prev=top;
- }
- else{
- cur=top->rchild;
- }
- }
- return result;
- }
- char* CreateBiTree(BiTree& T, char* str)
- {
- if (*str == '#')
- {
- T = NULL;
- return str + 1;
- }
-
- T = new BiNode;
- T->data = *str;
- char* strAfterLeft = CreateBiTree(T->lchild, str + 1);
- char* strAfterRight = CreateBiTree(T->rchild, strAfterLeft);
-
- return strAfterRight;
- }
-
- int SucTraverse(BiTree T) {
- if (T == NULL) return 0;
- SucTraverse(T->lchild);
- SucTraverse(T->rchild);
- cout << T->data;
- return 0;
- }
-
- int DestroyBiTree(BiTree& T) {
- if (T == NULL) return 0;
- DestroyBiTree(T->lchild);
- DestroyBiTree(T->rchild);
- delete T;
- T = NULL;
- return 0;
- }
- // int main(){
- // // char *str = "abd###ceg##h##f#i##";
- // char str[2000];
- // while(cin >> str)
- // {
- // BiTree tree;
- // InitBiTree(tree);
- // // 根据带空节点的前序遍历字符串构造二叉树
- // CreateBiTree(tree, str);
- // // 后序遍历递归算法
- // SucTraverse(tree);
- // cout << endl;
- // // 后序遍历非递归算法
- // string result = SucTraverse_nonRec(tree);
- // cout << result << endl;
- // DestroyBiTree(tree);
- // }
- // return 0;
- // }
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e6+10;
- signed main()
- {
- string a,b;
- while(cin>>a>>b){
- cout<
find(a[0])< - }
-
- }
问题 E: 根据前序+中序还原二叉树
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- signed main()
- {
- function<void(string,string)> post1=[&](string a,string b){
- int l=a.length();
- if(l==0) return;
- if(l==1)
- {
- cout<0];
- return;
- }
- int p=b.find(a[0]);
- post1(a.substr(1,p),b.substr(0,p));
- post1(a.substr(p+1,l-p-1),b.substr(p+1,l-p-1));
- cout<0];
- };
- string a,b;
- while(cin>>a>>b)
- {
- post1(a,b);
- cout<<'\n';
- }
- }
问题 F: 算法6-12:自底向上的赫夫曼编码
- #include
- using namespace std;
- typedef struct {
- int parent;
- int weight;
- int lch;
- int rch;
- }Huffnode;
- Huffnode h[205];
- typedef struct {
- char code[15];
- }Hufftree;
- Hufftree hcd[102];
- int CreateHufftree(Huffnode hn[],int n)
- {
- for(int i=n;i<2*n-1;i++)
- h[i].weight=0;
- for(int i=0;i<2*n-1;i++)
- h[i].parent=h[i].lch=h[i].rch=-1;
-
- for(int i=n;i<2*n-1;i++)
- {
- int min1=INT_MAX,min2=INT_MAX;
- int index1,index2;
- for(int j=0;j
- {
- if(h[j].weight
-1) - {
- min1=h[j].weight;
- index1=j;
- }
- }
- h[index1].parent=i;
- for(int j=0;j
- {
- if(h[j].weight
-1) - {
- min2=h[j].weight;
- index2=j;
- }
- }
- h[index2].parent=i;
- if(index1>index2)
- {
- swap(min1,min2);
- swap(index1,index2);
- }
- h[i].weight=min1+min2;
- h[i].lch=index1;
- h[i].rch=index2;
- }
- return 0;
- }
- int Createhuffcode(Huffnode h[],Hufftree hcd[],int n)
- {
- int head=0;
- char s[15];
- for(int i=0;i
- {
- int par=h[i].parent;
- int j=i;
- while(par!=-1)
- {
- if(h[par].lch==j) s[head]='0';
- else s[head]='1';
- head++;
- j=par;
- par=h[par].parent;
- }
- int k=0;
- while(head>0)
- {
- head--;
- hcd[i].code[k]=s[head];
- k++;
- }
- cout<
- head=0;
- }
- return 0;
- }
- int main()
- {
- int n;
- while(cin>>n)
- {
- for(int i=0;i
- cin>>h[i].weight;
- CreateHufftree(h,n);
- Createhuffcode(h,hcd,n);
- }
- }
问题 G: 视频合并问题
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=100010;
- int a[N];
- signed main(){
- int n,x,res=0;
- priority_queue<int,vector<int>,greater<int> >heap;
- cin>>n;
- while(n--){
- cin>>x;
- heap.push(x);
- }
- while(heap.size()>1){
- int a=heap.top();
- heap.pop();
- int b=heap.top();
- heap.pop();
- res+=(a+b);
- heap.push(a+b);
- }
- cout<
- return 0;
- }
问题 H: 二叉树实现的简单物种识别系统-附加代码模式
- #include
- using namespace std;
-
- struct BiNode
- {
- string data;
- BiNode *lchild, *rchild;
- };
- typedef BiNode *BiTree;
-
- int InitBiTree(BiTree &T)
- {
- T = NULL;
- return 0;
- }
-
-
- BiNode *StartRecognize(BiTree T)
- {
- BiTree p=T;
- char c;
- for(int i=0;i<2;i++){
- cin>>c;
- if(c=='y'||c=='Y'){
- p=p->rchild;
- }else{
- p=p->lchild;
- }
- }
- return p;
- }
-
- BiNode* getNode(string data){
- BiNode* node = new BiNode();
- node->data = data;
- node->lchild = node->rchild = nullptr;
- }
数据的同学强烈建议python+if
- a = input()
- b = input()
- if a == 'y' or a =='Y':
- if b == 'y' or b =='Y':
- print("the answer is:eagle")
- else:
- print("the answer is:swallow")
- else:
- if b == 'y' or b =='Y':
- print("the answer is:tiger")
- else:
- print("the answer is:rabbit")
问题 I: 静态链表存储的二叉树查找根节点
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e6+10;
- int s1[N];
- char s2[N];
- signed main(){
- int T=2;
- while(T--)
- {
- memset(s1,0,sizeof s1);
- int n;
- cin>>n;
- fer(j,0,n-1)
- {
- cin>>s2[j];
- char a,b;
- cin>>a>>b;
- if (a != '-')
- s1[a - '0']++;
- if (b != '-')
- s1[b - '0']++;
- }
- fer(j,0,n-1)
- {
- if(s1[j]==0)
- {
- cout<
- break;
- }
- }
- }
- }
问题 J: 基础实验4-2.1:树的同构
- #include
- using namespace std;
- struct TreeNode{
- char data;
- int left;
- int right;
- }T1[10],T2[10];
- int a[100];
- int BuildTree(TreeNode T[])
- {
- memset(a,0,sizeof a);
- int n;
- int root=-1;
- cin>>n;
- for(int i=0;i
- { char cl,cr;
- cin>>T[i].data>>cl>>cr;
- if(cl!='-')
- {
- T[i].left=cl-'0';
- a[cl-'0']=1;
- }
- else{
- T[i].left=-1;
- }
- if(cr!='-')
- {
- T[i].right=cr-'0';
- a[cr-'0']=1;
- }
- else{
- T[i].right=-1;
- }
- }
- for(int i=0;i
- {
- if(a[i]==0)
- {
- root=i;
- break;
- }
- }
- return root;
- }
- int judge(int R1,int R2)
- {
- if(R1==-1&&R2==-1){
- return 1;
- }
- if((R1==-1&&R2!=-1)||(R1!=-1&&R2==-1)){
- return 0;
- }
- if((R1!=-1&&R2!=-1)&&T1[R1].data!=T2[R2].data){
- return 0;
- }
- if(T1[R1].left==-1&&T2[R2].left==-1){
- return judge(T1[R1].right,T2[R2].right);
- }
- if((T1[R1].left!=-1&&T2[R2].left!=-1)&&T1[T1[R1].left].data==T2[T2[R2].left].data){
- return judge(T1[R1].left,T2[R2].left)&&judge(T1[R1].right,T2[R2].right);
- }
- else{
- return judge(T1[R1].left,T2[R2].right)&&judge(T1[R1].right,T2[R2].left);
- }
- }
- int main()
- {
- int root1=BuildTree(T1);
- int root2=BuildTree(T2);
- if(judge(root1,root2))
- {
- cout<<"Yes";
- }
- else{
- cout<<"No";
- }
- }
问题 K: 哈夫曼树--查找值最小的两个叶节点
- #include
- #define int long long
- #define pb push_back
- #define fer(i,a,b) for(int i=a;i<=b;++i)
- #define der(i,a,b) for(int i=a;i>=b;--i)
- #define all(x) (x).begin(),(x).end()
- #define pll pair
- #define et cout<<'\n'
- #define xx first
- #define yy second
- using namespace std;
- template <typename _Tp>void input(_Tp &x){
- char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
- x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
- if(f)x=-x;
- }
- template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
- const int N=1e6+10;
- pll a[N];
- signed main(){
- int n;
- cin>>n;
- fer(i,1,n){
- cin>>a[i].first;
- a[i].second=i-1;
- }
- sort(a+1,a+1+n);
- }
问题 L: 静态链表存储的二叉树的非递归遍历算法-附加代码模式
- #include
- using namespace std;
-
- struct BiNode
- {
- char data;
- char lchild;
- char rchild;
- int flag = 0;
- };
-
- struct BiTree
- {
- int nodeNumber;
- BiNode data[10];
- int rootIndex;
- };
-
- void FindRootIndex(BiTree & T){
- vector<char> v;
- for (int i = 0; i < T.nodeNumber; ++i) {
- if (T.data[i].lchild != '-') v.push_back(T.data[i].lchild-'0');
- if (T.data[i].rchild != '-') v.push_back(T.data[i].rchild-'0');
- }
- for (int i = 0; i < T.nodeNumber; ++i) {
- if (find(v.begin(), v.end(), i) == v.end())
- {
- T.rootIndex = i;
- return;
- }
- }
- }
-
- string getPreTraverseStr(const BiTree & T){
- if (T.nodeNumber <= 0) return "";
- string s;
- stack
sta; - sta.push(T.data[T.rootIndex]);
- while (!sta.empty())
- {
- BiNode t;
- t = sta.top();
- sta.pop();
- s += t.data;
- if (t.rchild != '-') sta.push(T.data[t.rchild-'0']);
- if (t.lchild != '-') sta.push(T.data[t.lchild-'0']);
- }
- return s;
- }
-
- string getInTraverseStr(const BiTree & T){
- if (T.nodeNumber <= 0) return "";
- string s;
- stack
sta; - sta.push(T.data[T.rootIndex]);
- while (!sta.empty())
- {
- if (sta.top().flag == 0) {
- sta.top().flag++;
- if (sta.top().lchild != '-') {
- sta.push(T.data[sta.top().lchild - '0']);
- }
- }
- else
- {
- BiNode t;
- t = sta.top();
- sta.pop();
- s += t.data;
- if (t.rchild != '-')
- {
- sta.push(T.data[t.rchild-'0']);
- }
- }
-
- }
- return s;
- }
-
- string getSucTraverseStr(const BiTree & T){
- if (T.nodeNumber <= 0) return "";
- string s;
- stack
sta; - sta.push(T.data[T.rootIndex]);
- while (!sta.empty())
- {
- if (sta.top().flag == 0)
- {
- sta.top().flag++;
- if (sta.top().lchild != '-')
- {
- sta.push(T.data[sta.top().lchild-'0']);
- }
- }
- else if (sta.top().flag == 1)
- {
- sta.top().flag++;
- if (sta.top().rchild != '-')
- {
- sta.push(T.data[sta.top().rchild-'0']);
- }
- }
- else
- {
- s += sta.top().data;
- sta.pop();
- }
- }
- return s;
- }
-
相关阅读:
2020年MathorCup数学建模B题养老服务床位需求预测与运营模式研究全过程解题程序及多篇论文
【Mask-RCNN】基于Mask-RCNN的目标检测和识别
记录一次递归查询导致的 java.lang.StackOverflowError: null
古代汉语(王力版)笔记 通论8-9
关于.model.meta,.model.index,.model.data-00000-of-00001--学习笔记
请问idea git分支树为什么会这样
haas506 2.0开发教程-hota(仅支持2.2以上版本)
oak深度相机入门教程-累积行人计数
【GB28181】wvp-GB28181-pro修改分屏监控为16画面(前端)
西门子CT重建算法
-
原文地址:https://blog.csdn.net/m0_61735576/article/details/127663058