1 #pragma once 2 //首先建立树节点的类型 3 //一个树节点有数据域，有指向左子树的指针域，有指向右子树的指针域 4 //我们将其封装成一个结构体类型 5 class DoubleTree{ 6 public: 7     typedef struct _DOUBLENODE{ 8         int m_nData;                //二叉树节点数据 9         _DOUBLENODE* leftNode;      //二叉树左子树10         _DOUBLENODE* rightNode;     //二叉树右子树11     }*PTREENODE, TREENODE;12 //一棵树，只要有一个指针指向根节点，还有记录树节点的变量就足以表示13 private:14     int treeCount;                  //树节点个数15     PTREENODE pRoot;                //根节点16 public:17     DoubleTree();                   //初始化       18     ~DoubleTree();                  //析构19     bool IsEmpty();                 //判断树是否为空20     bool Insert(int nData);         //插入数据21     bool DeleteNode(int nData);     //删除数据22     bool DestroyTree();             //销毁树23     int  GetDepth();                //获取深度24     void  PreOrderTraverse();       //前序遍历25     void  InOrderTraverse();        //中序遍历26     void  PostOrderTraverse();      //后序遍历27 private:28     //递归所用函数29     bool  Insert(PTREENODE &pNode, int nData);30     bool  DeleteNode(PTREENODE &pNode, int nData);31     bool  DestroyTree(PTREENODE pNode);32     int   GetDepth(PTREENODE pNode);33     void  PreOrderTraverse(PTREENODE pNode);34     void  InOrderTraverse(PTREENODE pNode);35     void  PostOrderTraverse(PTREENODE pNode);36     //删除数据时需要调用的函数37     PTREENODE GetMaxpLchild(PTREENODE pNode);38     PTREENODE GetMinpRchild(PTREENODE pNode);39     //平衡函数40     void  SingRotateLeft(PTREENODE &pK2);41     void  SingRotateRight(PTREENODE &pK2);42     void  DoubleRotateLR(PTREENODE &pK);43     void  DoubleRotateRL(PTREENODE &pK);44 };

#include "stdafx.h"#include
     
      #include "DoubleTree.h"//初始化DoubleTree::DoubleTree(){    pRoot = nullptr;                       //将根节点指针初始化指向空    treeCount = 0;                         //将树节点个数初始化为0}//析构DoubleTree::~DoubleTree(){}//判断树是否为空树//我们知道根节点指针初始化时，将指针置为null//而所有的节点都是由根节点出发，如果根都没有，那么树就是空树//即判断根节点指针是否为空，为空返回true否则返回falsebool DoubleTree::IsEmpty(){    if (pRoot){                                   //当根节点指针有值，则不为空        return false;    }    return true;}
     

