c++对二叉树的先序，后序，中序递归，非递归先序，后序，中序，层次遍历

树的总结

#include <iostream>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<queue>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <numeric>
#include<stack> 
using namespace std; 

数据结构定义

• 第一种 typedef 用于定义别名，*Tree 或者 TreeNode，在后面可以直接使用 。

• 在创建树的时候， 如果传参数 则需要，Tree &T; 代码如下 《需要定义别名》

  • void preCreate(Tree &T); TreeNode *root; preCreate(root);

• 不传参数 需要定义返回类型，如下面写法 《可以不定义别名》

  • TreeNode* preCreate(); TreeNode *root = preCreate();

/** 1. 定义方式 **/
typedef struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {} 
}*Tree,BTree;

• 用于层次遍历的数据结构部分

typedef struct Node {
    TreeNode *pp;
    int tag; 
}TNode;

• 先序序列创建树

TreeNode* preCreate() {
    TreeNode *T;
    int n;
    cin>>n;
    if(n==0){
        T=NULL;
    } else {
        T=new TreeNode(n);
        T->left=preCreate();
        T->right=preCreate();
    }
    return T; 
}

7种遍历方式

• 递归《就不写了，一般递归的时候，直接在函数里面打印或者放一个vector用来存储遍历的结果，写非递归》，
• 非递归，
• 层次

递归写法

void preDGOrder(TreeNode *t) {
   if(t) {
       printf("%d ",t->val);
       preDGOrder(t->left);
       preDGOrder(t->right);
   } 
}

先序非递归 — 利用栈

void preOrder(TreeNode *root) {
    stack<TreeNode*> s;
    TreeNode *p=root;
    while(p||!s.empty()) {
        while(p) {
            printf("%d ",p->val);
            s.push(p);
            p=p->left;
        }
        if(!s.empty()) {
            p=s.top();
            s.pop();
            p=p->right;
        }
    } 
} 

先序非递归—利用数组模拟实现栈

void preOrder1(TreeNode *root) {
    TreeNode* a[100];
    int top=0;
    TreeNode *p=root;
    while(p||!top>=0) {
        while(p) {
            printf("%d ",p->val);
            a[top]=p;
            top++;
            p=p->left;
        }
        if(top>=0) {
            p=a[top];
            top--;
            p=p->right;
        }
    } 
} 

中序非递归 — 使用栈 《使用数组模拟栈和先序遍历一样》

 void InOrder(TreeNode *root) {
    TreeNode *p=root;
    stack<TreeNode*> s;
    while(p||!s.empty()) {
        while(p) {
            s.push(p);
            p=p->left;
        }
        if(!s.empty()) {
            p=s.top();
            s.pop();
            printf("%d ",p->val);
            p=p->right;
        }
    } 
}

非递归 后序遍历 — 使用数组

void postOrder(TreeNode *root) {
    struct{
        TreeNode *pp;
        int tag;
    }ss[100];
    int top=0;
    TreeNode *p=root;
    while(p || top>0) {
        while(p) {
            top++;
            ss[top].tag=0;
            ss[top].pp=p;
            p=p->left;
        }
        if(top>0) {
            if(ss[top].tag==0) { // 第一次出现在栈顶，根据后序遍历的规则，手写一个顺序就可以看出来
                ss[top].tag=1;
                p=ss[top].pp;
                p=p->right;
            } else {           // 第2次出现在栈顶
                p=ss[top].pp;
                printf("%d ",p->val);
                top--;
                p=NULL;
            }
        }
    } 
} 

非递归 后序遍历— 使用栈

void postOrder1(TreeNode *root) {
   int top=0;
   TreeNode *p=root;
   stack<TNode*> s;
   TNode *t;
   while(p||!s.empty()) {
       while(p) {
           TNode *node=new TNode;
           node->tag=0;
           node->pp=p;
           s.push(node);
           p=p->left;
       }
       if(!s.empty()) {
           t=s.top();
           s.pop();
           if(t->tag==0) {
               t->tag=1;
               s.push(t);
               p=t->pp->right;
           } else {
               printf("%d ",t->pp->val);
               p=NULL;
           }
       }
   } 
}

递归 后序遍历

void postOrder2(TreeNode *t) {
    if(t) {
        postOrder2(t->left);
        postOrder2(t->right);
        printf("%d ",t->val);
    }
  } 

层次遍历 — 使用数组模拟队列

void level(TreeNode *root) {
   int front=0,rear=0;
   TreeNode* a[100];
   TreeNode* p=root;
   if(root) {
       rear++;
       a[rear]=p;
   } else {
       return;
   }

   while(front!=rear) {
       front++;
       p=a[front];
       printf("%d ",p->val);
       if(p->left) {
           rear++;
           a[rear]=p->left;
       }
       if(p->right) {
           rear++;
           a[rear]=p->right;
       }
   } 
}

层次遍历 — 使用队列

void level1(TreeNode* root) {
   TreeNode* p=root;
   queue<TreeNode*> que;

   if(root) {
       que.push(p);
   } else {
       return;
   }

   while(!que.empty()) {
       p=que.front();
       printf("%d ",p->val);
       que.pop();
       if(p->left) {
           que.push(p->left);
       }
       if(p->right) {
           que.push(p->right);
       }
   }
} 
int main() {
   TreeNode *root=preCreate();
   preOrder(root);
   printf("\n");
   InOrder(root);
   printf("\n");
   postOrder(root);
   printf("\n");
   postOrder1(root);
   printf("\n");
   postOrder2(root);
   printf("\n");
   level(root);
   printf("\n");
   level1(root);
   return 0; 
}

转载：https://blog.csdn.net/weixin_43958091/article/details/102085972