二叉树的高度和深度
In this tutorial, we will learn how to find height and depth of binary tree with program implementation in C++. It is one of the most commonly used non-linear data structures. We will learn about:
在本教程中，我们将学习如何使用C ++中的程序实现来查找二叉树的高度和深度。 它是最常用的非线性数据结构之一。 我们将了解：
- What is the height of a binary tree? 二叉树的高度是多少？
- Algorithm and implementation for finding height of Binary tree 查找二叉树高度的算法和实现
- What is the depth of a binary tree? 二叉树的深度是多少？
- Algorithm and implementation for finding depth of Binary tree 查找二叉树深度的算法和实现
Many times, people are confused between Depth and Height of Binary tree. It is because the depth of binary tree is always equal to the height of binary tree but they are not the same and using the terms interchangeably is not correct. So, it is important for us to understand the difference between the Height and Depth of Binary tree.
很多时候，人们对二叉树的深度和高度感到困惑。 这是因为二叉树的深度始终等于二叉树的高度，但是它们不相同，并且互换使用这些术语是不正确的。 因此，重要的是要了解二叉树的高度和深度之间的差异。
二叉树的高度 (Height of Binary Tree)
“Dream as high as the sky and as Deep as the ocean.”
“梦象天空一样深，象海洋一样深。”
As the quote on top says sky is what we should see while calculating height. The height of binary tree is the measure of length of the tree in the vertical direction. It is measured in upward direction that is from child to parent. The leaf nodes have height of 0 as there is no nodes below them. The height of the root node of the binary tree is the height of the whole tree. The height of a particular node is the number of edges on the longest path from that node to a leaf node.
正如最上面的报价所说，天空是计算高度时应该看到的。 二叉树的高度是垂直方向上树的长度的量度。 它是从孩子到父母的向上方向测量的。 叶节点的高度为0，因为它们下面没有节点。 二叉树的根节点的高度是整个树的高度。 特定节点的高度是从该节点到叶节点的最长路径上的边数。
Finding the Height of Binary Tree
求二叉树的高度
To find the height of the binary tree we will recursively calculate the height of the left and right subtree of a node. To find the heights of left and right subtrees we use in-order traversal. After finding the height of both left and right subtree we will store the height of the subtree which has maximum value and add 1 to it to include the current level of tree.
为了找到二叉树的高度，我们将递归计算节点左右子树的高度。 为了找到左和右子树的高度，我们使用有序遍历。 找到左右子树的高度后，我们将存储具有最大值的子树的高度，并向其添加1以包括当前树的级别。
算法 (Algorithm)
|
1
2
3
4
5
6
7
|
FindHeight( Node root)
If root == NULL
return 0
else
int leftH = FindHeight ( root->left )
int rightH = FindHeight(root->right )
return max( leftH, rightH )+1
|
|
1
2
3
4
5
6
7
|
FindHeight ( Node root )
If root == NULL
return 0
else
int leftH = FindHeight ( root -> left )
int rightH = FindHeight ( root -> right )
return max ( leftH , rightH ) + 1
|
用C ++程序查找二叉树的高度 (C++ Program to Find Height of Binary Tree)
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <bits/stdc++.h>
using namespace std;
/* structure of a binary tree */
struct node
{
int data; // to store the value of a node in tree
node* left; // pointer to the left child
node* right; // pointer to the right child
};
/* function to find the maximum height of binary tree */
int FindHeight(node* node)
{
if (node == NULL) // when the subtree is empty
return 0;
else
{
int leftH,rightH;
/*find the height of left subtree */
leftH = FindHeight(node->left);
/*find the height of right subtree */
rightH = FindHeight(node->right);
/* return the maximum height */
if (leftH > rightH)
return(leftH + 1);
else
return(rightH + 1);
}
}
/* function to get new node for the tree */
node* getNode(int data)
{
node* newNode = new node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return(newNode);
}
int main()
{
/* creating the binary tree */
node *root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
cout << "The Height of the binary tree is " << FindHeight(root);
return 0;
}
|
Output:
输出：
The Height of the binary tree is 3
二叉树的高度为3
二叉树的深度 (Depth of Binary Tree)
Think of ocean and the quote above while calculating depth. The depth is a measure of how far a node is from the root of the tree. The depth of the ocean is calculated with respect to the sea level similarly the depth of any node in binary tree is measured with respect to the root node of the tree. The depth of a particular node in binary tree is the number of edges from the root node to that node. The depth of binary tree is the depth of the deepest node (leaf node).
在计算深度时，请考虑一下海洋和上面的报价。 深度是节点距树根的距离的量度。 相对于海平面计算海洋深度，类似地，相对于树的根节点，测量二叉树中任何节点的深度。 二叉树中特定节点的深度是从根节点到该节点的边数。 二叉树的深度是最深节点(叶节点)的深度。
To find the depth of the binary tree we will recursively calculate the depth of the left and right child of a node. After finding the depth of both left and right child we will store the depth of the child which has maximum value and add 1 to it to include the current level of tree.
为了找到二叉树的深度，我们将递归计算节点左右子节点的深度。 找到左右孩子的深度后，我们将存储具有最大值的孩子的深度，并向其添加1以包括当前树的级别。
算法 (Algorithm)
|
1
2
3
4
5
6
7
|
FindDepth( Node root)
If root == NULL
return 0
else
int leftD = FindDepth ( root->left )
int rightD = FindDepth (root->right )
return max( leftD, rightD)+1
|
|
1
2
3
4
5
6
7
|
FindDepth ( Node root )
If root == NULL
return 0
else
int leftD = FindDepth ( root -> left )
int rightD = FindDepth ( root -> right )
return max ( leftD , rightD ) + 1
|
查找二进制树深度的C ++程序 (C++ Program to Find Depth of Binary Tree)
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <bits/stdc++.h>
using namespace std;
/* structure of a binary tree */
struct node
{
int data; // to store the value of a node in tree
node* left; // pointer to the left child
node* right; // pointer to the right child
};
/* Finding the depth of tree */
int FindDepth(node* node)
{
if (node == NULL) // when the subtree is empty
return 0;
else
{
int leftD,rightD;
/*find the depth of left child */
leftD = FindDepth(node->left);
/*find the depth of right child */
rightD = FindDepth(node->right);
/* return the maximum depth */
if (leftD > rightD)
return(leftD + 1);
else
return(rightD + 1);
}
}
/* function to get new node for the tree */
node* getNode(int data)
{
node* newNode = new node();
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return(newNode);
}
int main()
{
/* creating the binary tree */
node *root = getNode(1);
root->left = getNode(2);
root->right = getNode(3);
root->left->left = getNode(4);
root->left->right = getNode(5);
root->right->left = getNode(6);
root->right->right = getNode(7);
root->left->right->right = getNode(10);
cout << "The Depth of the binary tree is " << FindDepth(root)-1;
return 0;
}
|
|
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <bits/stdc++.h>
using namespace std ;
/* structure of a binary tree */
struct node
{
int data ; // to store the value of a node in tree
node * left ; // pointer to the left child
node * right ; // pointer to the right child
} ;
/* Finding the depth of tree */
int FindDepth ( node * node )
{
if ( node == NULL ) // when the subtree is empty
return 0 ;
else
{
int leftD , rightD ;
/*find the depth of left child */
leftD = FindDepth ( node -> left ) ;
/*find the depth of right child */
rightD = FindDepth ( node -> right ) ;
/* return the maximum depth */
if ( leftD > rightD )
return ( leftD + 1 ) ;
else
return ( rightD + 1 ) ;
}
}
/* function to get new node for the tree */
node * getNode ( int data )
{
node * newNode = new node ( ) ;
newNode -> data = data ;
newNode -> left = NULL ;
newNode -> right = NULL ;
return ( newNode ) ;
}
int main ( )
{
/* creating the binary tree */
node * root = getNode ( 1 ) ;
root -> left = getNode ( 2 ) ;
root -> right = getNode ( 3 ) ;
root -> left -> left = getNode ( 4 ) ;
root -> left -> right = getNode ( 5 ) ;
root -> right -> left = getNode ( 6 ) ;
root -> right -> right = getNode ( 7 ) ;
root -> left -> right -> right = getNode ( 10 ) ;
cout << "The Depth of the binary tree is " << FindDepth ( root ) - 1 ;
return 0 ;
}
|
Output:
输出：
The Depth of the binary tree is 3
二叉树的深度为3
Comment down below if you have queries related to height and depth of binary tree.
如果您有关于二叉树的高度和深度的查询，请在下面注释。
翻译自: https://www.thecrazyprogrammer.com/2019/11/height-and-depth-of-binary-tree.html