如何输入n建立深度为n的完全二叉树(C实现)

Question

如题，求解如何建立(c和c++均可)。先谢谢大家了！orz

Answer 1

我猜题主想问的是如何建立深度为n的满二叉树吧，因为深度为n的完全二叉树的结点数是不固定的啊，只给一个深度n，我怎么知道你有多少结点。深度为n的完全二叉树的结点数范围为$2^{n-1}$ to $2^{n}-1$ （为毛latex图片显示不出来，显示的是语法串）。题主先把概念搞清楚。
这段代码给你参考一下，是c++写的，稍微改一下就行了。利用层序遍历的思路，用到了stl的一个队列。

//num是结点数，而不是树高
void CreateTreeLevel(TreeNode* &rt, int num)//
{
    queue<TreeNode*> q;
    rt = new TreeNode(1);
    TreeNode* cur = rt;
    q.push(cur);
    for(int i = 2; i <= num;)
    {
        cur = q.front();
        q.pop();
        cur->left = new TreeNode(i++);
        q.push(cur->left);
        if(i >= num)
            break;
        cur->right = new TreeNode(i++);
        q.push(cur->right);
    }
}

Answer 2

Struct Node{ Node(Node*_l, Node*_r):left(_l), right(_r){} Node* left, *right;};

Node* build(int depth){
    if (depth ==0) return Null;
    return new Node(build(depth-1), build(depth-1));
}

Answer 3

我只是试试看。。。。