Untitled

SUBMITTED BY: Guest

DATE: June 2, 2017, 1:49 p.m.

FORMAT: C++

SIZE: 3.8 kB

Raw Download

HITS: 484

Report
  1. #include<iostream>
  3. using namespace std;
  5. typedef char MyData;
  8. struct TreeNode
  9. {
  10. MyData Key;
  11. TreeNode *Next; // Con tro dong vai tro lien ket 1 danh sach lien ket don
  12. TreeNode *Left; // -------------------- lien ket tren cay ---------------
  13. TreeNode *Right;// ------------------------------------------------------
  14. }; // Node vua la Node trong LinkList vua la Node cua Tree.
  16. TreeNode* MakeTNode(MyData Data) // Tao mot node moi
  17. {
  18. TreeNode *p = new TreeNode;
  19. p->Key = Data;
  20. p->Left = NULL;
  21. p->Right = NULL;
  22. p->Next = NULL;
  23. return p;
  24. }
  26. void PushToStack(TreeNode *&pHead, TreeNode *pNode) // Day mot nut vao Stack (AddHead)
  27. {
  28. if (pHead == NULL)
  29. {
  30. pHead = pNode;
  31. }
  32. else
  33. {
  34. pNode->Next = pHead;
  35. pHead = pNode;
  36. }
  37. }
  39. MyData PopDataFromStack(TreeNode *&pHead) // Lay du lieu ra tu dinh cua Stack
  40. {
  41. if (pHead != NULL)
  42. {
  43. char tmp = pHead->Key;
  44. TreeNode *p = pHead;
  45. pHead = pHead->Next;
  46. delete p;
  47. return tmp;
  48. }
  49. }
  51. TreeNode* PopNodeFromStack(TreeNode *&pHead) // Lay mot node ra tu dinh cua Stack
  52. {
  53. if (pHead != NULL)
  54. {
  55. TreeNode *p = pHead;
  56. pHead = pHead->Next;
  57. p->Next = NULL;
  58. return p;
  59. }
  60. }
  62. TreeNode *CreateTreeNode(TreeNode *& Operator, TreeNode *& Node)
  63. {
  64. MyData tmp;
  66. tmp = PopDataFromStack(Operator);
  67. TreeNode *p = MakeTNode(tmp);
  69. TreeNode *ptmp;
  71. ptmp = PopNodeFromStack(Node);
  72. p->Right = ptmp;
  74. ptmp = PopNodeFromStack(Node);
  75. p->Left = ptmp;
  77. return p;
  78. } // Tao mot cay moi bang cach lay tu Operator Stack 1 phan tu va Node Stack 2 phan tu
  82. void PreOrderTrav(TreeNode* root) // Duyet NLR
  83. {
  84. if (root != NULL)
  85. {
  86. cout << root->Key;
  87. PreOrderTrav(root->Left);
  88. PreOrderTrav(root->Right);
  90. }
  91. }
  93. void PostOrderTrav(TreeNode *root) //Duyet LRN
  94. {
  95. if (root != NULL)
  96. {
  97. PostOrderTrav(root->Left);
  98. PostOrderTrav(root->Right);
  99. cout << root->Key;
  100. }
  101. }
  102. void TraverseInStack(TreeNode *Head)
  103. {
  104. while (Head)
  105. {
  106. cout << Head->Key;
  107. Head = Head->Next;
  108. }
  109. }
  111. int main()
  112. {
  113. TreeNode *OperatorStack = NULL , *NodeStack = NULL;
  114. // Khoi tao 2 stack
  116. char x;
  117. char tmp;
  120. do
  121. {
  122. cin >> x;
  123. if (x == '#')
  124. break;
  126. if (x == '*' || x == '/' || x == '+' || x == '-' || x == '(' || x == ')') // Neu la toan tu
  127. {
  128. if (OperatorStack == NULL || x == '(')
  130. PushToStack(OperatorStack, MakeTNode(x));
  133. else
  135. if (x == '+' || x == '-')
  137. {
  138. while (OperatorStack != NULL && OperatorStack->Key != '(')
  140. PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));
  142. PushToStack(OperatorStack, MakeTNode(x));
  144. }
  145. else
  146. if ((x=='*'|| x=='/') && (OperatorStack->Key =='*' || OperatorStack->Key == '/'))
  147. {
  148. while (OperatorStack != NULL && (OperatorStack->Key == '*' || OperatorStack->Key == '/'))
  150. PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));
  152. PushToStack(OperatorStack, MakeTNode(x));
  154. }
  155. else
  157. if (x == ')')
  158. {
  159. while (OperatorStack->Key != '(')
  161. PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));
  164. tmp = PopDataFromStack(OperatorStack);
  165. }
  166. else
  167. PushToStack(OperatorStack, MakeTNode(x));
  171. }
  172. else // Neu la toan hang
  173. PushToStack(NodeStack, MakeTNode(x));
  175. // Bo comment neu muon kiem tra stack hoat dong
  177. //////cout << "operstack: ";
  178. //////TraverseInStack(OperatorStack);
  179. //////cout << endl;
  180. //////cout << "nodestack: ";
  181. //////TraverseInStack(NodeStack);
  182. //////cout << endl;
  184. } while (x != '#');
  187. while (OperatorStack != NULL)
  188. PushToStack(NodeStack, CreateTreeNode(OperatorStack, NodeStack));
  192. PreOrderTrav(NodeStack);
  193. cout << endl;
  194. PostOrderTrav(NodeStack);
  196. return 0;
  197. }
comments powered by Disqus