非递归达成树的遍历

发布时间：2021-11-20 12:56:18 所属栏目：PHP教程来源：互联网

导读：【非递归实现树的遍历代码】 #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

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

#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;
}

（编辑：应用网_丽江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php读取大文件最好的实	php无限遍历文件夹示例
php中实现过滤UBB代码	Laravel模板引擎Blade