当前位置:   article > 正文

数据结构-二叉树-头歌(交换左右子树/寻找最长路径(长度及路径)/WPL/双序遍历/二叉树最大宽度/二叉树表达数)_二叉树结点data数据的修改头歌

二叉树结点data数据的修改头歌

基于二叉链表的二叉树左右孩子的交换 

  1. //交换左右子树
  2. #include<iostream>
  3. #include<cstring>
  4. using namespace std;
  5. typedef struct BiTNode
  6. {
  7. char data;
  8. struct BiTNode *lchild,*rchild;
  9. }BiTNode,*BiTree;
  10. void CreateBiTree(BiTree &T,char S[],int &i)
  11. {//先序建立二叉树
  12. if(S[i]=='0')
  13. T=NULL;
  14. else
  15. {
  16. T=new BiTNode;
  17. T->data=S[i];
  18. CreateBiTree(T->lchild,S,++i);
  19. CreateBiTree(T->rchild,S,++i);
  20. }
  21. }
  22. void ChangeRL(BiTree &T)
  23. {//二叉树左右孩子的交换
  24. /**************begin************/
  25. if (T == 0) {
  26. return;
  27. }
  28. BiTNode *temp;
  29. temp=T->lchild;
  30. T->lchild=T->rchild;
  31. T->rchild=temp;
  32. ChangeRL(T->lchild);
  33. ChangeRL(T->rchild);
  34. /**************end************/
  35. }
  36. void PreOrderTraverse(BiTree T)
  37. {//先序遍历
  38. if(T)
  39. {
  40. cout<<T->data;
  41. PreOrderTraverse(T->lchild);
  42. PreOrderTraverse(T->rchild);
  43. }
  44. }
  45. int main()
  46. {
  47. char S[100];
  48. while(cin>>S)
  49. {
  50. if(strcmp(S,"0")==0) break;
  51. int i=-1;
  52. BiTree T;
  53. CreateBiTree(T,S,++i);
  54. ChangeRL(T);
  55. PreOrderTraverse(T);
  56. cout<<endl;
  57. }
  58. return 0;
  59. }

基于二叉链表的二叉树的双序遍历

  1. #include<iostream>
  2. #include <string.h>
  3. using namespace std;
  4. typedef struct BiTNode
  5. {
  6. char data;
  7. struct BiTNode *lchild,*rchild;
  8. }BiTNode,*BiTree;
  9. void CreateBiTree(BiTree &T,char S[],int &i)
  10. {//先序建立二叉树
  11. if(S[i]=='0')
  12. T=NULL;
  13. else
  14. {
  15. T=new BiTNode;
  16. T->data=S[i];
  17. CreateBiTree(T->lchild,S,++i);
  18. CreateBiTree(T->rchild,S,++i);
  19. }
  20. }
  21. void DoubleTraverse(BiTree T)
  22. {//双序遍历二叉树T的递归算法
  23. /**************begin************/
  24. if (T==0) {
  25. return;
  26. }
  27. cout<<T->data;
  28. DoubleTraverse(T->lchild);
  29. cout<<T->data;
  30. DoubleTraverse(T->rchild);
  31. /**************end************/
  32. }
  33. int main()
  34. {
  35. char S[100];
  36. while(cin>>S)
  37. {
  38. if(strcmp(S,"0")==0) break;
  39. int i=-1;
  40. BiTree T;
  41. CreateBiTree(T,S,++i);
  42. DoubleTraverse(T);
  43. cout<<endl;
  44. }
  45. return 0;
  46. }

