二叉树知识总结（二）

二叉树编程练习：

• 求叶子节点数目

  void leafNum(BiTNode* root, int *num)
  {
      if (root == NULL)
      {
          //递归结束的条件，空树
          return;
      }
      //叶子节点
      if (root->lChild == NULL && root->rChild == NULL)
          (*num)++;
      //遍历左子树
      leafNum(root->lChild, num);
      //遍历右子树
      leafNum(root->rChild, num);
  
  }

• 求二叉树的高度

  int treeDepth(BiTNode* root) 
  {
      if (root == NULL) return 0;
      //计算左子树的高度
      int left = treeDepth(root->lChild);
      //计算右子树的高度
      int right = treeDepth(root->rChild);
      //求出左右子树比较高的那个
      int max = left > right ? left : right;
  
      return max + 1;
  
  }

• 拷贝树

  BiTNode* copyTree(BiTNode* root)
  {
      //空树
      if (root == NULL) return NULL;
      //拷贝左子树
      BiTNode* left = copyTree(root->lChild);
      //拷贝右子树
      BiTNode* right = copyTree(root->rChild);
      //创建一个新的节点
      BiTNode* pNew = new BiTNode;
      //初始化
      pNew->data = root->data;
      //指针域
      pNew->lChild = left;
      pNew->rChild = right;
      return pNew;
  }