【简介】

树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：

或者

// 二叉树节点结构
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};

【二叉树的创建】

通过读入一个字符串，建立二叉树的算法如下：

或者

// 1.创建二叉树
void CreateTree(TreeNode* &root){
    int val;
    //按先序次序输入二叉树中结点的值,‘-1’表示空树
    cin>>val;
    // 空节点
    if(val == -1){
        root = nullptr;
        return;
    }//if
    root = new TreeNode(val);
    //构造左子树
    CreateTree(root->left);
    //构造右子树
    CreateTree(root->right);
}

层次建立二叉树：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 创建二叉树
TreeNode* CreateTreeByLevel(vector<char> num){
    int len = num.size();
    if(len == 0){
        return NULL;
    }//if
    queue<TreeNode*> queue;
    int index = 0;
    // 创建根节点
    TreeNode *root = new TreeNode(num[index++]);
    // 入队列
    queue.push(root);
    TreeNode *p = NULL;
    while(!queue.empty() && index < len){
        // 出队列
        p = queue.front();
        queue.pop();
        // 左节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *leftNode = new TreeNode(num[index]);
            p->left = leftNode;
            queue.push(leftNode);
        }
        index++;
        // 右节点
        if(index < len && num[index] != -1){
            // 如果不空创建一个节点
            TreeNode *rightNode = new TreeNode(num[index]);
            p->right = rightNode;
            queue.push(rightNode);
        }
        index++;
    }//while
    return root;
}

-1代表NULL

创建如上二叉树输入：

15 11 20 8 14 -1 -1 -1 -1 13 -1

【二叉树的遍历】

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

【递归算法】

【非递归算法】

【先序遍历】

【思路】：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。

// 先序遍历
void PreOrder(TreeNode* root){
    if(root == NULL){
        return;
    }
    stack<TreeNode*> stack;
    stack.push(root);
    TreeNode *p = NULL;
    while(!stack.empty()){
        p = stack.top();
        stack.pop();
        cout<<p->val<<endl;
        // 右子节点不空压入栈中
        if(p->right){
            stack.push(p->right);
        }
        // 左子节点不空压入栈中
        if(p->left){
            stack.push(p->left);
        }
    }//while
}

【中序遍历】

【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
         先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

【后序遍历】

【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

或者

    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> result;
        if(root == nullptr){
            return result;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.insert(result.begin(),node->val);
            // 左子树
            if(node->left){
                s.push(node->left);
            }//if
            // 右子树
            if(node->right){
                s.push(node->right);
            }//if
        }//while
        return result;
    }

【层次遍历】

【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。

【测试】

输入：（先序）

15 11 8 -1 -1 14 13 -1 -1 -1 20 -1 -1

输出：

代码一：

    /*-------------------------------------
    *   日期：2015-03-25
    *   作者：SJF0115
    *   题目: 二叉树各种遍历
    *   来源：
    *   博客：
    ------------------------------------*/
    #include <iostream>
    #include <vector>
    #include <stack>
    #include <queue>
    using namespace std;

    // 二叉树节点结构
    struct TreeNode{
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x):val(x),left(nullptr),right(nullptr){}
    };
    // 1.创建二叉树
    void CreateTree(TreeNode* &root){
        int val;
        //按先序次序输入二叉树中结点的值,‘-1’表示空树
        cin>>val;
        // 空节点
        if(val == -1){
            root = nullptr;
            return;
        }//if
        root = new TreeNode(val);
        //构造左子树
        CreateTree(root->left);
        //构造右子树
        CreateTree(root->right);
    }
    // 2.1 递归先序遍历
    void PreOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        result.push_back(root->val);
        // 左子树
        PreOrder(root->left,result);
        // 右子树
        PreOrder(root->right,result);
    }
    // 2.2 非递归先序遍历
    void PreOrder2(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.push_back(node->val);
            // 右子树
            if(node->right){
                s.push(node->right);
            }//if
            // 左子树
            if(node->left){
                s.push(node->left);
            }//if
        }//while
    }
    // 3.1 递归中序遍历
    void InOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        // 左子树
        InOrder(root->left,result);
        result.push_back(root->val);
        // 右子树
        InOrder(root->right,result);
    }
    // 3.2 非递归中序遍历
    void InOrder2(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        TreeNode *node = root;
        while(node != nullptr || !s.empty()){
            // 左子树
            if(node != nullptr){
                s.push(node);
                node = node->left;
            }//if
            // 右子树
            else{
                node = s.top();
                s.pop();
                result.push_back(node->val);
                node = node->right;
            }
        }//while
    }
    // 4.1 递归后序遍历
    void PostOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        // 左子树
        PostOrder(root->left,result);
        // 右子树
        PostOrder(root->right,result);
        result.push_back(root->val);
    }
    // 4.2 非递归后序遍历
    void PostOrder2(TreeNode *root,vector<int> &result) {
        if(root == nullptr){
            return;
        }//if
        stack<TreeNode*> s;
        s.push(root);
        TreeNode *node;
        while(!s.empty()){
            node = s.top();
            s.pop();
            result.insert(result.begin(),node->val);
            // 左子树
            if(node->left){
                s.push(node->left);
            }//if
            // 右子树
            if(node->right){
                s.push(node->right);
            }//if
        }//while
    }
    // 5 层次遍历
    void LevelOrder(TreeNode* root,vector<int> &result){
        if(root == nullptr){
            return;
        }//if
        queue<TreeNode*> queue;
        queue.push(root);
        TreeNode *node;
        while(!queue.empty()){
            node = queue.front();
            queue.pop();
            result.push_back(node->val);
            // 左子树
            if(node->left){
                queue.push(node->left);
            }//if
            // 右子树
            if(node->right){
                queue.push(node->right);
            }//if
        }//while
    }
    // 输出结果
    void Print(vector<int> result){
        int size = result.size();
        for(int i = 0;i < size;++i){
            cout<<result[i]<<" ";
        }//for
        cout<<endl;
    }
    int main(){
        freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin);
        TreeNode* root = nullptr;
        vector<int> result;
        // 创建二叉树
        cout<<"1. 创建二叉树"<<endl;
        CreateTree(root);
        cout<<"-----------------------------"<<endl;

        cout<<"2.1 递归先序遍历"<<endl;
        PreOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"2.2 非递归先序遍历"<<endl;
        PreOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"3.1 递归中序遍历"<<endl;
        InOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"3.2 非递归中序遍历"<<endl;
        InOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"4.1 递归后序遍历"<<endl;
        PostOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"4.2 非递归后序遍历"<<endl;
        PostOrder2(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;

        cout<<"5 层次遍历"<<endl;
        LevelOrder(root,result);
        Print(result);
        result.clear();
        cout<<"-----------------------------"<<endl;
        return 0;
    }

测试用例：

输入：

ABC##DE#G##F###

输出：

代码二：