C/C++二叉树的创建及遍历：递归遍历、非递归遍历、层次遍历

淩亂°似流年 2022-04-24 09:20 264阅读 0赞

### 文章目录 ###

*  1 二叉树的主要性质
 *  2 二叉树的创建及遍历
 *   *  2.1 C语言实现
     *   *  2.1.1 递归遍历
         *  2.1.2 非递归遍历
         *   *  先序
             *  中序
             *  后序
         *  2.1.3 层次遍历
     *  2.2 C++实现

# 1 二叉树的主要性质 #

1.  一棵非空二叉树的第i层最多有 2 i 2^i 2i（i >= 1)个节点
2.  一棵深度为k的二叉树最多有 2 k 2^k 2k\-1个节点
3.  一棵非空二叉树，设叶子节点数为 n 0 n\_0 n0，度为2的节点数为 n 2 n\_2 n2，则 n 0 n\_0 n0 =  n 2 n\_2 n2 \+ 1
4.  设有n个节点的完全二叉树的深度为k，则 k = \[ l o g 2 n log\_2n log2n\] + 1 （\[ l o g 2 n log\_2n log2n\]表示不大于 l o g 2 n log\_2n log2n的最大整数）
5.

# 2 二叉树的创建及遍历 #

## 2.1 C语言实现 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]

### 2.1.1 递归遍历 ###

![在这里插入图片描述][20190420234147154.jpg]

### 2.1.2 非递归遍历 ###

#### 先序 ####

先序遍历的过程是首先访问根结点.然后先序遍历根的左子树，最后先序遍历根的右子树。对于根的左子树和右子树，遍历的过程相同。如果用非递归方法，就要在遍历左子树之前先保存右子树根结点的地址(指针)，以便在完成左子树的遍历之后取出右子树根结点的地址，再遍历这棵右子树。同样,在遍历左子树的左子树之前也要先保存左子树的右子树根结点的地址，以此类推。可以看出,对这些地址的保存和取出符合后进先出的原则,可设置一个辅助栈来保存这些右子树根结点的地址。为了方便编写算法,这个辅助栈保存所有经过的结点的指针,包括空的根指针和空的孩子指针。

#### 中序 ####

中序遍历的过程是首先中序遍历左子树,然后访问根结点，最后中序遍历根的右子树。对于根的左子树和右子树,遍历的过程相同。如果用非递归方法，就要在遍历左子树之前先保存根结点的地址(指针),以便在完成左子树的遍历之后取出根结点的地址访问根结点,然后再中序遍历右子树。同样,在中序遍历左子树的左子树之前也要先保存左子树的根结点地址，以此类推。可以看出,对这些地址的保存和取出符合后进先出的原则,可设置一个辅助栈来保存所经过的结点的地址。为了方便编写算法,栈中也保存空树的空指针。中序遍历二叉树的非递归算法如下:

#### 后序 ####

后序遍历的过程是首先后序遍历左子树，然后后序遍历根的右子树,最后访问根结点。如果用非递归方法，就要在遍历左子树之前先保存根结点的地址，以便在完成左子树遍历之后根据根结点的地址遍历右子树和访问根结点。对于根的左子树和根的右子树，遍历的过程相同。对这些地址的保存和使用符合后进先出的原则，可设置-一个辅助栈来保存所经过的结点的地址。因为后序遍历的特点是只有在遍历了左子树和右子树之后才能访问根结点,所以为了表明子树是否被遍历过,可再设置一个辅助变量。

### 2.1.3 层次遍历 ###

由层次遍历的定义可以推知，在进行层次遍历时，对一层结点访问完后再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问，这样一层一层地进行，先遇到的结点先访问,这与队列的操作原则比较吻合。因此，在进行层次遍历时可设置一个队列结构,遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从队头取出一个元素,每取一个元素执行下面两个操作:

(1)访问该元素所指的结点;  
(2)若该元素所指结点的左、右孩子指针非空，则将该元素所指结点的非空左孩子指针和右孩子指针顺序入队。

若队列非空,重复以上过程,当队列为空时,二叉树的层次遍历结束。在下面的层次遍历算法中,二叉树以二叉链表存储，一 维数组Queue\[ MAXNODE \]用于实现队列,变量front和rear分别表示当前队列首元素和队列尾元素在数组中的位置。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_5_color_FFFFFF_t_70]

