2013-09-03 14:16:51

面试题39：求二叉树的深度、判断二叉树是否为平衡二叉树

小结：

1. 根据平衡二叉树的定义，需要判断每个结点，因此，需要遍历二叉树的所有结点，并判断以当前结点为根的树是否为二叉树；
2. 用后序遍历的方式，先判断左右子树是否为平衡的，在判断当前节点；
3. 可以对每个结点求深度，根据深度判断，如函数IsBanlancedTreeBasic所示，但这种方法存在重复遍历，效率较低；
4. 后序遍历时，一边判断是否为平衡二叉树，一边求而二叉树的深度，这样就避免了重复遍历，如函数IsBanlancedTree所示。

代码编写注意事项：

1. 注意IsBanlancedTreeSub中需同时带回深度，因此在返回为true时，需要更新*pDepth的值；
2. 写代码时，注意下面的代码由于优先级会造成错误

if ( (lchilDepth - rchilDepth) < -1 || (lchilDepth - rchilDepth) > 1)

因此改为：

1 int diff = lchilDepth - rchilDepth;2     if ( diff < -1 || diff > 1)3     {4         return false;5     }

 

---

 

代码（测试通过，暂未发现问题，欢迎交流指正）：

1 #include 
     
        2 #include 
      
         3 using namespace std;  4   5 typedef char DataType;  6 const DataType LeafNode = '*';  7 const size_t SIZE = 1000;  8   9 typedef struct binaryTreeNode 10 { 11     DataType data; 12     binaryTreeNode *lchild; 13     binaryTreeNode *rchild; 14 }BTNode,*PBTNode; 15  16 //创建二叉树 17 PBTNode CreatBiTree(PBTNode &pRoot) 18 { 19     DataType newData = 0; 20  21     cin>>newData; 22  23     if (newData == LeafNode) 24     { 25         return NULL; 26     } 27  28     pRoot = new BTNode; 29     pRoot->data = newData; 30  31     pRoot->lchild = CreatBiTree(pRoot->lchild); 32     pRoot->rchild = CreatBiTree(pRoot->rchild); 33  34     return pRoot; 35 } 36  37 //访问二叉树结点 38 void VisitBiTreeNode(const PBTNode &pBTNode) 39 { 40     assert(NULL != pBTNode); 41     cout<
       
        data<<"\t"; 42 } 43  44 //前序遍历二叉树 45 void PreOrder(const PBTNode &pRoot) 46 { 47     if (pRoot != NULL) 48     { 49         VisitBiTreeNode(pRoot); 50         PreOrder(pRoot->lchild); 51         PreOrder(pRoot->rchild); 52     } 53 } 54  55 //中序遍历二叉树 56 void InOrder(const PBTNode &pRoot) 57 { 58     if (pRoot != NULL) 59     { 60         InOrder(pRoot->lchild); 61         VisitBiTreeNode(pRoot); 62         InOrder(pRoot->rchild); 63     } 64 } 65  66 //后序遍历二叉树 67 void PostOrder(const PBTNode &pRoot) 68 { 69     if (pRoot != NULL) 70     { 71         PostOrder(pRoot->lchild); 72         PostOrder(pRoot->rchild); 73         VisitBiTreeNode(pRoot); 74     } 75 } 76  77 //求二叉树深度 78 size_t GetDepthOfBiTree(const PBTNode &pRoot) 79 { 80     if (NULL == pRoot) 81     { 82         return 0; 83     } 84  85     size_t lchilDepth = GetDepthOfBiTree(pRoot->lchild); 86     size_t rchilDepth = GetDepthOfBiTree(pRoot->rchild); 87  88     return ( (lchilDepth > rchilDepth) ? (lchilDepth + 1) : (rchilDepth + 1) ); 89 } 90  91  92 //判断是否平衡二叉树，求每个结点的深度，有重复遍历 93 bool IsBanlancedTreeBasic(const PBTNode &pRoot) 94 { 95     if (pRoot == NULL)   //若左子树为空，右子树的深度超过1，判断会出错 96         return true; 97  98     //return ( IsBanlancedTree(pRoot->lchild) && IsBanlancedTree(pRoot->rchild) ); 99 100     if ( !IsBanlancedTreeBasic(pRoot->lchild) || !IsBanlancedTreeBasic(pRoot->rchild) )101     {102         return false;103     }104 105     size_t lchilDepth = GetDepthOfBiTree(pRoot->lchild);106     size_t rchilDepth = GetDepthOfBiTree(pRoot->rchild);107     int diff = lchilDepth - rchilDepth;108     //if ( (lchilDepth - rchilDepth) < -1 || (lchilDepth - rchilDepth) > 1)109     if ( diff < -1 || diff > 1)110     {111         return false;112     }113 114     return true;115 }116 117 //判断是否平衡二叉树，优化，没有重复遍历118 bool IsBanlancedTreeSub(const PBTNode &pRoot,size_t *pDepth)119 {120     if (pRoot == NULL)  121     {122         *pDepth = 0;123         return true;124     }125 126     size_t lchildDepth = 0;127     size_t rchildDepth = 0;128 129     if ( !IsBanlancedTreeSub(pRoot->lchild,&lchildDepth) || !IsBanlancedTreeSub(pRoot->rchild,&rchildDepth) )130     {131         return false;132     }133 134     int diff = lchildDepth - rchildDepth;135 136     if ( diff < -1 || diff > 1)137     {138         return false;139     }140 141     *pDepth = lchildDepth > rchildDepth ? (lchildDepth + 1) : (rchildDepth + 1);142     return true;143 }144 145 bool IsBanlancedTree(const PBTNode &pRoot)146 {147     size_t Depth = 0;148     return IsBanlancedTreeSub(pRoot,&Depth);149 }150 151 152 void DestoryBiTreeNode(PBTNode pRoot)153 {154     delete pRoot;155 }156 157 //销毁二叉树158 void DestoryBiTree(PBTNode &pRoot)159 {160     if (pRoot != NULL)161     {162         DestoryBiTree(pRoot->lchild);163         DestoryBiTree(pRoot->rchild);164         DestoryBiTreeNode(pRoot);165     }166 }167 168 //测试二叉树相关操作169 void TestBinaryTree()170 {171     PBTNode pRoot = NULL;172 173     cout<<"Test IsBanlancedTree..."<
       
      
     

