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

AD1024
  • 58

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

回复
阅读 3.2k
3 个回答
青春不谢
  • 289
✓ 已被采纳

我猜题主想问的是如何建立深度为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);
    }
}
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));
}
小草11
  • 1
新手上路,请多包涵

我只是试试看。。。。

宣传栏