#include <malloc.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef char elemType;
    typedef struct BiTNode { 
        elemType data;
        struct BiTNode *lchild, *rchild;
    } BiTNode, *BiTree;
    BiTree createBiTree(); // 先序输入节点的值，构造二叉树
    void PreOrderTraverseNonRec(BiTree T);  // 先序非递归遍历二叉树
    void InOrderTraverseNonRec(BiTree T);   // 中序非递归遍历二叉树
    void PostOrderTraverseNonRec(BiTree T); // 后序非递归遍历二叉树
    void LevelOrderTraverse(BiTree T); // 层次遍历二叉树（从上到下，每层从左到右）
    
    #define STACK_INIT_SIZE 100
    #define STACKINCREMENT 10
    typedef struct StackNode { 
        BiTNode **top;
        BiTNode **base;
        int size;
    } Stack;
    Stack *InitStack();             // 初始化空栈
    int isEmpty(Stack *S);          // 判断栈空
    BiTNode *GetTop(Stack *S);      // 取栈顶数据
    int push(Stack *S, BiTNode *p); // 入栈
    BiTNode *pop(Stack *S);         // 出栈
    
    #define MAXSIZE 100
    typedef struct { 
        BiTNode *data[MAXSIZE]; // 指针数组，数组中的每一个元素指向BiTNode类型的节点
        int front, rear; /* front:指向队列中第一个元素 rear:指向队列中最后一个元素下一位置 */
    } Queue;
    
    int main(void)
    { 
        BiTree root;
    
        printf("请按先序顺序输入节点值，输入‘#’代表节点为空：\n");
        root = createBiTree();
    
        printf("先序非递归：");
        PreOrderTraverseNonRec(root);
        printf("\n");
        printf("中序非递归：");
        InOrderTraverseNonRec(root);
        printf("\n");
        printf("后序非递归：");
        PostOrderTraverseNonRec(root);
        printf("\n");
        printf("按层次遍历：");
        LevelOrderTraverse(root);
        printf("\n");
    
        return 0;
    }
    
    // 先序输入节点的值，构造二叉树
    BiTree createBiTree()
    { 
        char ch;
        BiTree T;
    
        if ((ch = getchar()) == '#')
            T = NULL;
        else { 
            T = (BiTNode *)malloc(sizeof(BiTNode));
            T->data = ch;
            T->lchild = createBiTree();
            T->rchild = createBiTree();
        }
    
        return T;
    }
    // 输出元素x
    void visit(elemType x) {  printf("%c, ", x); }
    Stack *InitStack()
    { 
        Stack *S;
    
        S = (Stack *)malloc(sizeof(Stack));
        S->base = (BiTNode **)calloc(STACK_INIT_SIZE, sizeof(BiTNode *));
        S->top = S->base;
        S->size = STACK_INIT_SIZE;
    
        return S;
    }
    // 取栈顶数据
    BiTNode *GetTop(Stack *S)
    { 
        BiTNode *p = NULL;
        if (S->top == S->base)
            return NULL;
        p = *(S->top - 1);
    
        return p;
    }
    // 入栈
    int push(Stack *S, BiTNode *p)
    { 
        if (S->top - S->base >= S->size) { 
            S->base = (BiTNode **)realloc(
                S->base, (STACKINCREMENT + STACK_INIT_SIZE) * sizeof(BiTNode *));
            if (!S->base) { 
                printf("入栈失败！\n");
                return 0;
            }
            S->top = S->base + S->size;
            S->size += STACKINCREMENT;
        }
        *S->top++ = p;
    
        return 1;
    }
    // 出栈
    BiTNode *pop(Stack *S)
    { 
        if (S->top == S->base) { 
            printf("出栈失败！\n");
            return NULL;
        }
        return *--S->top;
    }
    // 判断栈空
    int isEmpty(Stack *S) {  return S->top == S->base; }
    
    // 先序非递归遍历二叉树
    void PreOrderTraverseNonRec(BiTree T)
    { 
        Stack *S = InitStack();
        BiTNode *p;
    
        push(S, T);
        while (!isEmpty(S)) { 
            p = GetTop(S);
            while (p != NULL) //向左走到尽头
            { 
                visit(p->data);
                push(S, p->lchild);
                p = GetTop(S);
            }
    
            /* while (p = GetTop(S))//向左走到尽头 { visit(p->data); push(S, p->lchild); } */
    
            p = pop(S); //空指针退栈
            if (!isEmpty(S)) { 
                p = pop(S);
                push(S, p->rchild); //向右一步
            }
        }
    }
    // 中序非递归遍历二叉树
    void InOrderTraverseNonRec(BiTree T)
    { 
        Stack *S = InitStack();
        BiTNode *p;
    
        push(S, T);
        while (!isEmpty(S)) { 
            p = GetTop(S);
            while (p != NULL) //向左走到尽头
            { 
                push(S, p->lchild);
                p = GetTop(S);
            }
    
            pop(S); //空指针退栈
            if (!isEmpty(S)) { 
                p = pop(S);
                visit(p->data);
                push(S, p->rchild);
            }
        }
    }
    // 后序非递归遍历二叉树
    void PostOrderTraverseNonRec(BiTree T)
    { 
        Stack *S = InitStack();
        BiTNode *p = T, *q; // q指向最近被访问过的节点，用作标志
    
        do { 
            while (p) //向左走到尽头
            { 
                push(S, p);
                p = p->lchild;
            }
            q = NULL;
            while (!isEmpty(S)) { 
                p = GetTop(S);
                if ((p->rchild == NULL) ||
                    q == p->rchild) {  //右子树为空或已经访问过
                    visit(p->data);
                    q = p;
                    pop(S);
                }
                else // 右子树非空且未被遍历
                { 
                    p = p->rchild; //向右一步
                    break;
                }
            }
        } while (!isEmpty(S));
    }
    // 层次遍历二叉树（从上到下，每层从左到右）
    void LevelOrderTraverse(BiTree T)
    { 
        Queue Q;
        BiTNode *temp = NULL;
    
        Q.front = Q.rear = 0;
        if (T) { 
            Q.data[Q.rear] = T;
            Q.rear = (Q.rear + 1) % MAXSIZE;
            while (Q.front != Q.rear) { 
                temp = Q.data[Q.front];
                visit(temp->data);
                Q.front = (Q.front + 1) % MAXSIZE;
    
                if (temp->lchild) { 
                    Q.data[Q.rear] = temp->lchild;
                    Q.rear = (Q.rear + 1) % MAXSIZE;
                }
                if (temp->rchild) { 
                    Q.data[Q.rear] = temp->rchild;
                    Q.rear = (Q.rear + 1) % MAXSIZE;
                }
            }
        }
    }

