The Java language describes the depth and width of binary trees
- 2020-11-25 07:14:32
- OfStack
Explanation:
2. The depth of the tree: The nodes passing from the root node to the leaf node successively (including root and leaf node) form one path of the tree, and the length of the longest path is the depth of the tree.
The width of a two-tree: There are a fixed number of nodes in each layer of a two-tree. The number of nodes in the layer with the most nodes is called the width of the two-tree.
Idea: Recursive implementation.
1. Each node can be regarded as the root node
2. The depth of the root node (any one node) is equal to the maximum depth +1 of its left or right subtree
3. Start the traversal from the root node. If it traverses to the leaf node, the depth is 0
//2 The depth of the tree
public static int Depth(node root){
if(root == null){
return 0;
}
int dl = Depth(root.leftchild);
int dr = Depth(root.rightchild);
return dl>dr? dl+1:dr+1;
}
2. The width of 2 cross trees
Idea: Add 1 counter after the sequence traversal, and record the number of nodes in each layer
1. The number of nodes at the first layer is recorded at each queue emergence, which is Size() of the queue.
2. At the end of each layer traversal, compare the maximum width with the number of nodes in the current layer and record the maximum value
public static int Width(node root) {
if(root == null)
return 0;
Queue<node> q = new LinkedList<node>();
q.add(root);
int width = 1;
// Maximum width
int len = 1;
// Number of nodes in current layer
while(q.size()>0){
while(len-->0){
node node = q.poll();
if(node.leftchild != null){
q.add(node.leftchild);
}
if(node.rightchild != null){
q.add(node.rightchild);
}
}
len = q.size();
// Record at the end of each layer loop 1 Number of nodes in the layer
width = width>q.size() ? width : q.size();
}
return width;
}
conclusion
That's it for the Java language to describe the depth and width of a 2-tree. If there is any deficiency, please let me know. Thank you for your support!