信号放大器问题的 结构 booster 在 booster.h 中定义：

1 #pragma once 2 #include 
     
       3  4 using namespace std; 5  6 struct booster 7 { 8     int degradeToLeaf;            //到达子节点的信号衰减量 9     int degradeFromParent;       //父节点到此的信号衰减量10     bool boosterHere;            // 放置了信号放大器，值为真11 12     void output(ostream& out) const13     {
    out << boosterHere << ' ' << degradeToLeaf << ' ' << degradeFromParent << ' ';}14 };15 16 // overload <<17 ostream& operator<<(ostream& out, booster x)18     {x.output(out); return out;}
     

并查集问题所需的结构 unionFindNode 定义在 unionFindNode.h 中：

1 #pragma once 2 using namespace std; 3  4  5 struct unionFindNode 6 { 7     int parent;  // root 为真时，表示树的重量；为假时表示父节点的指针 8     bool root;   // 为根时，值为真 9 10     unionFindNode()11     {12         parent = 1; root = true;13     }14 };

application.h ：

1 #pragma once 2 #include "booster.h" 3 #include "binaryTreeNode.h" 4 #include "linkBinaryTree.h" 5 #include "unionFindNode.h" 6  7  8 //信号放大器 9 void placeBoosters(binaryTreeNode
     
       *x, int tolerance);10 11 //并查集12 void initialize(int numberOfElements);13 int find(int theElement);14 void unite(int rootA, int rootB);
     

application.cpp :

1 #include 
     
       2 #include "application.h" 3  4 using namespace std; 5  6  7 /************************************************************************************* 8 //                                        信号放大器 9 *************************************************************************************/10 //x,二叉树节点； tolerance，最大容忍衰减11 void placeBoosters(binaryTreeNode
      
        *x, int tolerance)12 {13     x->element.degradeToLeaf = 0;  // x处衰减量初始化14 15     //计算x的左子树的衰减量，如果大于阈值，则放置信号放大器16     binaryTreeNode
       
         *y = x->leftChild;17     if (y != nullptr)18     {19         int degradation = y->element.degradeToLeaf + y->element.degradeFromParent;20         if (degradation > tolerance)    //衰减大于阈值，放置信号放大器21         {22             y->element.boosterHere = true;23             x->element.degradeToLeaf = y->element.degradeFromParent;24         }25         else26             x->element.degradeToLeaf = degradation;27     }28 29     //计算x的右子树的衰减量，如果大于阈值，则放置信号放大器30     y = x->rightChild;31     if (y != nullptr)32     {33         int degradation = y->element.degradeToLeaf + y->element.degradeFromParent;34         if (degradation > tolerance)    //衰减大于阈值，放置信号放大器35         {36             y->element.boosterHere = true;37             degradation = y->element.degradeFromParent;38         }39         else40             x->element.degradeToLeaf = degradation;41     }42 }43 44 45 /*************************************************************************************46 //                                        并查集47 *************************************************************************************/48 int *parent;49 void initialize(int numberOfElements)    //初始化 numberOfElements 棵树50 {51     parent = new int[numberOfElements + 1];52     for (int e = 1; e <= numberOfElements; e++)53         parent[e] = 0;54 }55 56 int find(int theElement)            //查找,返回 theElement 所在的树的根57 {58     while (parent[theElement] != 0)59         theElement = parent[theElement];    //向上移动一层60     return theElement;61 }62 63 void unite(int rootA, int rootB)    //合并64 {65     parent[rootB] = rootA;66 }