![在这里插入图片描述][20190420223520983.jpg]

## 2.2 C++实现 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70_pic_center]

#include <iostream>
    #include <queue>
    #include <stack>
    #include <vector>
    using namespace std;
    
    #define nil INT_MIN
    
    // 二叉树结点定义
    struct TreeNode { 
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode() : val(0), left(nullptr), right(nullptr) { }
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) { }
        TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) { }
    };
    
    // 创建二叉树
    TreeNode *createBinaryTree(vector<int> &vals, int n, int index)
    { 
        TreeNode *node = nullptr;
        if (index < n && vals[index] != nil) { 
            node = new TreeNode(vals[index]);
            node->left = createBinaryTree(vals, n, 2 * index + 1);
            node->right = createBinaryTree(vals, n, 2 * index + 2);
        }
        return node;
    }
    
    // 打印一个结点信息
    void visit(const TreeNode *node) {  cout << node->val << ' '; }
    
    // 递归遍历
    void preOrder(TreeNode *root, void (*visit)(const TreeNode *node))
    { 
        if (root) { 
            visit(root);
            preOrder(root->left, visit);
            preOrder(root->right, visit);
        }
    }
    void inOrder(TreeNode *root, void (*visit)(const TreeNode *node))
    { 
        if (root) { 
            inOrder(root->left, visit);
            visit(root);
            inOrder(root->right, visit);
        }
    }
    void postOrder(TreeNode *root, void (*visit)(const TreeNode *node))
    { 
        if (root) { 
            postOrder(root->left, visit);
            postOrder(root->right, visit);
            visit(root);
        }
    }
    
    // 非递归遍历
    void preOrderNonRecursive(TreeNode *root, void (*visit)(const TreeNode *node))
    { 
        stack<TreeNode *> stk;
        TreeNode *p = root;
        while (p || !stk.empty()) { 
        	// 向左走到尽头
            while (p) { 
                visit(p);
                stk.push(p);
                p = p->left;
            }
            p = stk.top();
            stk.pop();
            p = p->right;
        }
    }
    void inOrderNonRecursive(TreeNode *root, void (*visit)(const TreeNode *node))
    { 
        stack<TreeNode *> stk;
        TreeNode *p = root;
        while (p || !stk.empty()) { 
        	// 向左走到尽头
            while (p) { 
                stk.push(p);
                p = p->left;
            }
            p = stk.top();
            stk.pop();
            visit(p);
            p = p->right;
        }
    }
    /* * 后序：左子树 右子树 根结点 * 思想：1 沿着根的左孩子，依次入栈，直到左孩子为空 * 2 读栈顶元素，若其右孩子不空且未被访问过，将右子树执行步骤 1； * 否则，栈顶元素出栈并访问 */
    void postOrderNonRecursive(TreeNode *root, void (*visit)(const TreeNode *node))
    { 
        stack<TreeNode *> stk;
        // p 为当前访问的结点，rencent 为最近访问过的结点
        TreeNode *p = root, *recent = nullptr;
        while (p || !stk.empty()) { 
            // 走到最左边
            if (p) { 
                stk.push(p);
                p = p->left;
            }
            // 向右
            else { 
                p = stk.top();
                // 若右子树存在且未被访问
                if (p->right && p->right != recent) { 
                    p = p->right;
                    stk.push(p);
                    p = p->left;
                }
                // 出栈并访问
                else { 
                    stk.pop();
                    visit(p);
                    recent = p;
                    // 每次出栈访问完一个结点就相当于遍历完以该结点为根的子树，需将 p 置空
                    p = nullptr;
                }
            }
        }
    }
    
    // 层次遍历
    void levelOrder(TreeNode *root, void (*visit)(const TreeNode *node))
    { 
        queue<TreeNode *> q;
        q.push(root);
        while (!q.empty()) { 
            TreeNode *node = q.front();
            q.pop();
            visit(node);
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }
    int main(int argc, char const *argv[])
    { 
        vector<int> vals{ 5, 6, 9, 3, nil, 44, 1, 11, 22};
        TreeNode *root = createBinaryTree(vals, vals.size(), 0);
        cout << "1、递归遍历\n";
        cout << "先序：";
        preOrder(root, visit);
        cout << endl;
        cout << "中序：";
        inOrder(root, visit);
        cout << endl;
        cout << "后序：";
        postOrder(root, visit);
        cout << endl << endl;
    
        cout << "2、非递归遍历\n";
        cout << "先序：";
        preOrderNonRecursive(root, visit);
        cout << endl;
        cout << "中序：";
        inOrderNonRecursive(root, visit);
        cout << endl;
        cout << "后序：";
        postOrderNonRecursive(root, visit);
        cout << endl << endl;
    
        cout << "3、层次遍历\n";
        cout << "层次遍历：";
        levelOrder(root, visit);
        cout << endl << endl;
    
        return 0;
    }

1、递归遍历
    先序：5 6 3 11 22 9 44 1
    中序：11 3 22 6 5 44 9 1
    后序：11 22 3 6 44 1 9 5
    
    2、非递归遍历
    先序：5 6 3 11 22 9 44 1
    中序：11 3 22 6 5 44 9 1
    后序：11 22 3 6 44 1 9 5
    
    3、层次遍历
    层次遍历：5 6 9 3 44 1 11 22

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220217/d70c71727ca14152b056063ff4f5f558.png
[20190420234147154.jpg]: /images/20220217/ea0cff9618e8462091ed2cba3468ba83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_5_color_FFFFFF_t_70]: /images/20220217/22d4bb80d7394cc78275a89193f41295.png
[20190420223520983.jpg]: /images/20220217/f605694c600a49e099543278c3afd1ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20220217/48a95bfc817d4bf6b5c00c51f2a32f10.png