数据结构（c＋＋语言）求二叉树的宽度

Question

Answer 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;
}