代码积累日志!
http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91 这里都有介绍二叉树的基本概念!
下面看二叉树数据结构:
- #define Type char
- typedef struct BiTNode{
- Type data;
- struct BiTNode *lchild,*rchild;
- }BiTNode,*BiTree;
- typedef struct{
- BiTree data;
- bool is;
- }PostNode;
下面看二叉树基本操作:
- BiTree CreateTree()
- {
- BiTree T = NULL;
- Type e;
- cout << "请输入数据(#结束):";
- cin >> e;
- if(e != '#')
- {
- T = (BiTree)malloc(sizeof(BiTNode));
- T->data = e;
- T->lchild = CreateTree();
- T->rchild = CreateTree();
- }
- else
- return NULL;
- return T;
- }
- void MakeEmpty(BiTree &T)
- {
- if(T)
- {
- if(T->lchild)
- MakeEmpty(T->lchild);
- if(T->rchild)
- MakeEmpty(T->rchild);
- free(T);
- T = NULL;
- }
- }
- void Find(BiTree T,Type e)
- {
- if(T->data == e)
- {
- cout << "yes" << endl;
- return ;
- }
- else
- {
- if(T->lchild)
- Find(T,e);
- if(T->rchild)
- Find(T,e);
- }
- cout << "no" << endl;
- }
下面看前序遍历的递归和非递归操作:
非递归操作需要用到stack结构。
- void PreOrderTraverse(BiTree T)
- {
- if(!T)
- return ;
- cout << T->data << endl;
- PreOrderTraverse(T->lchild);
- PreOrderTraverse(T->rchild);
- }
- void PreOrderTraverse2(BiTree T)
- {
- stack<BiTNode*> s;
- BiTree q = T;
- while(q != NULL || !s.empty())
- {
- while(q != NULL)
- {
- cout << q->data << endl;
- s.push(q);
- q = q->lchild;
- }
- if(!s.empty())
- {
- q = s.top();
- s.pop();
- q = q->rchild;
- }
- }
- }
下面看中序遍历的递归和非递归操作:
非递归需要stack结构。
- void InOrderTraverse(BiTree T)
- {
- if(T == NULL)
- return ;
- InOrderTraverse(T->lchild);
- cout << T->data << endl;
- InOrderTraverse(T->rchild);
- }
- void InOrderTraverse2(BiTree T)
- {
- stack<BiTNode*> s;
- BiTree q = T;
- while(q != NULL || !s.empty())
- {
- while(q != NULL)
- {
- s.push(q);
- q = q->lchild;
- }
- if(!s.empty())
- {
- q = s.top();
- cout << q->data << endl;
- s.pop();
- q = q->rchild;
- }
- }
- }
非递归也用到stack,这里较麻烦。
- void PostOrderTraverse(BiTree T)
- {
- if(T == NULL)
- return ;
- PostOrderTraverse(T->lchild);
- PostOrderTraverse(T->rchild);
- cout << T->data << endl;
- }
- void PostOrderTraverse2(BiTree T)
- {
- stack<PostNode*> s;
- PostNode* postq;
- BiTree q = T;
- while(q != NULL || !s.empty())
- {
- while(q != NULL)
- {
- PostNode *postq = (PostNode*)malloc(sizeof(PostNode));
- postq->data = q;
- postq->is = true;
- s.push(postq);
- q = q->lchild;
- }
- if(!s.empty())
- {
- postq = s.top();
- s.pop();
- if(postq->is == true)
- {
- postq->is = false;
- s.push(postq);
- q = postq->data->rchild;
- }
- else
- {
- cout << postq->data->data << endl;
- q = NULL;
- }
- }
- }
- }
下面看层序遍历:
此处需要用到队列deque。
- void LayerOrderTraverse(BiTree T)
- {
- deque<BiTree> q;
- BiTree p;
- if(T)
- {
- q.push_back(T);
- }
- else
- return;
- while(!q.empty())
- {
- p = q.front();
- q.pop_front();
- cout << p->data << endl;
- if(p->lchild)
- {
- q.push_back(p->lchild);
- }
- if(p->rchild)
- {
- q.push_back(p->rchild);
- }
- }
- }
2013.8.2
jofranks 于南昌