1 //插入数据时调用的递归子函数 2 //在递归查找到插入位置时，根据插入位置为null，插入数据 3 //为当前点分配一个空间，并将数据传进去，树元素个数加1， 4 bool DoubleTree::Insert(PTREENODE &pRootTemp,int nData){ 5     if (!pRootTemp){                               //如果当前指针为空，证明可插入 6         pRootTemp = new TREENODE;                  //申请新节点空间 7         memset(pRootTemp, 0, sizeof(TREENODE));    //空间初始化为0 8         pRootTemp->m_nData = nData;                //存入要插入的数据 9         treeCount++;                               //树长度加110         return true;11     }12     //如果当前点不为空，则取出当前点元素13     //插入的数据大于当前点数据14     //把当前点右子树地址传入，调用插数据函数，递归调用15     if (nData>pRootTemp->m_nData){                 //插入的数比根节点大，右遍历16         Insert(pRootTemp->rightNode, nData);       //右子树继续插入17         //如果插入成功，则要以当前点为基础，在递归回掉过程中判断是否需要平衡18         //在右插入成功的情况下，获取到当前左右子树深度19         //1.当右子树深度大于左子树深度，相差为2时，只能初步判断需要平衡20         //2.继续判断，将当前节点的右子树传进去，再次判断深度21         //3.此时获取的深度，为我当前节点的，右子树的，左右子树深度22         //4.当左子树深度大于右子树深度时，需要右左旋(情况1)23         //5.否则只需要左旋（情况2）24         //简单说明如下25         //图示：（情况1）26         //27         //    (回朔时当前节点)         //第一次判断当前节点的左右子树深度28         //            /  \29         //              (节点1)        //第一次满足的情况下，判断节点1的左右深度30         //               /   \31         //                   (节点2)32         //33         //也就是说当节点1左子树有值，而节点2不存在的情况下，需要先右旋，再左旋34         ////图示2：（情况2）35         //    (回朔时当前节点)        36         //            /  \37         //              (节点1)        38         //               /   \39         //           (节点3)   40         //要注意的是，做先右旋的操作，是以节点1为基准的，也就是说传入的参数是节点141         if (GetDepth(pRootTemp->rightNode) - GetDepth(pRootTemp->leftNode) == 2){42             if (GetDepth(pRootTemp->rightNode->leftNode) >43                 GetDepth(pRootTemp->rightNode->rightNode)){44                 DoubleRotateRL(pRootTemp);           //右深度大于左深度 45             }46             else{47                 SingRotateLeft(pRootTemp);  48             }49         }50     }51     //在左插入成功的情况下，判断是否需要平衡！获取到当前左右子树深度52     //1.当左子树深度大于右子树深度，相差为2时，只能初步判断需要平衡53     //2.继续判断，将当前节点的左子树传进去，再次判断深度54     //3.此时获取的深度，为我当前节点的，左子树的，左右子树深度55     //4.当右子树深度大于左子树深度时，需要左右旋(情况1)56     //5.否则只需要右旋（情况2）57     //简单说明如下58     //图示：（情况1）59     //60     //    (回朔时当前节点)         //第一次判断当前节点的左右子树深度61     //            /  \62     //        (节点1)              //第一次满足的情况下，判断节点1的左右深度63     //         /  \64     //    (节点2)65     //66     //也就是说当节点1左子树有值，而节点2不存在的情况下，需要先左旋，再右旋67     ////图示2：（情况2）68     //    (回朔时当前节点)        69     //            /  \70     //        (节点1)        71     //         /   \72     //           (节点3)   73 74     //要注意的是，做先左旋的操作，是以节点1为基准的，也就是说传入的参数是节点175     if (pRootTemp->m_nData > nData){                //插入的数比根节点小，左遍历        76         Insert(pRootTemp->leftNode, nData);         //将左子树地址返回77         if (GetDepth(pRootTemp->leftNode) - GetDepth(pRootTemp->leftNode) == 2)78         {79             if (GetDepth(pRootTemp->leftNode->rightNode) >80                 GetDepth(pRootTemp->leftNode->leftNode)){81                 DoubleRotateLR(pRootTemp); 82             }83             else{84                 SingRotateRight(pRootTemp); 85             }86         }87     }88     else{89         return false;                              //其他情况（数据等于的时候），返回失败90     }    91     return true;92 }93 //插入数据外部调用函数94 bool DoubleTree::Insert(int nData){95     if (Insert(pRoot, nData))return true;          //传入根节点，插入成功返回true96     return false;97 }

