[数据结构与算法]二叉树的实现及非递归遍历

二叉树的结构体定义

 struct TreeNode {  //二叉树结构体定义(来自leetcode)
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 };

二叉树的构建
这里采用层序遍历对二叉树进行插入操作(需要关注的点时，构建树时一般站在父节点的角度，防止丢失与根结点的联系，而遍历二叉树时可以站在当前结点去考虑问题。（这是本蒟蒻目前能达到的理解深度）

TreeNode* LevelOrder(TreeNode* p,int v) {  //采用层序遍历构建二叉树,在移动f结点时要小心不要让它丢失了和树的联系，尽量站在存在的父节点对左右孩子进行判断
     TreeNode* tmp = new TreeNode(v);  //建立新结点并赋值
     queue<TreeNode*> qt;  //层序遍历用的队列
     TreeNode* f = p;
         if (!p) {  //若根结点为空则直接赋值并返回
             p = tmp;
             cout << p->val << " ";
             return p;
         }
         else {   //若根结点不为空则入队
             qt.push(p);
             while (!qt.empty()) {  //当队伍不为空时循环
                 f = qt.front();  //对队头结点的左孩子和右孩子进行判断
                 qt.pop();
                 if (f->left) qt.push(f->left);  //左孩子和右孩子非空时入队，为空时则直接赋值退出循环
                 else if (!f->left) {
                     f->left = tmp; 
                     cout << f->left->val << " ";
                     break;
                 }
                 if(f->right) qt.push(f->right);
                 else
                 {
                     f->right = tmp;
                     cout << f->right->val << " ";
                     break;
                 }
             }
             return p;  //返回
         }
 }

非递归先序遍历
//遍历树时一般基于当前结点，对于先序遍历，若当前结点存在则访问，并指向它的左孩子；若当前结点不存在，弹出一个结点，并指向该结点的右孩子。

void PreOrder(TreeNode* node) {  //先序遍历
     stack<TreeNode*> s;
     TreeNode* p = node;
     while (p || !s.empty()) {  
         if (p) {
             cout << p->val<<" ";  
             s.push(p);
             p = p->left;
         }
         else{
             p = s.top();
             s.pop();
             p = p->right;
         }
     }
 }

非递归中序遍历

void InOrder(TreeNode* node) { //中序遍历
     stack<TreeNode*> s;
     TreeNode* p=node;
     while (p || !s.empty()) {
         if (p) {
             s.push(p);
             p = p->left;
         }
         else {
             p = s.top();
             s.pop();
             cout << p->val << " ";
             p = p->right;
         }
     }
 }

主函数如下：

int main() {
    TreeNode* node=NULL;

   for (int i = 0; i < 9; i++) {
        node=LevelOrder(node,i);  //层序遍历
    }

    PreOrder(node);  //先序遍历
    InOrder(node);  //中序遍历
    return 0;
}

后序遍历
以查找某结点的所有祖先为例

 struct myStack {  //后序遍历需要记录该结点的右子树是否访问过，因此自建一个栈；
     TreeNode* t;
     int tag;  //为1时表示右子树已经访问过了，此时可以出栈
 };

 void postOrder(TreeNode* node, int v) {
     myStack *s = new myStack[9];  //定义一个足够大的栈内存
     int top = 0;
     while (node || top > 0) {    //当结点非空或栈非空时循环
         while (node&&node->val!=v) {  //结点存在并且不是v时则沿着左子树入栈
             s[++top] = { node ,0};
             node = node->left;
         }
         if (node && node->val == v) {  //结点为v时，栈中所有元素为该结点的祖先结点；
             cout << "v的所有祖先：";
             for(int i=1;i<top;i++){  
                 cout << s[i].t->val << " ";
             }
             cout << endl;
             return;
         }
         //栈非空且栈顶tag为1时出栈，这里为1说明刚刚被访问过右子树，即可出栈（因为在入栈
         //的时候已经访问过（非v）了，所以无需再访问，直接出栈）
         while (top > 0 || s[top].tag == 1) {  
             top--;
         }
         if (top > 0) {
             s[top].tag = 1;
             node = s->t->right;
         }
     }
 }