求二叉树的深度和宽度 ----我对默认构造函数的理解

////计算二叉树的深度和宽度：深度：层数宽度：各层最大节点数

///关于二叉树问题，一般都要用到递归的方法。

////算法：首先构造二叉树节点的结构；要创建二叉树，创建的过程，使用递归算法；其次，计算二叉树深度，也要递归；最难的一点是计算求出层次中的最大节点数，使用队列的方法

 1 #include <iostream>
 2 #include <queue>
 3 #include <tchar.h>
 4 using namespace std;
 5 struct BTNode{
 6 char m_value;
 7 BTNode* m_left;
 8 BTNode* m_right;
 9 
10 };
11 
12 void CreateBtree(BTNode* &pRoot)
13 {
14 char nValue = 0;
15 cin>>nValue;
16 if(nValue == '#')
17 return;
18 /////注意啦！！！new BTNode()调用默认构造函数
19 ///默认构造函数的作用是将结构体或class中的基本变量做初始化
20 //比如int类型初始化为0，string类型初始化"";指针类型初始化为NULL
21 ///这一点非常重要，如果创建一个节点，其m_left和m_right别初始化为NULL
22 ////一个节点是否为叶子节点就是通过判断其左右孩子是否为null来判断的
23 pRoot = new BTNode();
24 pRoot->m_value = nValue;
25 CreateBtree(pRoot->m_left);
26 CreateBtree(pRoot->m_right);
27 }
28 
29 int GetDepth(BTNode* pRoot)
30 {
31 if(pRoot == NULL)
32 return 0;
33 int lLen = 0;
34 int rLen = 0;
35 lLen = GetDepth(pRoot->m_left);
36 rLen = GetDepth(pRoot->m_right);
37 return lLen > rLen ? lLen+1 : rLen+1;
38 }
39 
40 int GetWidth(BTNode* pRoot)
41 {
42 if(pRoot == NULL)
43 return 0;
44 queue<BTNode*> que;
45 BTNode* pCur= NULL;
46 que.push(pRoot);
47 int iWidth= 1;
48 int iLastLen = 1;
49 int iCurLen =0;
50 int iTempLastLen = 0;
51 while(!que.empty())
52 {
53 iTempLastLen = iLastLen;
54 pCur = que.back();
55 que.pop();
56 while(iTempLastLen != 0)
57 {
58 if(pCur->m_left != NULL)
59 que.push(pCur->m_left);
60 if(pCur->m_right != NULL)
61 que.push(pCur->m_right);
62 iTempLastLen--;
63 }
64 iCurLen = que.size();
65 iWidth = iWidth > iCurLen ? iWidth : iCurLen;
66 iLastLen = iCurLen;
67 }
68 return iWidth;
69 
70 }
71 
72 int main()
73 {
74 BTNode *pRoot = NULL; 
75 CreateBtree(pRoot);
76 int idepth = 0;
77 idepth = GetDepth(pRoot);
78 int iwidth = 0;
79 iwidth = GetWidth(pRoot);
80 cout <<idepth<< " "<<iwidth <<endl;
81 return 0;
82 }
83 
84

博客内容只为本人学习所感转载亦或自写，不足或错误之处请大家不吝赐教