二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧。
采用递归方式
下面是代码内容:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
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;
}
|
采用非递归方式
采用非递归方式计算二叉树的宽度需要借助于队列。代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
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; //返回计算所得的最大的二叉树的宽度。
}
|
总结:
不管采用哪种方式,实际上还是利用了对二叉树的遍历的特点来进行的。
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
原文链接:http://blog.csdn.net/marksinoberg/article/details/50464078