1 //下面开始介绍删除节点  2 //先说几个子函数  3 //假如我们已经找到了要删除点的位置  4 //此时我们不可能说，直接把这个节点删了。  5 //因为你一删除，如果后边有子树怎么办，会丢失 。  6 //另一个问题，树是一个整体，如果你随便哪删除节点的子树接过来  7 //那你能保证这树还能满足，左子树小于右子树吗？  8 //那么，我们是不是应该讨论，删除点的值该拿什么来代替  9 //(1)明白一点，左子树的各节点值都比要删除点值小 10 //也就是说如果我们找到左子树中的最大值，那么这个值就可以替代掉要删除位置的值 11 //(2)相反，右子树的值都比根节点大，这时只有最小值可以替换根节点 12 // 13 //图示： 14 //   15 //                             (当前要删除的点) 16 //                                 /     \ 17 //                             (左子树) （右子树） 18 //**************************************************************************** 19 //                                (当前要删除的点) 20 //                                   /          \ 21 //                               (节点1)        （节点2） 22 //                                /  \              /  \ 23 //                          （节点3）（节点4）（节点5） （节点6） 24 //******************************************************************************** 25 //很显然，如果要删除的点没了，要从子树中找值代替。只有节点4，和节点5符合条件 26 //节点4就是左子树中最大值，最大值怎么找到呢，只需要在左子树中一直往右找，到最后 27 //节点5呢，则是右子树中最小值，只需在子树中一直往左边找，到最后那个 28  29 //找到左子树最大值，并返回地址 30 DoubleTree::PTREENODE  DoubleTree::GetMaxpLchild(PTREENODE pNode){ 31     while(pNode->rightNode){          //如果根节点右子树存在 32         pNode = pNode->rightNode;     //右子树地址给根节点 33     } 34     return pNode;                     //返回左子树最大值地址 35      36 } 37 //找到右子树最小值，并返回地址 38 DoubleTree::PTREENODE  DoubleTree::GetMinpRchild(PTREENODE pNode){ 39     while (pNode->leftNode){          //如果根节点左子树存在 40         pNode = pNode->leftNode;      //左子树地址给根节点 41     } 42     return pNode;                     //返回最小值地址 43 } 44  45 //删除数据外部调用 46 bool DoubleTree::DeleteNode(int nData){ 47     if (!DeleteNode(pRoot, nData))                    //删除节点 48     { 49         return false; 50     } 51     treeCount--;                                      //元素个数减一 52     return true; 53 } 54 //删除数据时，用于递归的子函数 55 bool DoubleTree::DeleteNode(PTREENODE &pNode, int nData){ 56     if (nullptr == pNode){                            //如果遍历到空节点，返回错误没找到数 57         return false; 58     } 59     if (nData == pNode->m_nData){                     //如果当前指向数据与传入的数相等 60         if (!pNode->leftNode&&!pNode->rightNode)      //而且左右子树没有数，证明为叶子节点 61         {                                             //此时可以删除 62             delete pNode;                             //删除节点 63             pNode = nullptr; 64         } 65         //如果删除的点找到了，可是左子树有值，此时应该找到左子树最大值，来覆盖这个值 66         else if (pNode->leftNode){                           67             PTREENODE pMax = GetMaxpLchild(pNode->leftNode);//找到最大节点 68             pNode->m_nData = pMax->m_nData;                 //找到的最大值给要删除的节点 69             //当要删除的点被替换掉后，下一步就要删除传入这个最大值，删除这个最大值 70             DeleteNode(pNode->leftNode, pMax->m_nData);     //递归删除 71             //删除成功后需要判断是否平衡 72             //类似插入时的平衡，请参考插入后平衡代码 73             if (GetDepth(pNode->leftNode) - GetDepth(pNode->rightNode) == 2){ 74                 if (GetDepth(pNode->leftNode->rightNode) > 75                     GetDepth(pNode->leftNode->rightNode)){ 76                     DoubleRotateLR(pNode);   //左右旋 77                 } 78                 else{ 79                     SingRotateRight(pNode);  //右旋 80                 } 81             } 82  83         } 84         //如果要删除的点找到了，但左子树没有，右子树存在，则找到右子树最小值 85         //具体讲解参考上方代码，举一反三 86         else if (pNode->rightNode){ 87             PTREENODE pMin = GetMinpRchild(pNode->rightNode); 88             pNode->m_nData = pMin->m_nData; 89             DeleteNode(pNode->rightNode, pMin->m_nData); 90             if (GetDepth(pNode->rightNode) - GetDepth(pNode->leftNode) == 2){ 91                 if (GetDepth(pNode->rightNode->leftNode) > 92                     GetDepth(pNode->rightNode->rightNode)){ 93                     DoubleRotateRL(pNode);     94                 } 95                 else{ 96                     SingRotateLeft(pNode); 97                 } 98             } 99         }100     }101     //不相等时递归查找102     else if (nData < pNode->m_nData){103         DeleteNode(pNode->leftNode, nData);104     }105     else if (nData > pNode->m_nData){106         DeleteNode(pNode->rightNode, nData);107     }108     return true;109 }

1 //获得树的深度                         2 int DoubleTree::GetDepth(){                       //获取深度 3     int nMaxHeight = GetDepth(pRoot); 4     return nMaxHeight; 5 } 6 int DoubleTree::GetDepth(PTREENODE pNode){ 7     if (nullptr == pNode)                         //递归的退出条件 8         return 0; 9     int nLHeight = GetDepth(pNode->leftNode);     //获取左子树的深度10     int nRHeight = GetDepth(pNode->rightNode);    //获取右子树的深度11     int nMaxHeight = nLHeight > nRHeight ? nLHeight : nRHeight;12     nMaxHeight += 1;                              //加上自己(第一次传入节点的位置)这一层13     return  nMaxHeight;14 }

