1 //二叉树问题集：   2 //20140822   3    4 #include <iostream>   5 #include <cstdio>   6 #include <cstdlib>   7 #include <queue>   8 #include <stack>   9 #include <list>  10 using namespace std;  11   12   13 typedef int ElementType;  14 typedef struct TreeNode  15 {  16     ElementType data;  17     struct TreeNode* pLeft;  18     struct TreeNode* pRight;  19 }TreeNode;  20   21 typedef struct TreeNode* PtrNode;  22 typedef struct TreeNode* BinaryTree;  23   24   25 //建立二叉树：  26 PtrNode CreateBinaryTreeNode(ElementType val)  27 {  28     PtrNode ptrNode = new TreeNode;  29     ptrNode->data =http://www.mamicode.com/ val;  30     ptrNode->pLeft = NULL;  31     ptrNode->pRight = NULL;  32     return ptrNode;  33 }  34   35 void ConnectTreeNodes(PtrNode pNode1, PtrNode pNode2, PtrNode pNode3)  36 {  37     if (pNode1 == NULL)  38     {  39         return ;  40     }  41     pNode1->pLeft = pNode2;  42     pNode1->pRight = pNode3;  43 }  44   45 BinaryTree CreateBinaryTree()  46 {  47     PtrNode pNode1 = CreateBinaryTreeNode(1);  48     PtrNode pNode2 = CreateBinaryTreeNode(2);  49     PtrNode pNode3 = CreateBinaryTreeNode(3);  50     PtrNode pNode4 = CreateBinaryTreeNode(4);  51     PtrNode pNode5 = CreateBinaryTreeNode(5);  52     PtrNode pNode6 = CreateBinaryTreeNode(6);  53     PtrNode pNode7 = CreateBinaryTreeNode(7);  54     PtrNode pNode8 = CreateBinaryTreeNode(8);  55     PtrNode pNode9 = CreateBinaryTreeNode(9);  56     PtrNode pNode10 = CreateBinaryTreeNode(10);  57     PtrNode pNode11 = CreateBinaryTreeNode(11);  58     PtrNode pNode12 = CreateBinaryTreeNode(12);  59   60     ConnectTreeNodes(pNode1, pNode2, pNode3);  61     ConnectTreeNodes(pNode2, pNode4, pNode5);  62     ConnectTreeNodes(pNode3, pNode6, pNode7);  63     ConnectTreeNodes(pNode4, pNode8, pNode9);  64     ConnectTreeNodes(pNode8, pNode10, pNode11);  65   66     return pNode1;  67 }  68 BinaryTree CreateBinaryTree2()  69 {  70     PtrNode pNode1 = CreateBinaryTreeNode(1);  71     PtrNode pNode2 = CreateBinaryTreeNode(2);  72     PtrNode pNode3 = CreateBinaryTreeNode(3);  73     PtrNode pNode4 = CreateBinaryTreeNode(4);  74     PtrNode pNode5 = CreateBinaryTreeNode(5);  75     PtrNode pNode6 = CreateBinaryTreeNode(6);  76     PtrNode pNode7 = CreateBinaryTreeNode(7);  77     PtrNode pNode8 = CreateBinaryTreeNode(8);  78     PtrNode pNode9 = CreateBinaryTreeNode(9);  79     PtrNode pNode10 = CreateBinaryTreeNode(10);  80     PtrNode pNode11 = CreateBinaryTreeNode(11);  81     PtrNode pNode12 = CreateBinaryTreeNode(12);  82   83     ConnectTreeNodes(pNode1, pNode2, pNode3);  84     ConnectTreeNodes(pNode2, pNode4, pNode5);  85     ConnectTreeNodes(pNode3, pNode6, pNode7);  86     ConnectTreeNodes(pNode4, pNode8, pNode9);  87     ConnectTreeNodes(pNode8, pNode10, NULL);  88   89     return pNode1;  90 }  91   92 BinaryTree CreateBinaryTree3()  93 {  94     PtrNode pNode1 = CreateBinaryTreeNode(10);  95     PtrNode pNode2 = CreateBinaryTreeNode(5);  96     PtrNode pNode3 = CreateBinaryTreeNode(12);  97     PtrNode pNode4 = CreateBinaryTreeNode(4);  98     PtrNode pNode5 = CreateBinaryTreeNode(7);  99     ConnectTreeNodes(pNode1, pNode2, pNode3); 100     ConnectTreeNodes(pNode2, pNode4, pNode5); 101  102     return pNode1; 103 } 104  105 BinaryTree CreateBinaryTree4() 106 { 107     PtrNode pNode1 = CreateBinaryTreeNode(1); 108     PtrNode pNode2 = CreateBinaryTreeNode(2); 109     PtrNode pNode3 = CreateBinaryTreeNode(3); 110     PtrNode pNode4 = CreateBinaryTreeNode(4); 111     PtrNode pNode5 = CreateBinaryTreeNode(5); 112     PtrNode pNode6 = CreateBinaryTreeNode(6); 113     PtrNode pNode7 = CreateBinaryTreeNode(7); 114     PtrNode pNode8 = CreateBinaryTreeNode(8); 115     PtrNode pNode9 = CreateBinaryTreeNode(9); 116     PtrNode pNode10 = CreateBinaryTreeNode(10); 117     PtrNode pNode11 = CreateBinaryTreeNode(11); 118     PtrNode pNode12 = CreateBinaryTreeNode(12); 119  120     //ConnectTreeNodes(pNode1, pNode2, pNode3); 121     //ConnectTreeNodes(pNode2, pNode4, pNode5); 122     ConnectTreeNodes(pNode3, pNode6, pNode7); 123     ConnectTreeNodes(pNode4, pNode8, pNode9); 124     //ConnectTreeNodes(pNode8, pNode10, pNode11); 125  126     return pNode1; 127 } 128  129 //先序遍历：递归 130 void PerOrderPrint(BinaryTree Tree) 131 { 132     if (Tree == NULL) 133     { 134         return ; 135     } 136  137     cout << Tree->data << " "; 138     PerOrderPrint(Tree->pLeft); 139     PerOrderPrint(Tree->pRight); 140  141 } 142  143 //中序遍历：递归 144 void InOrderPrint(BinaryTree Tree) 145 { 146     if (Tree == NULL) 147     { 148         return; 149     } 150     InOrderPrint(Tree->pLeft); 151     cout << Tree->data << " "; 152     InOrderPrint(Tree->pRight); 153 } 154  155 //后序遍历：递归 156 void PostOrderPrint(BinaryTree Tree) 157 { 158     if (Tree == NULL) 159     { 160         return; 161     } 162     PostOrderPrint(Tree->pLeft); 163     PostOrderPrint(Tree->pRight); 164     cout << Tree->data << " "; 165 } 166  167 /************************************************************************/ 168 /* 二叉树的非递归遍历:先序，中序、后序、及层序遍历 169 /************************************************************************/ 170 /************************************************************************ 171 * 非递归先序遍历： 172 * 方法：用栈结构， 173 *    1.先让右子树节点进栈，再让左子树节点进栈 174 *    2.如果栈非空，则进行出栈操作 175 *    类似于层序遍历 176 ************************************************************************/ 177 void PerOrderPrintNoRecursive(BinaryTree Tree) 178 { 179     if (Tree == NULL) 180     { 181         return; 182     } 183     PtrNode ptrNode = Tree; 184     stack<PtrNode> s; 185     s.push(ptrNode); 186     while (!s.empty()) 187     { 188         ptrNode = s.top(); 189         cout << ptrNode->data << " "; 190         s.pop(); 191         if (ptrNode->pRight != NULL) //注意：先序遍历先让右子树节点入栈 192         { 193             s.push(ptrNode->pRight); 194         } 195         if (ptrNode->pLeft != NULL) 196         { 197             s.push(ptrNode->pLeft); 198         } 199     } 200 } 201  202  203 /************************************************************************ 204 * 非递归中序遍历： 205 * 方法：用栈结构， 206 *    1. 207 *    2. 208 ************************************************************************/ 209 void InOrderPrintNoRecursive(BinaryTree Tree) 210 { 211     if (Tree == NULL) 212     { 213         return; 214     } 215  216     PtrNode ptrCurrent = Tree; //指明当前要检测的数据,此时根节点不要先入栈 217     stack<PtrNode> s; 218     while (ptrCurrent != NULL || !s.empty()) 219     { 220         while (ptrCurrent != NULL) 221         { 222             s.push(ptrCurrent); 223             ptrCurrent = ptrCurrent->pLeft; 224         } 225         if (!s.empty()) 226         { 227             ptrCurrent = s.top(); 228             cout << ptrCurrent->data << " "; 229             s.pop(); 230             ptrCurrent = ptrCurrent->pRight; 231         } 232     } 233 } 234  235  236 /************************************************************************ 237 * 非递归后序遍历： 238 * 方法：用栈结构， 239 ************************************************************************/ 240 //void PostOrderNoRecursive(BinaryTree Tree) 241 //{ 242 //    if (Tree == NULL) 243 //    { 244 //        return ; 245 //    } 246  247 //    PtrNode ptrCurr = Tree; 248 //    stack<PtrNode> s; 249 //    s.push(ptrCurr); 250 //    while (ptrCurr != NULL || !s.empty()) 251 //    { 252 //        while (ptrCurr != NULL) 253 //        { 254 //            ptrCurr = s.top(); 255 //            if (ptrCurr->pLeft != NULL) 256 //            { 257 //                s.push(ptrCurr->pLeft); 258 //            } 259 //            if (ptrCurr->pRight != NULL) 260 //            { 261 //                s.push(ptrCurr->pRight); 262 //            } 263 //        } 264  265 //    } 266  267 //} 268  269  270  271 //层序遍历二叉树 272 void LayerOrderPrint(BinaryTree Tree) 273 { 274     if (Tree == NULL) 275     { 276         return ; 277     } 278  279     int nodeNumInTree = 0; //  记录节点的个数 280     queue<PtrNode> Queue; 281     PtrNode ptrNode = Tree; 282     Queue.push(ptrNode); 283     while (!Queue.empty()) 284     { 285         ptrNode = Queue.front(); 286         cout << ptrNode->data << " " ; 287         nodeNumInTree++; 288         Queue.pop(); 289         if (ptrNode->pLeft != NULL) 290         { 291             Queue.push(ptrNode->pLeft); 292         } 293         if (ptrNode->pRight != NULL) 294         { 295             Queue.push(ptrNode->pRight); 296         } 297     } 298  299     //cout << endl; 300     //cout << "节点的个数： " << nodeNumInTree; 301  302     return ; 303 } 304  305  306 //求书中结点的个数 307 int GetNodeNumber(BinaryTree Tree) 308 { 309     if (Tree == NULL) 310     { 311         return 0; 312     } 313     return GetNodeNumber(Tree->pLeft) + GetNodeNumber(Tree->pRight) + 1; 314 } 315  316 //求叶子节点的个数： 317 int GetLeavesNumber(BinaryTree Tree) 318 { 319     if (Tree == NULL) 320     { 321         return 0; 322     } 323     static int leavesNum = 0; 324  325     if (Tree->pLeft == NULL && Tree->pRight == NULL) 326     { 327         leavesNum++; 328     } 329     GetLeavesNumber(Tree->pLeft); 330     GetLeavesNumber(Tree->pRight); 331  332     return leavesNum; 333 } 334  335 //求二叉树深度 336 int GetTreeDepth(BinaryTree Tree) 337 { 338     if (Tree == NULL) 339     { 340         return 0; 341     } 342     int leftDepth = GetTreeDepth(Tree->pLeft); 343     int rightDepth = GetTreeDepth(Tree->pRight); 344  345     return leftDepth >= rightDepth?leftDepth+1:rightDepth+1; 346 } 347  348 //将二叉树变为有序的双向链表 剑指offer27题 349 void ConvertToDoubleList(BinaryTree Tree, PtrNode* listNode); 350 BinaryTree ConvertToList(BinaryTree Tree) 351 { 352     if (Tree == NULL) 353     { 354         return NULL; 355     } 356  357     PtrNode listNode = NULL; 358     ConvertToDoubleList(Tree, &listNode); 359  360     //返回头结点： 361     PtrNode lastNode = listNode; 362     while (lastNode != NULL && lastNode->pLeft != NULL) 363     { 364         lastNode = lastNode->pLeft; 365     } 366  367  368  369     return lastNode; 370 } 371 void ConvertToDoubleList(BinaryTree Tree, PtrNode* listNode) 372 { 373     if (Tree == NULL) 374     { 375         return ; 376     } 377  378     PtrNode pCurrent = Tree; 379     if (pCurrent->pLeft != NULL) 380     { 381         ConvertToDoubleList(pCurrent->pLeft, listNode); 382     } 383  384     pCurrent->pLeft = *listNode; 385     if (*listNode != NULL) 386     { 387         (*listNode)->pRight = pCurrent; 388     } 389     *listNode = pCurrent; 390  391     if (pCurrent->pRight != NULL) 392     { 393         ConvertToDoubleList(pCurrent->pRight, listNode); 394     } 395 } 396  397 void PrintList(BinaryTree ListTree) 398 { 399     if (ListTree == NULL) 400     { 401         return; 402     } 403     PtrNode p = ListTree; 404     while (p != NULL) 405     { 406         cout << p->data << " "; 407         p = p->pRight; 408     } 409     cout << endl; 410 } 411 //转换成双向链表完 412  413  414 /********************************************************* 415 * 求二叉树第K层的节点数 416 * 1.如果树为空或者K<1，返回0 417 * 2.如果K == 1， 返回1 418 * 3.如果K>1, 节点数等于左子树第K-1层节点与右子树第K-1层之和 419 **********************************************************/ 420 //递归 421 int GetNodeNumInLayerK(BinaryTree Tree, int k) 422 { 423     if (Tree == NULL || k < 1) 424     { 425         return 0; 426     } 427     if (k == 1) 428     { 429         return 1; 430     } 431  432     return GetNodeNumInLayerK(Tree->pLeft, k - 1) + GetNodeNumInLayerK(Tree->pRight, k - 1); 433 } 434 //非递归，根据层序遍历，求出第K层节点数 435 int GetNodeNumInLayerKByLayerPrint(BinaryTree Tree, int k) 436 { 437     if (Tree == NULL || k < 1) 438     { 439         return 0; 440     } 441 //    if (k == 1) 442 //    { 443 //        return 1; 444 //    } 445  446     PtrNode ptrNode = Tree; 447     queue<PtrNode> q; 448     q.push(ptrNode); 449     while (q.size()) 450     { 451         --k; 452         if (k <= 0) break; 453         int nodeNumInQ = q.size(); 454         while (nodeNumInQ--) 455         { 456             ptrNode = q.front(); 457             q.pop(); 458             if (ptrNode->pLeft != NULL) 459             { 460                 q.push(ptrNode->pLeft); 461             } 462             if (ptrNode->pRight != NULL) 463             { 464                 q.push(ptrNode->pRight); 465             } 466         } 467     } 468     return q.size(); 469 } 470  471  472 /********************************************************* 473 * 判断两个树结构是否结构相同  474 * 1.如果两个树都为空，返回true; 475 * 2.如果一个为空，一个不为空， 返回flase 476 * 3.如果都不为空, 则判断对应的左右子树是否结构相同，  477 **********************************************************/ 478 bool StructureCmp(BinaryTree Tree1, BinaryTree Tree2) 479 { 480     if (Tree1 == NULL && Tree2 == NULL) 481     { 482         return true; 483     } 484     if (Tree1 == NULL && Tree2 != NULL || Tree1 != NULL && Tree2 == NULL) 485     { 486         return false; 487     } 488  489     bool left = StructureCmp(Tree1->pLeft, Tree2->pLeft); 490     bool right = StructureCmp(Tree1->pRight, Tree2->pRight); 491     return (left && right); 492 } 493  494  495 /********************************************************* 496 * 判断树的子结构  497 * 输入两个树A和B，判断树B是否是树A的子结构 498 * 1.如果两个树都为空，返回false; 499 * 2.如果一个为空，一个不为空， 返回flase 500 * 3.如果都不为空, 则判断对应的是否是子结构，  501 * 4.步骤： 502 *    1）在A中找到和B的根节点的值相同的节点R 503 *    2）判断树A中以R为根节点的子树是不是包含和树B一样的结构 504 * 剑指offer，第18题 505 **********************************************************/ 506 bool DoesTreeAHaveTreeB(BinaryTree TreeA, BinaryTree TreeB); 507 bool HasSubtree(BinaryTree TreeA, BinaryTree TreeB) 508 { 509     bool result = false; 510     if (TreeA != NULL && TreeB != NULL) 511     { 512         if (TreeA->data =http://www.mamicode.com/= TreeB->data) 513         { 514             result = DoesTreeAHaveTreeB(TreeA,TreeB); 515         } 516         if (!result) 517         { 518             result = HasSubtree(TreeA->pLeft, TreeB); 519         } 520         if (!result) 521         { 522             result = HasSubtree(TreeA->pRight, TreeB); 523         } 524     } 525     return result; 526 } 527  528 bool DoesTreeAHaveTreeB(BinaryTree TreeA, BinaryTree TreeB) 529 { 530     if (TreeA == NULL) 531     { 532         return false; 533     } 534     if (TreeB == NULL) 535     { 536         return true; 537     } 538  539     return DoesTreeAHaveTreeB(TreeA->pLeft, TreeB->pLeft) && DoesTreeAHaveTreeB(TreeA->pRight,  540         TreeB->pRight); 541 } 542  543  544  545  546 /********************************************************* 547 * 判断树是否是平衡二叉树 548 * 1.如果树为空，返回true; 549 * 2.如果不为空, 则判断左右子树是否都是AVL，且左右子树高度相差不大于1，则返回true，其他返回false，  550 **********************************************************/ 551 bool IsAVL(BinaryTree Tree, int& Height) 552 { 553     if (Tree == NULL) 554     { 555         return true; 556     } 557  558     int leftHeight = 0; 559     int rightHeight = 0; 560     bool isLeftAVL = IsAVL(Tree->pLeft, leftHeight); 561     bool isRightAVL = IsAVL(Tree->pRight, rightHeight); 562     Height = leftHeight >= rightHeight?leftHeight+1:rightHeight+1; 563  564     if (isLeftAVL && isRightAVL && abs(leftHeight - rightHeight) <= 1) 565     { 566         return true; 567     } 568     else 569     { 570         return false; 571     } 572  573 } 574  575  576  577 /********************************************************* 578 * 求二叉树的镜像  579 * 1.左右子树交换; 580 **********************************************************/ 581 void TreeMirror(BinaryTree Tree) 582 { 583     if (Tree == NULL) 584     { 585         return ; 586     } 587     PtrNode ptrNode = NULL; 588     ptrNode = Tree->pLeft; 589     Tree->pLeft = Tree->pRight; 590     Tree->pRight = ptrNode; 591  592     TreeMirror(Tree->pLeft); 593     TreeMirror(Tree->pRight); 594 } 595  596 /********************************************************* 597 * 重建二叉树 598 * 根据二叉树的先序及中序遍历，重建二叉树 599 * 剑指offer 6题;编程之美3.9 600 **********************************************************/ 601 PtrNode ConstructBinaryTree(int* startPerOrder, int* endPerOrder, int* startInOrder, int* endInOrder); 602 BinaryTree RebuildTree(int* PerOrder, int* InOrder, int length) 603 { 604     if (PerOrder == NULL || InOrder == NULL || length <= 0) 605     { 606         return NULL; 607     } 608  609     BinaryTree rebuildTree = NULL; 610     rebuildTree = ConstructBinaryTree(PerOrder, PerOrder+length-1, InOrder, InOrder+length-1); 611  612     return rebuildTree; 613 } 614 PtrNode ConstructBinaryTree(int* startPerOrder, int* endPerOrder, int* startInOrder, int* endInOrder) 615 { 616     PtrNode rootNode = new TreeNode;  617     rootNode->pLeft = rootNode->pRight = NULL; 618     rootNode->data = http://www.mamicode.com/startPerOrder[0]; 619  620     int* ptrInOrder = startInOrder; 621     while (*ptrInOrder != rootNode->data && ptrInOrder <= endInOrder) 622         ++ptrInOrder; 623     int leftLen = ptrInOrder - startInOrder; 624  625     if (leftLen > 0) 626     { 627         rootNode->pLeft = ConstructBinaryTree(startPerOrder+1, startPerOrder+leftLen, 628             startInOrder, startInOrder+leftLen-1); 629     } 630     if (leftLen < endPerOrder - startPerOrder) 631     { 632         rootNode->pRight = ConstructBinaryTree(startPerOrder+leftLen+1, endPerOrder, 633             startInOrder+leftLen+1, endInOrder); 634     } 635  636     return rootNode; 637 } 638  639  640  641 /********************************************************* 642 * 找最低公共祖先  643 * 1.如果两个节点为根节点的左右子节点，则返回根节点 644 * 2.如果都在左子树，则递归处理左子树，如果都在右子树，则递归处理右子树 645 **********************************************************/ 646 bool FindNode(BinaryTree Tree, PtrNode pNode) 647 { 648     if (Tree == NULL) 649     { 650         return false; 651     } 652     if (Tree == pNode) 653     { 654         return true; 655     } 656     bool found = FindNode(Tree->pLeft, pNode); 657     if (!found) 658     { 659         found = FindNode(Tree->pRight, pNode); 660     } 661  662     return found; 663 } 664 PtrNode GetLastCommonParent(BinaryTree Tree, PtrNode pNode1, PtrNode pNode2) 665 { 666     if (Tree == NULL || pNode1 == NULL || pNode2 == NULL) 667     { 668         return NULL; 669     } 670     if (FindNode(Tree->pLeft, pNode1)) 671     { 672         if (FindNode(Tree->pRight, pNode2)) 673         { 674             return Tree; 675         } 676         else 677             return GetLastCommonParent(Tree->pLeft, pNode1, pNode2); 678     } 679     else if (FindNode(Tree->pRight, pNode1)) 680     { 681         if (FindNode(Tree->pLeft, pNode2)) 682         { 683             return Tree; 684         } 685         else 686             return GetLastCommonParent(Tree->pRight, pNode1, pNode2); 687     } 688 } 689  690 //递归解法二： 691 PtrNode GetLCA(BinaryTree Tree, PtrNode pNode1, PtrNode pNode2) 692 { 693     if (Tree == NULL) 694     { 695         return NULL; 696     } 697     if (Tree == pNode1 || Tree == pNode2) 698     { 699         return Tree; 700     } 701      702     PtrNode leftNode = GetLCA(Tree->pLeft, pNode1, pNode2); 703     PtrNode rightNode = GetLCA(Tree->pRight, pNode1, pNode2); 704  705     if (leftNode != NULL && rightNode != NULL) 706     { 707         return Tree; 708     } 709     else if (leftNode != NULL) 710     { 711         return leftNode; 712     } 713     else if (rightNode != NULL) 714     { 715         return rightNode; 716     } 717     else 718         return NULL; 719 } 720  721 //非递归解法：先求出两个节点从根节点开始的路径，然后比较路径节点，最后一个相同的就是公共祖先节点 722 bool GetNodePath(BinaryTree Tree, PtrNode pNode, list<PtrNode>& path) 723 { 724     if (Tree == NULL) 725     { 726         return false; 727     } 728     path.push_back(Tree); 729     if (Tree == pNode) 730     { 731         return true; 732     } 733  734     bool found = GetNodePath(Tree->pLeft, pNode, path); 735     if (!found) 736     { 737         found = GetNodePath(Tree->pRight, pNode, path); 738     } 739  740     if (!found) 741     { 742         path.pop_back(); 743     } 744  745     return found; 746 } 747 PtrNode GetLastCommonParentNoRecur(BinaryTree Tree, PtrNode pNode1, PtrNode pNode2) 748 { 749     if (Tree == NULL) 750     { 751         return NULL; 752     } 753     list<PtrNode> path1; 754     bool foundNode1 = GetNodePath(Tree, pNode1, path1); 755     list<PtrNode> path2; 756     bool foundNode2 = GetNodePath(Tree, pNode2, path2); 757     if (!foundNode1 || !foundNode2) 758     { 759         return NULL; 760     } 761  762     PtrNode lastCommonNode = NULL; 763     list<PtrNode>::iterator iter1 = path1.begin(); 764     list<PtrNode>::iterator iter2 = path2.begin(); 765     while (iter1 != path1.end() && iter2 != path2.end()) 766     { 767         if (*iter1 == *iter2) 768         { 769             lastCommonNode = *iter1; 770         } 771         else 772             break; 773         iter1++; 774         iter2++; 775     } 776     return lastCommonNode; 777 } 778  779  780  781 /********************************************************* 782 * 求二叉树中节点的最大距离 783 * 1.如果为空，则最大距离就为0,同时左右子树的最大深度为0 784 * 2.如果不为空，则最大距离要么是左子树最大深度，要么是右子树 785 *    最大深度，要么是左右子树最大深度之和，同时记录左右 786 *    子树的最大深度 787 * 剑指offer；编程之美3.8 788 **********************************************************/ 789 int GetLargestDestInNode(BinaryTree Tree, int& nMaxLeft, int& nMaxRight) 790 { 791     if (Tree == NULL) 792     { 793         nMaxLeft = 0; 794         nMaxRight = 0; 795         return 0; 796     } 797     int maxLL = 0, maxLR = 0; 798     int maxRL = 0, maxRR = 0; 799     int maxDistLeft = 0; 800     int maxDistRight = 0; 801     if (Tree->pLeft == NULL) 802     { 803         maxDistLeft = 0; 804         nMaxLeft = 0; 805     } 806     if (Tree->pRight == NULL) 807     { 808         maxDistRight = 0; 809         nMaxRight = 0; 810     } 811  812     if(Tree->pLeft != NULL) 813     { 814         maxDistLeft = GetLargestDestInNode(Tree->pLeft, maxLL, maxLR); 815         nMaxLeft = maxLL>maxLR?maxLL+1:maxLR+1; 816     } 817     if(Tree->pRight != NULL) 818     { 819         maxDistRight = GetLargestDestInNode(Tree->pRight, maxRL, maxRR); 820         nMaxRight = maxRL>maxRR?maxRL+1:maxRR+1; 821     } 822  823     int maxDist = maxDistLeft>maxDistRight?maxDistLeft:maxDistRight; 824     int nMax = nMaxLeft + nMaxRight; 825     return maxDist>nMax?maxDist:nMax; 826 } 827  828 /********************************************************* 829 * 求二叉树中和为某一值得路径 830 * 路径：从根节点到叶子节点的路径 831 * 1.如果树为空，则路径为空 832 * 2.如果树不为空，则从根节点开始遍历（即前序遍历）,遍历的过程中记录路径 833 *    并记录遍历过的路径的和，如果遍历到叶子节点，判断和是否为所给值， 834 *    如果是，则输出此路径，然后再回到上一个节点。 835 *    记录节点的路径就是一个栈结构， 836 * 注意：在回到上一个几点时，要将叶子节点出栈 837 * 另:本题用vector实现，是因为需要打印路径时，stack无法遍历打印 838 * 剑指offer25题 839 **********************************************************/ 840 void GetRoad(BinaryTree Tree, vector<int>& path, const int& expectedSum, int& currentSum); 841 void GetRoad(BinaryTree Tree, int expectedSum) 842 { 843     if (Tree == NULL) 844     { 845         return; 846     } 847     vector<int> path; 848     int currentSum = 0; 849     GetRoad(Tree, path, expectedSum, currentSum); 850     return ; 851 } 852 void GetRoad(BinaryTree Tree, vector<int>& path, const int& expectedSum, int& currentSum) 853 { 854     if (Tree == NULL) 855     { 856         return ; 857     } 858  859     path.push_back(Tree->data); 860     currentSum += Tree->data; 861     bool isLeaf = Tree->pLeft == NULL && Tree->pRight == NULL; 862     if (isLeaf && expectedSum == currentSum) 863     { 864         cout << "和为" << expectedSum << "的路径为： "; 865         vector<int>::iterator iter = path.begin(); 866         for (; iter != path.end(); ++iter) 867         { 868             cout << *iter << " "; 869         } 870         cout << endl; 871     } 872  873     GetRoad(Tree->pLeft, path, expectedSum, currentSum); 874     GetRoad(Tree->pRight, path, expectedSum, currentSum); 875  876     if (!path.empty()) 877     { 878         //在返回父节点之前，应该从currentSum中减去当前节点的值，因为函数传递的参数currentSum是以引用传递的 879         //若currentSum是非引用传递而是一般传值(即int currentSum)，则不用这步操作 880         currentSum -= path.back();  881     } 882     path.pop_back(); //在返回到父节点之前，删除路径上当前的节点 883 } 884  885  886 /********************************************************* 887 * 判断二叉树是否是完全二叉树 888 * 1.如果树为空，则返回true 889 * 2.如果树不为空，则从根据层序遍历，遍历到第一个左子树为空的节点 890 *    第一个左子树为空的节点的右子树也为空，并且其以后的所有节点 891 *    的左右字数均为空的话，则为完全二叉树，返回true 892 *    否则，不是完全二叉树，返回false 893 **********************************************************/ 894 bool IsCompleteBinaryTree(BinaryTree Tree) 895 { 896     if (Tree == NULL) 897     { 898         return true; 899     } 900  901     queue<PtrNode> q; 902     PtrNode ptrNode = Tree; 903     q.push(ptrNode); 904      905     PtrNode ptrFirNode = NULL; 906     while (!q.empty()) 907     { 908         ptrNode = q.front(); 909         if (ptrFirNode != NULL && (ptrNode->pLeft != NULL || ptrNode->pRight != NULL)) 910         { 911             return false; 912         } 913         if (ptrFirNode == NULL && (ptrNode->pLeft == NULL || ptrNode->pRight == NULL)) 914         { 915             ptrFirNode = ptrNode; 916         } 917         q.pop(); 918  919         if (ptrNode->pLeft != NULL) 920         { 921             q.push(ptrNode->pLeft); 922         } 923         if (ptrNode->pRight != NULL) 924         { 925             q.push(ptrNode->pRight); 926         } 927     } 928  929     return true; 930 } 931  932  933  934  935 int main() 936 { 937     cout << "建立二叉树..." << endl; 938     BinaryTree Tree = CreateBinaryTree(); 939     BinaryTree Tree2 = CreateBinaryTree2(); 940     BinaryTree Tree4 = CreateBinaryTree4(); 941  942  943     int treeDepth = GetTreeDepth(Tree); 944     cout << "二叉树深度： " << treeDepth << endl; 945  946     int nodeNum = GetNodeNumber(Tree); 947     cout << "二叉树结点个数： " << nodeNum << endl; 948  949     cout << "先序遍历..." << endl; 950     PerOrderPrint(Tree); 951     cout << endl; 952  953     cout << "非递归先序遍历..." << endl; 954     PerOrderPrintNoRecursive(Tree); 955     cout << endl; 956  957     cout << "中序遍历..." << endl; 958     InOrderPrint(Tree); 959     cout << endl; 960  961     cout << "非递归中序遍历..." << endl; 962     InOrderPrintNoRecursive(Tree); 963     cout << endl; 964  965     cout << "非递归后序遍历..." << endl; 966     //PostOrderNoRecursive(Tree); 967     cout << endl; 968  969     cout << "层序遍历..." << endl; 970     LayerOrderPrint(Tree); 971     cout << endl; 972  973     //int nodeNum = GetNodeNumber(Tree); 974     //cout << "二叉树结点个数： " << nodeNum << endl; 975  976  977     int leavesNum = GetLeavesNumber(Tree); 978     cout << "叶节点的个数： " << leavesNum << endl; 979  980 //    //转换成双向链表 981 //    PtrNode treeToList = ConvertToList(Tree); 982 //    cout << "双向链表由左至右打印：" <<endl; 983 //    PrintList(treeToList); 984  985     //第K层的节点数 986     int k = 3; 987     //int nodeNumInK = GetNodeNumInLayerK(Tree, k) - GetNodeNumInLayerK(Tree, k - 1); 988     int nodeNumInK = GetNodeNumInLayerK(Tree, k); 989     cout << "第" << k << "层节点数： " << nodeNumInK<< endl;  990     int nodeNumInK2 = GetNodeNumInLayerKByLayerPrint(Tree, k); 991     cout << "根据层序遍历，求得第" << k << "层节点数： " << nodeNumInK2<< endl;  992  993  994     //判断两个树结构是否相同： 995     cout << "判断两个树结构是否形同： " << StructureCmp(Tree, Tree2) << endl; 996  997     //判断B是否是A的子结构： 998     bool hasSubtree = HasSubtree(Tree, Tree4); 999     cout << "是否是子结构"  << hasSubtree << endl;1000 1001     //判断树是否是AVL树：1002     int height = 0;1003     bool isAvl = IsAVL(Tree, height);1004     cout << "是否是AVL树： " << isAvl << endl;1005 1006     //二叉树的镜像：1007     TreeMirror(Tree);1008     cout << "镜像层序输出：";1009     LayerOrderPrint(Tree);1010     //恢复原状：1011     TreeMirror(Tree);1012     cout << endl;1013 1014     //由先序及中序遍历重建二叉树1015     int length = nodeNum;1016     int perOrder[] = {1,2,4,8,10,11,9,5,3,6,7};1017     int inOrder[] = {10,8,11,4,9,2,5,1,6,3,7};1018     BinaryTree rebuildTree = RebuildTree(perOrder, inOrder, length);1019     cout << "重建后层序输出： ";1020     LayerOrderPrint(rebuildTree);1021     cout << endl;1022 1023     //寻找最低公共祖先节点1024     PtrNode commonParentNode = GetLastCommonParent(Tree, Tree->pLeft->pLeft->pLeft, Tree->pRight->pRight);1025     cout << commonParentNode->data << endl;1026     commonParentNode = GetLastCommonParent(Tree, Tree->pLeft->pLeft->pLeft, Tree->pLeft->pRight);1027     cout << "LCA： " << commonParentNode->data << endl;1028     //非递归方法求公共祖先节点：1029     commonParentNode = GetLastCommonParentNoRecur(Tree, Tree->pLeft->pLeft->pLeft, Tree->pLeft->pRight);1030     cout << "LCA： " << commonParentNode->data << endl;1031     //非递归方法求公共祖先节点：1032     //递归方法二：1033     commonParentNode = GetLCA(Tree, Tree->pLeft->pLeft->pLeft, Tree->pLeft->pRight);1034     cout << "LCA： " << commonParentNode->data << endl;1035     1036 1037     //二叉树节点之间的最大距离1038     int nMaxLeft = 0;1039     int nMaxRight = 0;1040     int nMaxLen = GetLargestDestInNode(Tree, nMaxLeft, nMaxRight);1041     cout << nMaxLen << endl;1042 1043 1044     //和为某一个值得路径1045     int expectedSum = 22;1046     BinaryTree Tree3 = CreateBinaryTree3();1047     GetRoad(Tree3, expectedSum);1048 1049     //判断二叉树是否是完全二叉树1050     bool isCompleteTree = IsCompleteBinaryTree(Tree);1051     cout << "是否是完全二叉树： " << isCompleteTree << endl;1052 1053 1054     return 0;1055 }