计算二叉树的宽度的两种方式

简介: 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧。采用递归方式下面是代码内容:int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高...

二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧。


采用递归方式


下面是代码内容:

int GetMaxWidth(BinaryTree pointer){
    int width[10];//加入这棵树的最大高度不超过10
    int maxWidth=0;
    int floor=1;
    if(pointer){
        if(floor==1){//如果访问的是根节点的话,第一层节点++;
            width[floor]++;
            floor++;
            if(pointer->leftChild)
                width[floor]++;
            if(pointer->rightChild)
                width[floor]++;
        }else{
            floor++;
            if(pointer->leftChild)
                width[floor]++;
            if(pointer->rightChild)
                width[floor]++;
        }
        if(maxWidth<width[floor])
            maxWidth=width[floor];
        GetMaxWidth(pointer->leftChild);
        floor--;//记得退回一层,否则会出错。因为已经Get过了,所以要及时的返回。
        GetMaxWidth(pointer->rightChild);
    }
    return maxWidth;
}

采用非递归方式


采用非递归方式计算二叉树的宽度需要借助于队列。代码如下:

int GetMaxWidth(BinaryTree pointer){
    if(pointer==null){
        return 0;
    }
    Queue<BinaryTreeNode> queue=new ArrayDeque<BinaryTreeNode>();
    int maxWidth=1;//最大宽度
    queue.add(pointer);
    while(true){
        int size=queue.size();//计算当前层的节点的个数
        if(size==0){
            break;
        }
        while(size>0){//如果当前层还有节点就进行下去
            BinaryTreeNode node=queue.poll();
            size--;
            if(node->leftChild)
                queue.add(node->leftChild);//当前节点的左子树入队
            if(node->rightChild)
                queue.add(node->rightChild);//当前节点的右子树入队
            maxWidth=Math.max(size,queue.size());
        }
    }
    return maxWidth;//返回计算所得的最大的二叉树的宽度。
}

总结:
不管采用哪种方式,实际上还是利用了对二叉树的遍历的特点来进行的。

目录
相关文章
|
5月前
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
数据结构学习记录——平衡二叉树的调整(基本介绍、右单旋、左单旋、左右双旋、右左双旋、平衡因子的计算)
70 1
|
人工智能 BI
LeetCode-310 最小高度树
LeetCode-310 最小高度树
二叉树最大宽度
二叉树最大宽度
64 0
给定三个顶点的坐标使用程序计算三角形
给定三个顶点的坐标使用程序计算三角形
63 0
LeetCode 1637. 两点之间不包含任何点的最宽垂直面积
给你 n 个二维平面上的点 points ,其中 points[i] = [xi, yi] ,请你返回两点之间内部不包含任何点的 最宽垂直面积 的宽度。
89 0
|
C++
C++ 自定义二叉树并输出二叉树图形
C++ 自定义二叉树并输出二叉树图形
260 2
|
算法
判断三角形的性质(直角或等腰)简便算法
判断三角形的性质(直角或等腰)简便算法
135 0
|
前端开发 Serverless
两个盒子,左边固定宽,右边自适应,你能想到几种方法?
最近不是又要秋招了吗? 有的小伙伴就说了,你的面试专栏可是鸽了有一段时间了奥,再不更新我就取关拉! 这这这,我这不来更新了吗,三个招聘季节,更新了三篇,**合情,合理~** ~~再也不画饼了~~
|
机器学习/深度学习 人工智能 BI
310. 最小高度树 : 树形 DP 模板题
310. 最小高度树 : 树形 DP 模板题