测试结果：

Test IsBanlancedTree...Please enter the binary tree,'*' for leaf nodeab**c**The pre order is :a       b       cThe in order is :b       a       cThe post order is :b       c       aIsBanlancedTree : 1IsBanlancedTreeBasic : 1Test DestoryBiTree...Please enter the binary tree,'*' for leaf nodeab***The pre order is :a       bThe in order is :b       aThe post order is :b       aIsBanlancedTree : 1IsBanlancedTreeBasic : 1Test DestoryBiTree...Please enter the binary tree,'*' for leaf nodea**The pre order is :aThe in order is :aThe post order is :aIsBanlancedTree : 1IsBanlancedTreeBasic : 1Test DestoryBiTree...Please enter the binary tree,'*' for leaf nodeabc****The pre order is :a       b       cThe in order is :c       b       aThe post order is :c       b       aIsBanlancedTree : 0IsBanlancedTreeBasic : 0Test DestoryBiTree...Please enter the binary tree,'*' for leaf nodeabcd****e*f**The pre order is :a       b       c       d       e       fThe in order is :d       c       b       a       e       fThe post order is :d       c       b       f       e       aIsBanlancedTree : 0IsBanlancedTreeBasic : 0Test DestoryBiTree...Please enter the binary tree,'*' for leaf nodeabd**e**cf***The pre order is :a       b       d       e       c       fThe in order is :d       b       e       a       f       cThe post order is :d       e       b       f       c       aIsBanlancedTree : 1IsBanlancedTreeBasic : 1Test DestoryBiTree...Please enter the binary tree,'*' for leaf node**The pre order is :        请按任意键继续. . .