weixin_52463018
2021-11-15 18:49
采纳率: 100%
浏览 24

数据结构(c++语言)求二叉树的宽度

img

图片转代码服务由CSDN问答提供 功能建议

        二叉树的宽度
()先创建一颗二叉树
(2)用层次遍历的方法遍历整棵二叉树,在遍历的时
候记录下每层的节点的个数,具有最大的元素个数
的层的节点数量就是这棵树的宽度。
  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

  • 最佳回答

    参考:

    #include<iostream>
    #include<stdlib.h> 
    #include<deque>  //插入标准库中的头文件
    using namespace std;
     
    typedef struct treenode
    {
        char data;
        treenode *right;
        treenode *left;
    }*Node;
     
    //创建二叉树
    void creat_tree(treenode *&rt)
    {
        char ch;
        ch = getchar();
        if ('#' == ch) {
            rt = NULL;
        } else {
            rt = new treenode;
            rt->data = ch;
            creat_tree(rt->left);        //构造左子树
            creat_tree(rt->right);    //构造右子树    
        }
    }
     
    //层次遍历
    void Complete_binary_tree(treenode *&root,int &height,int &width) { //在这里采用层次遍历的方法
        if (root == NULL) { //空树满足条件
            height = 0;
            width = 0;
        }
     
        int max = -1; height = 0; width = 0;
        Node last = root;
        deque <Node> c;  //定义一个空的队列
        c.push_back(root);
        while (!c.empty()) {  //如果队列不为空
            Node temp = c.front();  //返回队列的第一个元素
            width++;  //宽度加1
            if (temp) {  //如果是非空结点
                cout << temp->data << " ";
                c.pop_front();  //出队列
     
                if (temp->left) {
                    c.push_back(temp->left);  //左孩子
                }
                if (temp->right) {
                    c.push_back(temp->right); //右孩子
                }
     
                if (temp == last ) { //访问到最右边的非空节点
                    if (!c.empty()) {
                        last = c.back();  //重新赋值
                    }
                    height++;  //高度加1
                    //接下来判断宽度
                    if (width >= max) {
                        max = width;
                        width = 0;  //重新计数
                    }
                }
            }
        }
        width = max;
    }
     
    int main() {
        treenode *root = NULL;
        int height, width;  //表示高度和最大宽度
        cout << "请输入二叉树,空值以#代表:" << endl;
        creat_tree(root);        //创建二叉树
        Complete_binary_tree(root,height,width);
        cout << "高度为:" << height << endl;
        cout<<"最大宽度为:" << width << endl;
        system("pause");
        return 0;
    }
    
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题