• 1167阅读
  • 1回复

二叉树学习笔记 [复制链接]

上一主题 下一主题
离线啊冲
 

只看楼主 倒序阅读 使用道具 楼主  发表于: 2016-02-04



二叉树的简单操作,记录一下方便复习:


[cpp] view plain copy
  1. #pragma once  
  2. #include <string.h>  
  3. #include <iostream>  
  4.   
  5. class CMyTree  
  6. {  
  7. public:  
  8.     CMyTree() :m_pNode(nullptr), m_nCount(0){};  
  9.     ~CMyTree(){};  
  10.   
  11.     typedef struct _NODE  
  12.     {  
  13.         int nData;  
  14.         _NODE* pLChild;  
  15.         _NODE* pRChild;  
  16.   
  17.     }NODE, *PNODE;  
  18. public:  
  19.     PNODE& GetNode(){ return m_pNode; }  
  20.       
  21.     bool AddNode(PNODE &pNode,int nData)  
  22.     {  
  23.         pNode = new NODE;  
  24.         memset(pNode, 0, sizeof(NODE));  
  25.         pNode->nData = nData;  
  26.         m_nCount++;  
  27.         return true;  
  28.     }  
  29.   
  30.     bool IsEmpty(){ m_pNode ? false : true; }  
  31.   
  32.     bool Insert(int nData)  
  33.     {  
  34.         if (Insert(m_pNode, nData))  
  35.         {  
  36.             return true;  
  37.         }  
  38.         return false;  
  39.     }  
  40.     bool Insert(PNODE &pNode, int nData)  
  41.     {  
  42.         if (nullptr == pNode)  
  43.         {  
  44.             AddNode(pNode, nData);  
  45.             return true;  
  46.         }  
  47.         else if (nData == pNode->nData)  
  48.             return false;  
  49.         else if (nData < pNode->nData)  
  50.         {  
  51.             return Insert(pNode->pLChild, nData);  
  52.         }  
  53.         else if (nData > pNode->nData)  
  54.         {  
  55.             return Insert(pNode->pRChild, nData);  
  56.         }  
  57.         return false;  
  58.     }  
  59.   
  60.     PNODE GetMaxLChild(PNODE pNode)     // 获取左子树的最大值节点  
  61.     {  
  62.         while (pNode->pRChild)  
  63.         {  
  64.             pNode = pNode->pRChild;  
  65.         }  
  66.         return pNode;  
  67.     }  
  68.   
  69.     PNODE GetMinRChild(PNODE pNode)     // 获取右子树的最小值节点  
  70.     {  
  71.         while (pNode->pLChild)  
  72.         {  
  73.             pNode = pNode->pLChild;  
  74.         }  
  75.         return pNode;  
  76.     }  
  77.   
  78.     bool Delete(int nData)  
  79.     {  
  80.         if (Delete(m_pNode, nData))  
  81.         {  
  82.             m_nCount--;  
  83.             return true;  
  84.         }  
  85.         return false;  
  86.     }  
  87.     bool Delete(PNODE &pNode, int nData)  
  88.     {  
  89.         if (nullptr == pNode)  
  90.             return false;  
  91.         else if (nData == pNode->nData)  
  92.         {  
  93.             if (!pNode->pLChild && !pNode->pRChild)  
  94.             {  
  95.                 delete pNode;  
  96.                 pNode = nullptr;  
  97.                 return true;  
  98.             }  
  99.             else if (pNode->pLChild)  
  100.             {  
  101.                 PNODE pMax = GetMaxLChild(pNode->pLChild);  
  102.                 pNode->nData = pMax->nData;  
  103.                 return Delete(pNode->pLChild, pMax->nData);  
  104.             }  
  105.             else if (pNode->pRChild)  
  106.             {  
  107.                 PNODE pMax = GetMinRChild(pNode->pRChild);  
  108.                 pNode->nData = pMax->nData;  
  109.                 return Delete(pNode->pRChild, pMax->nData);  
  110.             }  
  111.         }  
  112.         else if (nData < pNode->nData)  
  113.         {  
  114.             return Delete(pNode->pLChild, nData);  
  115.         }  
  116.         else if (nData > pNode->nData)  
  117.         {  
  118.             return Delete(pNode->pRChild, nData);  
  119.         }  
  120.         return false;  
  121.     }  
  122.   
  123.   
  124.     //清空  
  125.     void Clear()  
  126.     {  
  127.         Clear(m_pNode);  
  128.         m_nCount = 0;  
  129.     }  
  130.     void Clear(PNODE pNode)  
  131.     {  
  132.         if (nullptr != pNode)  
  133.         {  
  134.             Clear(pNode->pLChild);  
  135.             Clear(pNode->pRChild);  
  136.             delete pNode;  
  137.             pNode = nullptr;  
  138.         }  
  139.     }  
  140.   
  141.     //前序遍历  
  142.     void PreOrderTraverse()  
  143.     {  
  144.         PreOrderTraverse(m_pNode);  
  145.     }  
  146.     void PreOrderTraverse(PNODE pNode)  
  147.     {  
  148.         if (nullptr == pNode)  
  149.             return;  
  150.         std::cout << pNode->nData << std::endl;  
  151.         PreOrderTraverse(pNode->pLChild);  
  152.         PreOrderTraverse(pNode->pRChild);  
  153.     }  
  154.   
  155.     //中序遍历  
  156.     void InOrderTraverse()  
  157.     {  
  158.         InOrderTraverse(m_pNode);  
  159.     }  
  160.     void InOrderTraverse(PNODE pNode)  
  161.     {  
  162.         if (nullptr == pNode)  
  163.             return;  
  164.         InOrderTraverse(pNode->pLChild);  
  165.         std::cout << pNode->nData << std::endl;  
  166.         InOrderTraverse(pNode->pRChild);  
  167.     }  
  168.   
  169.     //后序遍历  
  170.     void PostOrderTraverse()  
  171.     {  
  172.         PostOrderTraverse(m_pNode);  
  173.     }  
  174.     void PostOrderTraverse(PNODE pNode)  
  175.     {  
  176.         if (nullptr == pNode)  
  177.             return;  
  178.         PostOrderTraverse(pNode->pLChild);  
  179.         PostOrderTraverse(pNode->pRChild);  
  180.         std::cout << pNode->nData << std::endl;  
  181.     }  
  182. private:  
  183.     PNODE m_pNode;  
  184.     int   m_nCount;  
  185. };  

善者 慈悲心常在 无怨无恨 以苦为乐
默认压缩密码www.hifyl.com
文件分享密码问题:http://www.hifyl.com/read-htm-tid-4444.html
离线v2680267313

只看该作者 沙发  发表于: 2016-04-30
用户被禁言,该主题自动屏蔽!
快速回复
限100 字节
如果您在写长篇帖子又不马上发表,建议存为草稿
 
上一个 下一个