【数据结构】之一、二叉树创建,前中后序遍历

前端之家收集整理的这篇文章主要介绍了【数据结构】之一、二叉树创建,前中后序遍历前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

代码积累日志!

http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91 这里都有介绍二叉树的基本概念!

下面看二叉树数据结构:

  1. #define Type char
  2.  
  3. typedef struct BiTNode{
  4. Type data;
  5. struct BiTNode *lchild,*rchild;
  6. }BiTNode,*BiTree;
  7.  
  8. typedef struct{
  9. BiTree data;
  10. bool is;
  11. }PostNode;


下面看二叉树基本操作:

  1. BiTree CreateTree()
  2. {
  3. BiTree T = NULL;
  4. Type e;
  5.  
  6. cout << "请输入数据(#结束):";
  7. cin >> e;
  8. if(e != '#')
  9. {
  10. T = (BiTree)malloc(sizeof(BiTNode));
  11. T->data = e;
  12. T->lchild = CreateTree();
  13. T->rchild = CreateTree();
  14. }
  15. else
  16. return NULL;
  17.  
  18. return T;
  19.  
  20. }
  21.  
  22. void MakeEmpty(BiTree &T)
  23. {
  24. if(T)
  25. {
  26. if(T->lchild)
  27. MakeEmpty(T->lchild);
  28. if(T->rchild)
  29. MakeEmpty(T->rchild);
  30. free(T);
  31.  
  32. T = NULL;
  33. }
  34.  
  35. }
  36.  
  37.  
  38. void Find(BiTree T,Type e)
  39. {
  40. if(T->data == e)
  41. {
  42. cout << "yes" << endl;
  43. return ;
  44. }
  45. else
  46. {
  47. if(T->lchild)
  48. Find(T,e);
  49. if(T->rchild)
  50. Find(T,e);
  51. }
  52.  
  53. cout << "no" << endl;
  54. }


下面看前序遍历的递归和非递归操作:

非递归操作需要用到stack结构。

  1. void PreOrderTraverse(BiTree T)
  2. {
  3. if(!T)
  4. return ;
  5. cout << T->data << endl;
  6. PreOrderTraverse(T->lchild);
  7. PreOrderTraverse(T->rchild);
  8. }
  9.  
  10. void PreOrderTraverse2(BiTree T)
  11. {
  12. stack<BiTNode*> s;
  13. BiTree q = T;
  14. while(q != NULL || !s.empty())
  15. {
  16. while(q != NULL)
  17. {
  18. cout << q->data << endl;
  19. s.push(q);
  20. q = q->lchild;
  21. }
  22. if(!s.empty())
  23. {
  24. q = s.top();
  25. s.pop();
  26. q = q->rchild;
  27. }
  28. }
  29. }


下面看中序遍历的递归和非递归操作:

非递归需要stack结构。

  1. void InOrderTraverse(BiTree T)
  2. {
  3. if(T == NULL)
  4. return ;
  5. InOrderTraverse(T->lchild);
  6. cout << T->data << endl;
  7. InOrderTraverse(T->rchild);
  8. }
  9.  
  10. void InOrderTraverse2(BiTree T)
  11. {
  12. stack<BiTNode*> s;
  13. BiTree q = T;
  14. while(q != NULL || !s.empty())
  15. {
  16. while(q != NULL)
  17. {
  18. s.push(q);
  19. q = q->lchild;
  20. }
  21. if(!s.empty())
  22. {
  23. q = s.top();
  24. cout << q->data << endl;
  25. s.pop();
  26. q = q->rchild;
  27. }
  28. }
  29. }


下面看后序遍历的递归非递归:

非递归也用到stack,这里较麻烦。

  1. void PostOrderTraverse(BiTree T)
  2. {
  3. if(T == NULL)
  4. return ;
  5. PostOrderTraverse(T->lchild);
  6. PostOrderTraverse(T->rchild);
  7. cout << T->data << endl;
  8. }
  9.  
  10. void PostOrderTraverse2(BiTree T)
  11. {
  12. stack<PostNode*> s;
  13. PostNode* postq;
  14. BiTree q = T;
  15. while(q != NULL || !s.empty())
  16. {
  17. while(q != NULL)
  18. {
  19. PostNode *postq = (PostNode*)malloc(sizeof(PostNode));
  20. postq->data = q;
  21. postq->is = true;
  22. s.push(postq);
  23. q = q->lchild;
  24. }
  25.  
  26. if(!s.empty())
  27. {
  28. postq = s.top();
  29. s.pop();
  30. if(postq->is == true)
  31. {
  32. postq->is = false;
  33. s.push(postq);
  34. q = postq->data->rchild;
  35. }
  36. else
  37. {
  38. cout << postq->data->data << endl;
  39. q = NULL;
  40. }
  41. }
  42. }
  43. }


下面看层序遍历:

此处需要用到队列deque。

  1. void LayerOrderTraverse(BiTree T)
  2. {
  3. deque<BiTree> q;
  4. BiTree p;
  5. if(T)
  6. {
  7. q.push_back(T);
  8. }
  9. else
  10. return;
  11.  
  12. while(!q.empty())
  13. {
  14. p = q.front();
  15. q.pop_front();
  16. cout << p->data << endl;
  17. if(p->lchild)
  18. {
  19. q.push_back(p->lchild);
  20. }
  21. if(p->rchild)
  22. {
  23. q.push_back(p->rchild);
  24. }
  25. }
  26. }



2013.8.2

jofranks 于南昌

猜你在找的数据结构相关文章