1 //简单右旋 2 //      应对情况           保存k1          k1右子树给k2左    k2给k1右子树 3 // 4 //       (1)k2             (2)k1           (1)k2           （2）k1 5 //       /                 / \              /               / \ 6 //     (2)k1            (3)  (可选)       (可选)           (3) (1)k2 7 //     / \                                                     / 8 //   (3) (可选)                                              (可选) 9 10 void  DoubleTree::SingRotateRight(PTREENODE &pNodeK2){11                                            //k1为k2的左子树，k2为找到的点，即旋转位置12     PTREENODE pNodeK1 = pNodeK2->leftNode; //新指针K1，接收要旋转点的左子树13     pNodeK2->leftNode = pNodeK1->rightNode;//将k1的右子树给k2的左子树14     pNodeK1->rightNode = pNodeK2;          //将k2给k1右子树15     pNodeK2 = pNodeK1;                     //k1给k2     16 }17 //简单左旋18 void  DoubleTree::SingRotateLeft(PTREENODE &pNodeK2){19     PTREENODE pNodeK1 = pNodeK2->rightNode;20     pNodeK2->rightNode = pNodeK1->leftNode;21     pNodeK1->leftNode= pNodeK2;22     pNodeK2 = pNodeK1;23 }24 //先右旋，后左旋（注意第一次旋转传入的参数）25 void  DoubleTree::DoubleRotateRL(PTREENODE &pNodeK3){26     SingRotateRight(pNodeK3->rightNode);27     SingRotateLeft(pNodeK3);28 }29 //先左旋，再右旋（注意第一次旋转传入参数）30 void  DoubleTree::DoubleRotateLR(PTREENODE &pNodeK3){31     SingRotateLeft(pNodeK3->leftNode);32     SingRotateRight(pNodeK3);33 34 }

1 //销毁递归子函数 2 bool DoubleTree::DestroyTree(PTREENODE pNode){ 3     //如果树为空，返回错误 4     if (!pNode){ 5         return false; 6     } 7     //如果当前点是叶子节点删除 8     if (!pNode->leftNode&&!pNode->rightNode){ 9         delete pNode;10         pNode = nullptr;11         return true;12     }13     else{14         //否则左有子树，删除左，右有子树，删除右15         if (pNode->leftNode){16             DestroyTree(pNode->leftNode);17         }18         if (pNode->rightNode){19             DestroyTree(pNode->rightNode);20         }21         DestroyTree(pNode);                   //删除根22     }23     return true;24 }25 //销毁外部调用函数26 bool DoubleTree::DestroyTree(){27     if (DestroyTree(pRoot))return true;28     return false;29 }

1 //前序遍历整棵树 2 void DoubleTree::PreOrderTraverse(){ 3     PreOrderTraverse(pRoot); 4 } 5 void  DoubleTree::PreOrderTraverse(PTREENODE pNode){ 6     if (!pNode){ 7         return; 8     } 9     //根->左->右10     printf("%d  ", pNode->m_nData);11     PreOrderTraverse(pNode->leftNode);12     PreOrderTraverse(pNode->rightNode);13 }14 //中序遍历整棵树15 void  DoubleTree::InOrderTraverse(){16     InOrderTraverse(pRoot);17 }18 void  DoubleTree::InOrderTraverse(PTREENODE pNode){19     if (!pNode){20         return;21     }22     //左子树->根->右子树23     InOrderTraverse(pNode->leftNode);24     printf("%d  ", pNode->m_nData);25     26     InOrderTraverse(pNode->rightNode);27 }28 //后序遍历整棵树29 void  DoubleTree::PostOrderTraverse(){30     PostOrderTraverse(pRoot);31 }32 void  DoubleTree::PostOrderTraverse(PTREENODE pNode){33     if (!pNode)    {34         return;35     }36     //左子树->右子树->根37     PostOrderTraverse(pNode->leftNode);38     PostOrderTraverse(pNode->rightNode);39     printf("%d  ", pNode->m_nData);40 }

1 #include "stdafx.h" 2 #include"DoubleTree.h" 3 int _tmain(int argc, _TCHAR* argv[]) 4 { 5     DoubleTree TEST; 6     TEST.Insert(0); 7     TEST.Insert(1); 8     TEST.Insert(2); 9     TEST.Insert(3);10     TEST.Insert(4);11     TEST.Insert(5);12     TEST.Insert(6);13     TEST.Insert(7);14     TEST.Insert(8);15     TEST.Insert(9);16     printf("\n中序遍历：\n");17     TEST.InOrderTraverse();18     printf("\n先序遍历：\n");19     TEST.PreOrderTraverse();20     printf("\n后序遍历\n");21     TEST.PostOrderTraverse();22     TEST.DeleteNode(1);23     printf("\n中序遍历：\n");24     TEST.InOrderTraverse();25     return 0;26 }