非递归实现树的遍历

非递归实现树的遍历

【非递归实现树的遍历代码】

#include <iostream>
#include <stack>
using namespace std;

typedef struct Node{
 char key;
 struct Node *lchild, *rchild;
}*Tree, TNode;

void PreOrder(Tree T) //先序遍历
{
 if (T == NULL)
  return;
 TNode *curr = T;
 //TNode *tmp;
 stack<Tree> s;
 while (curr != NULL || !s.empty()) {
  if (curr != NULL) {
   cout<<curr->key;
   s.push(curr);
   curr = curr->lchild;
  }
  else {
   curr = s.top();
   s.pop();
   curr = curr->rchild;
  }
 }
 /*
 while (curr != NULL) {
  cout<<curr->key;
  s.push(curr);
  curr = curr->lchild;
 }
 while(!s.empty()) {
  curr = s.top();
  s.pop();
  tmp = curr->rchild;
  while(tmp != NULL) {
   cout<<tmp->key;
   s.push(tmp);
   tmp = tmp->lchild;
  }
 }
 */
}

void InOrder(Tree T)  //中序遍历
{
 if (T == NULL)
  return;
 TNode *curr = T;
 //TNode *tmp;
 stack<Tree> s;
 while ((curr != NULL) || !s.empty()) {
  if (curr != NULL) {
   s.push(curr);
   curr = curr->lchild;
  }
  else {
   curr = s.top();
   cout<<curr->key;
   s.pop();
   curr = curr->rchild;
  }
 }

}

void PostOrder(Tree T) //后序遍历
{
 if (T == NULL)
  return ;
 TNode *curr = T, *pre = NULL;
 stack<Tree> s;
 while (curr != NULL || !s.empty()) {
  if (curr != NULL) {
   s.push(curr);
   curr = curr->lchild;
  }
  else {
   curr = s.top();
   s.pop();
   if (curr->rchild != NULL && curr->rchild != pre) {
    s.push(curr);
    curr = curr->rchild;
   }
   else {
    cout<<curr->key;
    pre = curr;
    curr = NULL;
   }
  }
 }
}

Tree createTree(char *s, int n, int i) //建树
{
 if (i >= n)
  return NULL;
 TNode *curr;
 curr = (TNode *)malloc(sizeof(TNode));
 curr->key = s[i];
 
 curr->lchild = createTree(s, n, 2*(i+1)-1);
 curr->rchild = createTree(s, n, 2*(i+1));
 return curr;
}

void freeTree(Tree T)  //释放
{
 if (T != NULL){
  freeTree(T->lchild);
  freeTree(T->rchild);
  delete T;
 }
}

int main(void)
{
 char s[] = "ABCDEFG";
 Tree T;
 T = createTree(s, 7, 0);
 InOrder(T);
 cout<<endl;
 PreOrder(T);
 cout<<endl;
 PostOrder(T);
 cout<<endl;
 freeTree(T);
 return 0;
}

C语言实现二叉树的递归遍历与非递归遍历

二叉树递归实现与二重指针

本文永久更新链接地址：