二叉树的初始化、前序、中序、后序遍历

问题：

给定二叉树的初始化数据，怎样动态建立一个二叉树呢？

比如我们给定这样的一组数据：{ 1, 2, 3, 4, 0, 5, 6, 0, 7 }（假设0代表空），则我们构建的二叉树是这样的:

 1
/ \

2 3
/ /
4 5 6

7
思路分析：

我们可以使用一个队列，队首出一个元素，队未进两个元素，而这两个元素正好是这个队首元素的左右节点。

头文件 （TreeNode.h）

#pragma once
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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


//初始化一个二叉树
TreeNode* initBTree(int elements[], int size);

//树的前序遍历
void preOrder(TreeNode *root, vector<int> &result);

//树的中序遍历
void inOrder(TreeNode *root, vector<int> &result);

//树的后序遍历
void postOrder(TreeNode *root, vector<int> &result);

/*树的深度*/
int btreedepth(TreeNode *bt);

/*树的节点数*/
int btreecount(TreeNode *bt)

//vector的遍历
void traverse(vector<int> nums);

函数（TreeNode.cpp）

#include "TreeNode.h"

/*初始化一个二叉树*/
TreeNode* initBTree(int elements[], int size)
{
    if (size < 1)
    {
        return NULL;
    }
    //动态申请size大小的指针数组
    TreeNode **nodes = new TreeNode*[size];
    //将int数据转换为TreeNode节点
    for (int i = 0; i < size; i++)
    {
        if (elements[i] == 0)
        {
            nodes[i] = NULL;
        }
        else
        {
            nodes[i] = new TreeNode(elements[i]);
        }
    }
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(nodes[0]);

    TreeNode *node;
    int index = 1;
    while (index < size)
    {
        node = nodeQueue.front();
        nodeQueue.pop();
        nodeQueue.push(nodes[index++]);
        node->left = nodeQueue.back();
        nodeQueue.push(nodes[index++]);
        node->right = nodeQueue.back();
    }
    return nodes[0];
}

/*树的前序遍历*/
void preOrder(TreeNode *root, vector<int> &result)
{
    if (root)
    {
        result.push_back(root->val);
        preOrder(root->left, result);
        preOrder(root->right, result);
    }
}

/*树的中序遍历*/
void inOrder(TreeNode *root, vector<int> &result)
{
    if (root)
    {
        inOrder(root->left, result);
        result.push_back(root->val);
        inOrder(root->right, result);
    }
}

/*树的后序遍历*/
void postOrder(TreeNode *root, vector<int> &result)
{
    if (root)
    {
        postOrder(root->left, result);
        postOrder(root->right, result);
        result.push_back(root->val);
    }
}

/*树的深度*/
int btreedepth(TreeNode *bt)
{
    if (bt == NULL)
        return 0;
    else
    {
        int dep1 = btreedepth(bt->left);
        int dep2 = btreedepth(bt->right);
        if (dep1>dep2)
            return dep1 + 1;
        else
            return dep2 + 1;
    }
}

/*树的节点数*/
int btreecount(TreeNode *bt)
{
    if (bt == NULL)
        return 0;
    else
        return btreecount(bt->left) + btreecount(bt->right) + 1;

}

/*树的叶子树*/
int btreeleafcount(TreeNode *bt)
{
    if (bt == NULL)
        return 0;
    else if (bt->left == NULL&&bt->right == NULL)
        return 1;
    else return btreeleafcount(bt->left) + btreeleafcount(bt->right);
}

/*输出树*/
void printbtree(TreeNode *bt)
{
    if (bt == NULL)
        return;
    else
    {
        cout << bt->val;
        if (bt->left != NULL || bt->right != NULL)
        {
            cout << '(';
            printbtree(bt->left);
            if (bt->right != NULL)
                cout << ',';
            printbtree(bt->right);
            cout << ')';
        }
    }
}


/*Vector遍历*/
void traverse(vector<int> nums)
{
    vector<int>::size_type size = nums.size();
    for (size_t i = 0; i < size; i++)
    {
        cout << nums[i] << ' ';
    }
    cout << endl;
}