基于二叉链表的二叉树最大宽度的计算

  1. #include <iostream>
  2. #include <string.h>
  3. #include <queue>
  4. #include <stdlib.h>
  5. using namespace std;
  6. typedef struct BiTNode
  7. {
  8. char data;
  9. struct BiTNode *lchild,*rchild;
  10. }BiTNode,*BiTree;
  11. BiTree CreateBiTree(int &pos, char *str)
  12. {// 先序建立二叉树
  13. char c=str[pos++];
  14. if(c=='0') return NULL;
  15. BiTree root=new BiTNode();
  16. root->data=c;
  17. root->lchild=CreateBiTree(pos,str);
  18. root->rchild=CreateBiTree(pos,str);
  19. return root;
  20. }
  21. int Width(BiTree T)
  22. {// 求二叉树T最大宽度
  23. /**************begin************/
  24. int max=0;
  25. queue <BiTree> q;
  26. if (T==0) {
  27. return 0;
  28. }
  29. if (T !=NULL)
  30. {
  31. q.push(T); //根节点进队列
  32. }
  33. while (q.empty() == false) //队列不为空判断
  34. {
  35. int size = q.size();
  36. while(size--)//遍历当前层的元素
  37. {
  38. BiTNode* temp=q.front();
  39. q.pop();
  40. if(temp->lchild) q.push(temp->lchild);
  41. if(temp->rchild) q.push(temp->rchild);
  42. }
  43. if(max<q.size())max=q.size();
  44. }
  45. return max;
  46. /**************end************/
  47. }
  48. int main()
  49. {
  50. char str[1000];
  51. while(cin>>str)
  52. {
  53. if(strcmp(str,"0")==0) break;
  54. int pos=0; // 标记字符串处理位置
  55. BiTree root=CreateBiTree(pos,str);
  56. cout<<Width(root)<<endl;
  57. }
  58. return 0;
  59. }

 基于二叉链表的二叉树最长路径的求解

  1. #include<iostream>
  2. #include<vector>
  3. #include<queue>
  4. #define MAXSIZE 100
  5. using namespace std;
  6. typedef struct BiTNode
  7. {
  8. char data;
  9. struct BiTNode *lchild,*rchild;
  10. }BiTNode,*BiTree;
  11. void CreateBiTree(BiTree &T,char S[],int &i)
  12. {//程序生成器
  13. if(S[i]=='0')
  14. T=NULL;
  15. else
  16. {
  17. T=new BiTNode;
  18. T->data=S[i];
  19. CreateBiTree(T->lchild,S,++i);
  20. CreateBiTree(T->rchild,S,++i);
  21. }
  22. }
  23. void LongestPath(BiTree T)
  24. {
  25. if (T == nullptr)
  26. {
  27. cout << "The tree is empty." << endl;
  28. return;
  29. }
  30. vector<char> currentPath;
  31. vector<char> longestPath;
  32. queue<pair<BiTree, vector<char>>> q;
  33. q.push({T, {T->data}});
  34. while (!q.empty())
  35. {
  36. auto current = q.front();
  37. q.pop();
  38. BiTree node = current.first;
  39. vector<char> currentPath = current.second;
  40. if (node->lchild == nullptr && node->rchild == nullptr)
  41. {
  42. if (currentPath.size() > longestPath.size())
  43. {
  44. longestPath = currentPath;
  45. }
  46. }
  47. if (node->lchild != nullptr)
  48. {
  49. vector<char> newPath = currentPath;
  50. newPath.push_back(node->lchild->data);
  51. q.push({node->lchild, newPath});
  52. }
  53. if (node->rchild != nullptr)
  54. {
  55. vector<char> newPath = currentPath;
  56. newPath.push_back(node->rchild->data);
  57. q.push({node->rchild, newPath});
  58. }
  59. }
  60. cout << longestPath.size() << endl;
  61. for (char node : longestPath)
  62. {
  63. cout << node;
  64. }
  65. cout << endl;
  66. }
  67. int main()
  68. {
  69. char S[100];
  70. while(cin>>S&&S[0]!='0')
  71. {
  72. int i=-1;
  73. BiTree T;
  74. CreateBiTree(T,S,++i);
  75. LongestPath(T);
  76. }
  77. return 0;
  78. }



基于二叉链表的二叉树叶子结点到根结点的路径的求解

  1. #include<iostream>
  2. using namespace std;
  3. char path[100]; //路径数组,存储路径上每个结点的值
  4. typedef struct BiTNode
  5. {
  6. char data;
  7. struct BiTNode *lchild,*rchild;
  8. }BiTNode,*BiTree;
  9. void CreateBiTree(BiTree &T,char S[],int &i)
  10. {//先序建立二叉树
  11. if(S[i]=='0')
  12. T=NULL;
  13. else
  14. {
  15. T=new BiTNode;
  16. T->data=S[i];
  17. CreateBiTree(T->lchild,S,++i);
  18. CreateBiTree(T->rchild,S,++i);
  19. }
  20. }
  21. void AllPath(BiTree T,char path[],int pathlen)
  22. {//二叉树叶子结点到根结点的路径的求解
  23. /**************begin************/
  24. if (T==0) {
  25. return;
  26. }
  27. path [pathlen]=T->data;
  28. pathlen++;
  29. if (T->lchild==0&&T->rchild==0) {
  30. //叶子结点
  31. for(int i=0;i<pathlen;i++){
  32. cout<<path[pathlen-i-1];
  33. }
  34. cout<<endl;
  35. }
  36. else{
  37. AllPath(T->lchild,path,pathlen);
  38. AllPath(T->rchild,path,pathlen);
  39. }
  40. /**************end************/
  41. }
  42. int main()
  43. {
  44. char S[100];
  45. while(cin>>S&&S[0]!='0')
  46. {
  47. int i=-1;
  48. BiTree T;
  49. CreateBiTree(T,S,++i);
  50. int pathlen=0; //初始化路径到根结点的长度为0
  51. AllPath(T,path,pathlen);
  52. }
  53. return 0;
  54. }

