二叉树遍历

 1#include <cstdio>
 2#include <queue>
 3#include <stack>
 4#define ElemType int
 5#define EndTag 0
 6using namespace std;
 7
 8// 二叉树的链式存储
 9typedef struct Node{
10 ElemType data;
11 struct Node *left, *right;
12} Node, *BinTree;

 1// 初始化二叉树
 2void InitTree(BinTree &T){
 3 T = new Node;
 4 if(T == NULL)
 5  return;
 6 T->left = T->right = NULL;
 7}
 8
 9// 从文件输入流创建二叉树(前序遍历建立)
10void CreateTree(BinTree &T, istream &in)
11{
12 ElemType e;
13 if(in.peek() != EOF)
14 {
15  in >> e;
16  if(e == EndTag)
17   T = NULL;
18  else{
19   T = new Node;T->data = e;
20   T->left = T->right = NULL;
21   CreateTree(T->left, in);
22   CreateTree(T->right, in);
23  }
24 }
25}

 1// 二叉树前序递归遍历
 2void PreOrder(BinTree &T)
 3{
 4 if(T)
 5 {
 6  printf("%d ", T->data);
 7  PreOrder(T->left);
 8  PreOrder(T->right);
 9 }
10}

 1// 二叉树前序非递归遍历
 2void PreOrder_NR(BinTree &T)
 3{
 4 if(T == NULL)
 5  return;
 6 stack<Node *> S;
 7 S.push(T); Node *cur;
 8 while(!S.empty())
 9 {
10  cur = S.top(); S.pop();
11  printf("%d ", cur->data);
12  if(cur->right != NULL)
13   S.push(cur->right);
14  if(cur->left != NULL)
15   S.push(cur->left);
16 }
17}

 1// 二叉树中序递归遍历
 2void InOrder(BinTree &T)
 3{
 4 if(T)
 5 {
 6  InOrder(T->left);
 7  printf("%d ", T->data);
 8  InOrder(T->right);
 9 }
10}

 1// 二叉树中序非递归遍历
 2void InOrder_NR(BinTree &T)
 3{
 4 stack<Node *> S;
 5 Node *cur = T;
 6 while(cur != NULL || !S.empty())
 7 {
 8  // 将左子女链上结点全部压栈
 9  while(cur != NULL)
10  {
11   S.push(cur);
12   cur = cur->left;
13  }
14  cur = S.top(); S.pop(); 
15  printf("%d ", cur->data); 
16  cur = cur->right; 
17 } 
18}

 1// 二叉树后序递归遍历
 2void PostOrder(BinTree &T)
 3{
 4 if(T)
 5 {
 6  PostOrder(T->left);
 7  PostOrder(T->right);
 8  printf("%d ", T->data);
 9 }
10}

 1// 二叉树后序非递归遍历(附加前驱指针法)
 2void PostOrder_NR(BinTree &T)
 3{
 4 if(!T)
 5  return;
 6 stack<Node *> S; S.push(T);
 7 Node *cur, *pre = NULL; // 当前指针cur和后序前驱指针pre
 8 while(!S.empty())
 9 {
10  cur = S.top();
11  if(!cur->left && !cur->right)
12  {
13   // 当前结点两个子树都为空
14   S.pop(); printf("%d ", cur->data); 
15   pre = cur;
16  }else if(pre && (cur->left == pre || cur->right == pre)){
17   // 当前结点存在子树不为空,但已被访问过
18   S.pop(); printf("%d ", cur->data); 
19   pre = cur;
20  }else{
21   // 当前结点存在子树不为空,并且没有被访问过
22   if(cur->right)
23    S.push(cur->right); // 右子女不为空,则先将右子女压栈
24   if(cur->left)
25    S.push(cur->left); // 左子女不为空,则将左子女压栈
26  } 
27 }
28}

 1// 二叉树后序非递归遍历(重复入栈法)
 2void PostOrder_NR2(BinTree &T)
 3{
 4 if(!T)
 5  return;
 6 stack<Node *> S; S.push(T); S.push(T);
 7 Node *cur;
 8 while(!S.empty())
 9 {
10  cur = S.top(); S.pop();
11  if(!S.empty() && cur == S.top())
12  {
13   // 栈不空并且cur是第一次被访问
14   if(cur->right)
15   {
16    S.push(cur->right); S.push(cur->right);
17   }
18   if(cur->left)
19   {
20    S.push(cur->left); S.push(cur->left);
21   }
22  }else
23   printf("%d ", cur->data);
24 }
25}

1enum Tag{L,R};
2
3// 附加标志tag用于后序非递归遍历
4typedef struct Node{
5 ElemType data;
6 struct Node *left, *right;
7 Tag tag; // 后序非递归遍历的标志位
8} Node, *BinTree;

 1// 二叉树后序非递归遍历(附加tag标志法)
 2void PostOrder_NR3(BinTree &T)
 3{
 4 stack<Node*> S;
 5 Node *cur = T, *temp; 
 6 while(cur || !S.empty())
 7 {
 8  while(cur)
 9  {
10   cur->tag = L;
11   S.push(cur);
12   cur = cur->left;
13  }
14  if(!S.empty())
15  {
16   temp = S.top();
17   if(temp->tag == L)
18   {
19    temp->tag = R;
20    cur = temp->right;
21   }else{
22    S.pop();
23    printf("%d ", temp->data);
24   }
25  }
26 }
27
28}

 1// 层次序遍历
 2void LevelOrder(BinTree &T)
 3{
 4 if(!T)
 5  return;
 6 queue<Node *> Q;
 7 Q.push(T); Node *cur;
 8 while(!Q.empty())
 9 {
10  cur = Q.front(); Q.pop();
11  printf("%d ", cur->data);
12  if(cur->left)
13   Q.push(cur->left);
14  if(cur->right)
15   Q.push(cur->right);
16 }
17}