函数递归调用图

函数递归调用图.png

二叉树

  1. // 二叉树.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
  2. //
  3. #include "pch.h"
  4. #include <stdio.h>
  6. struct Node {
  7.     int nData;        // 节点的数据域
  8.     Node* pLeft;    // 左子树指针
  9.     Node* pRight;    // 右子树指针
  11.     Node() :pLeft(), pRight() {}
  12.     Node(int nData) 
  13.         :nData(nData),pLeft(), pRight()
  14.     {}
  15. };
  17. // 二叉查找树
  18. class BSTree {
  19.     int m_nCount = 0; // 树中节点个数
  20.     Node* m_pRoot = 0;// 根节点指针:记录树中的根节点地址.
  22. protected:
  23.     // 参数1是指针的引用, 为的是能够在
  24.     // 函数内部修改函数外部的实参(可以参考交换两个变量的函数)
  25.     /*!
  26.      * 函数名 : insert
  27.      * 功  能 : 将数据nData插入到pTree作为根节点的树居中
  28.      * 参  数 : Node * & pTree 树的根节点.
  29.      * 参  数 : int nData 插入的数据
  30.      * 返回值 :  void
  31.      */
  32.     void insert( Node*& pTree, int nData) {
  33.         // 1. 判断树的根节点是否为NULL,如果为NULL
  34.         //    直接插入到根节点
  35.         if (pTree == nullptr) {
  36.             pTree = new Node(nData);
  37.             // 递增节点个数
  38.             ++m_nCount;
  39.             return;
  40.         }
  41.         // 2. 如果不为空,则判断插入的数据和根节点
  42.         //    所保存的数据的大小关系
  43.         if (nData < pTree->nData) {
  44.             // 3. 如果插入数据小于根节点数据,那么就将
  45.             //    根节点的左子树作为新的根节点,让后将
  46.             //    数据插入到左子树中.
  47.             insert(pTree->pLeft, nData);
  48.         }
  49.         else {
  50.             // 否则就插入到右子树中.
  51.             insert(pTree->pRight, nData);
  52.         }    
  53.     }
  55.     Node*& find(Node*& pTree, int nData) {
  56.         if (pTree == nullptr) {
  57.             return pTree;
  58.         }
  59.         // 1. 判断当前节点保存的数据是否
  60.         //    就是要查找的数据
  61.         if (pTree->nData == nData) {
  62.             // 如果是, 就返回节点本身
  63.             return pTree;
  64.         }
  65.         // 如果不是, 则判断这个数据是在节点的左子树中
  66.         // 还是在右子树中.
  67.         // 因为二叉树是左小右大的.
  68.         // 因此, 比较要删除的数据和当前节点的大小关系
  69.         // 就能知道是在左子树还是在右子树中
  70.         else if (nData < pTree->nData) {
  71.             return find(pTree->pLeft,nData);
  72.         }
  73.         else {
  74.             return find(pTree->pRight,nData);
  75.         }
  76.     }
  77.     void remove(Node*& pTree, int nData) {
  78.         if (pTree == nullptr) {
  79.             return;
  80.         }
  82.         printf("-------- 删除:%d-----  \n", nData);
  83.         printTree();
  85.         // 1. 在树中查找到要删除的节点.
  86.         Node*& pFindNode = find(pTree, nData);
  87.         // 是否能够找到节点.
  88.         if (pFindNode == nullptr) {
  89.             return;
  90.         }
  91.         // 2. 找到节点的就是被删除的节点
  92.         //    删除时要判断节点是否是一个叶子节点
  93.         //    如果是叶子节点可以直接删除
  94.         if (pFindNode->pLeft == nullptr && pFindNode->pRight == nullptr) {
  95.             // 直接删除
  96.             delete pFindNode;
  97.             // 将指针设置为空,由于pFindNode是一个指针
  98.             // 的引用, 因此它修改的是哪里????(实际上修改的是
  99.             // 父节点的右子树指针或左子树指针)
  100.             pFindNode = nullptr;
  101.             // 递减节点个数
  102.             --m_nCount;
  103.             return;
  104.         }
  105.         // 3. 如果不是叶子节点. 就需要在被删除节点的
  106.         //    子树中找到一个叶子节点, 然后两者的值
  107.         //    互换, 再删除掉叶子节点
  108.         // 3.1 再找叶子节点的时候, 需要考虑子树高度差
  109.         //    因此会在树高比较高的子树中找叶子节点.
  110.         int nLeftHeight = getHeight(pFindNode->pLeft);
  111.         int nRightHeight = getHeight(pFindNode->pRight);
  112.         // 3.2 树中左小右大的关系, 因此, 需要左子树中
  113.         //     找最大值, 在右子树中找最小值.    
  114.         if (nLeftHeight >= nRightHeight) {
  115.             // 左子树比较高,需要找最大值
  116.             Node*& pNode = getMax(pFindNode->pLeft);
  117.             // 将当前被找到的节点和叶子节点的数据域
  118.             // 进行调换
  119.             int t = pFindNode->nData;
  120.             pFindNode->nData = pNode->nData;
  121.             pNode->nData = t;
  122.             // 删除叶子节点
  123.             // 递归删除.
  124.             remove(pFindNode->pLeft, pNode->nData);
  125.         }
  126.         else {
  127.             // 右子树比较高,需要找最小值
  128.             Node*& pNode = getMin(pFindNode->pRight);
  129.             int t = pFindNode->nData;
  130.             pFindNode->nData = pNode->nData;
  131.             pNode->nData = t;
  132.             // 删除叶子节点
  133.             // 递归删除.
  134.             remove(pFindNode->pRight, pNode->nData);
  135.         }
  136.     }
  137.     /*!
  138.      * 函数名 : getHeight
  139.      * 功  能 : 求一个树的高度
  140.      * 参  数 : Node * pTree
  141.      * 返回值 :  int
  142.      */
  143.     int getHeight(Node* pTree) {
  144.         if (pTree == nullptr) {
  145.             return 0;
  146.         }
  147.         // 求出左子树的高度
  148.         int nLeftHeight = 
  149.             getHeight(pTree->pLeft);
  151.         // 求出右子树的高度
  152.         int nRightHeight = 
  153.             getHeight(pTree->pRight);
  154.         // 取左右子树高度的最大值作为子树的高度
  155.         int nHeight = nLeftHeight > nRightHeight ? nLeftHeight : nRightHeight;
  157.         // 本节点的高度 = 自身高度 + 子树的高度
  158.         return 1 + nHeight;
  159.     }    
  161.     Node*& getMin(Node*& pTree) {
  162.         if (pTree == nullptr) {
  163.             return pTree;
  164.         }
  166.         // 二叉树是左小右大的.
  167.         // 一个树的最小值就在树的最左边
  169.         if (pTree->pLeft == nullptr) {
  170.             // 如果本节点的左子节点已经为空了
  171.             // 说明了本节点就是树中最左边的节点
  172.             // 就返回节点自身.
  173.             return pTree;
  174.         }
  175.         return getMin(pTree->pLeft);
  176.     }
  178.     Node*& getMax(Node*& pTree) {
  179.         if (pTree == nullptr) {
  180.             return pTree;
  181.         }
  182.         // 二叉树是左小右大的.
  183.         // 一个树的最大值就在树的最右边
  184.         if (pTree->pRight == nullptr) {
  185.             // 如果本节点的右子节点已经为空了
  186.             // 说明了本节点就是树中最右边的节点
  187.             // 就返回节点自身.
  188.             return pTree;
  189.         }
  190.         return getMax(pTree->pRight);
  191.     }
  193.     // 清空整颗树(后序遍历
  194.     void clear(Node*& pTree) {
  195.         clear(pTree->pLeft);
  196.         clear(pTree->pRight);
  197.         delete pTree;
  198.     }
  199.     // 前序方式遍历树
  200.     void printTreeByPreOrder(Node*& pTree) {
  201.         if (pTree == nullptr) {
  202.             return;
  203.         }
  204.         printf("%d,", pTree->nData);
  205.         printTreeByPreOrder(pTree->pLeft);
  206.         printTreeByPreOrder(pTree->pRight);
  207.     }
  208.     // 中序方式遍历树
  209.     void printTreeByInOrder(Node*& pTree) {
  210.         if (pTree == nullptr) {
  211.             return;
  212.         }
  213.         printTreeByInOrder(pTree->pLeft);
  214.         printf("%d,", pTree->nData);
  215.         printTreeByInOrder(pTree->pRight);
  216.     }
  217.     // 后序方式遍历树
  218.     void printTreeByPostOrder(Node*& pTree) {
  219.         if (pTree == nullptr) {
  220.             return;
  221.         }
  222.         printTreeByPostOrder(pTree->pLeft);
  223.         printTreeByPostOrder(pTree->pRight);
  224.         printf("%d,", pTree->nData);
  225.     }
  227.     void printTree(Node*& pTree, int nWidth, char ch) {
  228.         if (pTree == nullptr) {
  229.             return;
  230.         }
  231.         printTree(pTree->pLeft, nWidth + 2, '/');
  232.         printf("%*c%d\n", nWidth, ch , pTree->nData);
  233.         printTree(pTree->pRight, nWidth + 2, '\\');
  234.     }
  236.     void sort(Node*& pTree) {
  237.         // 1. 判断树的形状:
  238.         int nLeftHeight = getHeight(pTree->pLeft);
  239.         int nRightHeight = getHeight(pTree->pRight);
  240.         if (nLeftHeight - nRightHeight > 1) {
  241.             // 1.1 左斜
  242.             nLeftHeight = getHeight(pTree->pLeft->pLeft);
  243.             nRightHeight = getHeight(pTree->pLeft->pRight);
  244.             if (nLeftHeight > nRightHeight) {
  245.                 // 1.1.1 左单斜
  246.             }
  247.             else {
  248.                 // 1.1.2 左歪斜
  250.             }
  251.         }
  252.         else if (nLeftHeight - nRightHeight < -1) {
  253.             // 1.2 右斜
  254.             nLeftHeight = getHeight(pTree->pRight->pLeft);
  255.             nRightHeight = getHeight(pTree->pRight->pRight);
  256.             if (nRightHeight > nLeftHeight) {
  257.                 // 1.2.1 右单斜
  258.             }
  259.             else {
  260.                 // 1.2.2 右歪斜
  261.             }
  262.         }
  263.     }
  264. public:
  265.     void insert(int nData) {
  266.         insert(m_pRoot, nData);
  267.     }
  268.     void remove(int nData) {
  269.         remove(m_pRoot, nData);
  270.     }
  271.     void printTree() {
  272.         printTree(m_pRoot, 2, '*');
  273.         printf("\n");
  274.     }
  275. };
  276. struct MyStruct {
  277.     int nNum = 0;
  278.     const char* pStr;
  279. };
  280. const char*& fun(const char*& p) {
  281.     return p;
  282. }
  283. int main(){
  284.     MyStruct stc = {0, "hello" };
  285.     const char*& p = fun(stc.pStr);
  286.     p = "呵呵";
  288.     BSTree tree;
  289.     tree.insert(10);
  290.     tree.insert(5);
  291.     tree.insert(20);
  292.     tree.insert(7);
  293.     tree.insert(6);
  294.     tree.printTree();
  297.     tree.remove(10);
  298.     tree.printTree();
  299. }