基于二叉树的表达式求值

  1. #include<iostream>
  2. #define MAXSIZE 100
  3. using namespace std;
  4. typedef struct BiTNode
  5. {//二叉树的双链表存储表示
  6. double data; //结点数据域
  7. bool ischaracter; //判断结点是否为字符
  8. struct BiTNode *lchild,*rchild; //左右孩子指针
  9. }BiTNode,*BiTree;
  10. typedef struct
  11. {//字符栈的存储结构
  12. char *base; //栈底指针
  13. char *top; //栈顶指针
  14. int stacksize; //栈可用的最大容量
  15. }SqStack1;
  16. typedef struct
  17. {//结点栈的存储结构
  18. BiTree *base;
  19. BiTree *top;
  20. int stacksize;
  21. }SqStack2;
  22. void InitStack1(SqStack1 &s)
  23. {//字符栈的初始化
  24. s.base=new char[MAXSIZE]; //为顺序栈动态分配一个最大容量为MAXSIZE的数组空间
  25. s.top=s.base; //初始为空栈
  26. s.stacksize=MAXSIZE; //置栈的最大容量为MAXSIZE
  27. }
  28. void InitStack2(SqStack2 &s)
  29. {//结点栈的初始化
  30. s.base=new BiTree[MAXSIZE];
  31. s.top=s.base;
  32. s.stacksize=MAXSIZE;
  33. }
  34. void Push1(SqStack1 &s,char ch)
  35. {//字符入栈操作
  36. if(s.top-s.base==s.stacksize) //栈满
  37. return;
  38. *s.top=ch; //元素ch压入栈顶
  39. s.top++; //栈顶指针加1
  40. }
  41. void Push2(SqStack2 &s,BiTree t)
  42. {//结点入栈操作
  43. if(s.top-s.base==s.stacksize)
  44. return;
  45. *s.top=t;
  46. s.top++;
  47. }
  48. void Pop1(SqStack1 &s,char &ch)
  49. {//字符出栈操作
  50. if(s.top==s.base) //栈空
  51. return;
  52. else
  53. {
  54. s.top--; //栈顶指针减1
  55. ch=*s.top; //将栈顶元素赋给ch
  56. }
  57. }
  58. void Pop2(SqStack2 &s,BiTree &t)
  59. {//结点出栈操作
  60. if(s.top==s.base)
  61. return;
  62. else
  63. {
  64. s.top--;
  65. t=*s.top;
  66. }
  67. }
  68. char GetTop(SqStack1 s)
  69. {//取字符栈的栈顶元素
  70. if(s.base==s.top) //栈空
  71. return -1;
  72. else
  73. return *(s.top-1); //返回栈顶元素的值,栈顶指针不变
  74. }
  75. bool EmptyStack(SqStack1 s)
  76. {//栈的判空操作
  77. if(s.base==s.top) //栈空返回true
  78. return true;
  79. else
  80. return false; //栈非空返回false
  81. }
  82. char Precede(char a,char b)
  83. {//判断符号的优先级
  84. if(a=='+'||a=='-')
  85. {
  86. if(b=='+'||b=='-'||b==')'||b=='=')
  87. return '>'; //>代表a的优先级高于b
  88. else
  89. return '<';
  90. }
  91. else if(a=='*'||a=='/')
  92. {
  93. if(b=='+'||b=='-'||b=='*'||b=='/'||b==')'||b=='=')
  94. return '>';
  95. else
  96. return '<';
  97. }
  98. else if(a=='(')
  99. {
  100. if(b==')')
  101. return '=';
  102. else
  103. return '<';
  104. }
  105. else if(a==')')
  106. return '>';
  107. else
  108. {
  109. if(b=='=')
  110. return '=';
  111. else
  112. return '<';
  113. }
  114. }
  115. double Operate(double a,char ch,double b)
  116. {//运算操作,返回相应的数值结果
  117. if(ch=='+')
  118. return a+b;
  119. else if(ch=='-')
  120. return a-b;
  121. else if(ch=='*')
  122. return a*b;
  123. else
  124. return a/b;
  125. }
  126. bool IsCharacter(char ch)
  127. {//判断ch是否为+、-、*、/、(、)、= 这类的字符,是则返回true
  128. if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='=')
  129. return true;
  130. else
  131. return false;
  132. }
  133. double InOrder(BiTree T) {
  134. if (T != nullptr) {
  135. if (T->ischaracter) {
  136. double ans1 = InOrder(T->lchild);
  137. double ans2 = InOrder(T->rchild);
  138. return Operate(ans1, T->data, ans2);
  139. } else {
  140. return T->data;
  141. }
  142. }
  143. return 0.0;
  144. }
  145. void CreateBT(char ch[],BiTree &t,SqStack1 optr,SqStack2 expt)
  146. {//创建二叉树
  147. int i=0;
  148. char opr,c[2]; //辅助数组c
  149. BiTree t1,t2;
  150. double num;
  151. while(ch[i]!='\0'||!EmptyStack(optr))
  152. {
  153. if(!IsCharacter(ch[i])) //当前遍历的不是运算符元素
  154. {
  155. c[0]=ch[i];
  156. c[1]='\0';
  157. BiTree q=new BiTNode; //生成一个新结点*q
  158. num=strtod(c,NULL); //将字符数组c转换成浮点数,赋给num
  159. q->ischaracter=false; //结点*q不为运算符
  160. q->data=num; //结点数据域置为num
  161. q->lchild=NULL; //左右孩子置为NULL
  162. q->rchild=NULL;
  163. Push2(expt,q); //将结点q压入数字栈
  164. i++; //指针i加1
  165. }//if
  166. else //当前遍历的是运算符元素
  167. {
  168. switch(Precede(GetTop(optr),ch[i])) //比较栈顶元素和当前遍历字符的优先级
  169. {
  170. case '<': //栈顶元素优先级小于当前运算符
  171. Push1(optr,ch[i]); //将当前运算符入栈
  172. i++; //指针i加1
  173. break;
  174. case '>': //栈顶元素优先级大于当前运算符
  175. Pop1(optr,opr); //运算符栈的元素出栈
  176. Pop2(expt,t2); //数字栈的栈顶元素出栈
  177. Pop2(expt,t1);
  178. t=new BiTNode; //生成新结点*t
  179. t->ischaracter=true; //结点*t为运算符
  180. t->data=opr; //结点数据域置为opr
  181. t->lchild=t1; //左孩子指向t1
  182. t->rchild=t2; //右孩子指向t2
  183. Push2(expt,t); //将结点t压入数字栈
  184. break;
  185. case '=': //栈顶元素优先级等于当前运算符
  186. Pop1(optr,opr); //运算符栈的元素出栈
  187. i++; //指针i加1
  188. break;
  189. }//switch
  190. }//else
  191. }//while
  192. }
  193. int main()
  194. {
  195. char ch[MAXSIZE];
  196. while(cin>>ch)
  197. {
  198. if(ch[0]=='=') break;
  199. BiTree t;
  200. SqStack1 optr; //运算符栈optr
  201. SqStack2 expt; //数字栈expt
  202. InitStack1(optr); //初始化栈
  203. InitStack2(expt); //初始化栈
  204. Push1(optr,'='); //先在运算符栈底放入一个'='
  205. CreateBT(ch,t,optr,expt); //创建二叉树
  206. double answer=InOrder(t);
  207. cout<<answer<<endl;
  208. }
  209. return 0;
  210. }

 二叉树的WPL计算

  1. #include<iostream>
  2. using namespace std;
  3. typedef struct BiTNode
  4. {
  5. int weight;
  6. struct BiTNode *left,*right;
  7. }BiTNode,*BiTree;
  8. void CreateBiTree(BiTree &T)
  9. {//先序建立二叉树
  10. int x;
  11. cin>>x;
  12. if(x==0) T=NULL;
  13. else
  14. {
  15. T=new BiTNode;
  16. T->weight=x;
  17. CreateBiTree(T->left);
  18. CreateBiTree(T->right);
  19. }
  20. }
  21. int WPL(BiTree T, int d) {
  22. if (T == nullptr) {
  23. return 0;
  24. } else if (T->left == 0 && T->right ==0) {
  25. return T->weight * d;
  26. } else {
  27. int wplLeft = WPL(T->left, d + 1);
  28. int wplRight = WPL(T->right, d + 1);
  29. return wplLeft + wplRight;
  30. }
  31. }
  32. int main()
  33. {
  34. while(1)
  35. {
  36. BiTree T;
  37. CreateBiTree(T);
  38. if(!T) break;
  39. int d=0; //调用时T指向二叉树的根结点,d为0
  40. cout<<WPL(T,d)<<endl;
  41. }
  42. return 0;
  43. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/737607
推荐阅读
相关标签
  

闽ICP备14008679号