37.2° Blog

1、递归

递归的两大条件：

• 终止条件：树为空的时候，或子树为空的时候
• 递推式：问题规模递减

Func(T) // 根据问题对树进行求解 = 解1 + 解2
{
  对根进行访问求解； --->  解1
  再对左右子树进行求解； --->  解2
}

如：求树的结点：根存在就加1，递归左右子树，左子树中节点数量 + 右子树中节点数量+ 1，就是整棵树的结点数量。

BiTNode *Func(BiTree T, int x)  //接口设计,这个函数就是求解的问题
{
  if (NULL != T) //判树是否为空.一定会出去,这就是终止条件
  {
    访问根结点; +1
    左子树的求解;===》Func(T->lchild);
    右子树的求解;===>Func(T->rchild);
  }
}

2、求二叉树结点个数

• 设计递归函数终止条件，问题求解方法就获得
• 终止条件 —> if判空树
• 问题求解：根的解 + 左右子树的解（直接调用方法）

二叉树遍历方式选择：

• 中序：二叉排序中对于带顺序、大小；中序遍历二叉排序树的时候，升序序列
• 后序：表达式求解
• 其余为先序遍历

// 求解结点个数，使用先序遍历
int getNodesNumber(BiTree T)
{
    if (T == NULL)
        return 0;
    return 1 + getNodesNumber(T->lchild) + getNodesNumber(T->rchild);
}

3、二叉树中值为x的结点

查找二叉树中值为x的结点。若存在，则返回存储位置；若不存在，则返回空值。

• 设计函数接口，问题求解方法获得
• 终止条件：if判空树
• 问题求解：根的解 + 左右子树的解（直接调用方法）

// 寻找树中值为x的结点
BiTNode* getNodesValue(BiTree T, ElemType x)
{
    if (T == NULL)
        return NULL;
    if (T->data == x)   // 判断根结点
        return T;
    BiTNode* pNode = getNodesValue(T->lchild, x);
    if (pNode == NULL)
        return getNodesValue(T->rchild, x);
    return pNode;
}

4、树的高度

左右子树高度最大者+1（根结点）

// 求树的高度
int getBiTreeHeight(BiTree T)
{
    if (T == NULL)
        return 0;
    int leftHeight = getBiTreeHeight(T->lchild);    // 左子树高度
    int rightHeight = getBiTreeHeight(T->rchild);   // 右子树高度
    // 树的高度，左右子树高度最大者+1(根结点)
    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

5、值为x结点为根结点的子树深度

求一颗二叉树中值为x的结点作为根结点的子树深度。

• 先去找结点x，x结点作为子树的根

// 求一颗二叉树中值为x的结点作为根结点的子树深度
int getElemNodeHeight(BiTree T, ElemType x)
{
    BiTNode* pNode = getNodesValue(T, x);
    if (pNode == NULL)
        return 0;
    return getBiTreeHeight(pNode);
}

6、交换一颗二叉树的左右子树

// 交换一颗二叉树的左右子树
void switchLRTreeChild(BiTree T)
{
    if (T == NULL)
        return;
    BiTNode* tmp = T->lchild;
    T->lchild = T->rchild;
    T->rchild = tmp;
    switchLRTreeChild(T->lchild);
    switchLRTreeChild(T->rchild);
}

7、判断两棵树是否相似

判断两棵树是否相似，相似返回TRUE，不相似返回FALSE

二叉树的相似，一般都是形态相同就行。

// 判断两棵树是否相似，相似返回TRUE，不相似返回FALSE
bool isSimilarBiTree(BiTree T1, BiTree T2)
{
    if (T1 == NULL && T2 == NULL)
        return true;
    if ((T1 != NULL && T2 == NULL) || (T1 == NULL && T2 != NULL))
        return false;
    return (isSimilarBiTree(T1->lchild, T2->lchild)
        && isSimilarBiTree(T1->rchild, T2->rchild));
}

8、求一颗二叉树的叶子节点个数

• 根结点为叶子，不存在左右子树，就没有必要再找下去，有一个叶子结点了，直接返回1

// 求一颗二叉树的叶子节点个数
int getLeafNodeNumber(BiTree T)
{
    if (T == NULL)
        return 0;
    if (T->lchild == NULL && T->rchild == NULL) // 根结点
        return 1;
    return getLeafNodeNumber(T->lchild) + getLeafNodeNumber(T->rchild);
}

9、叶子结点连为双链表

设计算法利用叶子节点中的空指针域将所有叶子结点链接成一个带头结点的双链表

• 使用头插法，先序遍历访问二叉树的每个叶子结点
• 将叶子节点插入到双向链表中，使用尾插法
• 双链表不到万不得已，不要使用头插法

// 使用尾插法将叶子结点连在双链表末尾
void linkLeaf2DuLinkListTail(BiTree T, BiTNode*& pTail)
{
    if (T == NULL)
        return;
    if (T->lchild == NULL && T->rchild == NULL)
    {
        // 尾插法
        pTail->rchild = T;
        T->lchild = pTail;
        pTail = pTail->rchild;  // 尾指针后移
    }
    else // 不是叶子结点
    {
        linkLeaf2DuLinkListTail(T->lchild, pTail);
        linkLeaf2DuLinkListTail(T->rchild, pTail);
    }
}
// 设计算法利用叶子节点中的空指针域将所有叶子结点链接成一个带头结点的双链表
void linkLeaf2DuLinkList(BiTree T, BiTNode*& L)
{
    // 初始化链表
    L = (BiTNode*)malloc(sizeof(BiTNode));
    L->lchild = NULL;
    L->rchild = NULL;
    BiTNode* pTail = L;     // 链表尾指针
    linkLeaf2DuLinkListTail(T, pTail);
}

  // 层序，中序遍历构建树
  ElemType levelOrderList[] = { 'A','B','C','D','E','F','G' };
  int levelOrderListLength = 7;
  ElemType inOrderList[] = { 'D','B','E','A','F','C','G' };
  int inOrderListLength = 7;
  BiTree T = LevelInOrderCreateTree(levelOrderList, 0, levelOrderListLength - 1,
      inOrderList, 0, inOrderListLength - 1);

  preOrder(T);
  printf("\n");
  InOrder(T);
  printf("\n");

  BiTNode* L = NULL;  
  linkLeaf2DuLinkList(T, L);
  BiTNode* pCurNode = L->rchild;
  while (pCurNode != NULL)
  {
      printf("%c ", pCurNode->data);
      pCurNode = pCurNode->rchild;
  }
  printf("\n");

10、求解算术表达式

假设一个仅含有 二元运算的算术表达式以二叉链表形式存放在二叉树T，设计算法求解算数表达式的值

int operatorFunc(char oprt, int leftRes, int rightRes)
{
    switch (oprt)
    {
    case'+':
        return leftRes + rightRes;
    case'-':
        return leftRes - rightRes;
    case'*':
        return leftRes * rightRes;
    case'/':
        return leftRes / rightRes;
    }
}
// 计算算法表达式
// 数字存在叶子结点，运算符存在其他节点
int getResultExpress(BiTree T)
{
    if (T == NULL)
        return 0;
    if (T->lchild == NULL && T->rchild == NULL)
        return T->data - '0';   // 字符存入，数字键'0'
    else
    {
        int leftRes = getResultExpress(T->lchild);
        int rightRes = getResultExpress(T->rchild);
        return operatorFunc(T->data, leftRes, rightRes);
    }
}

验证，采用先序、中序遍历建立二叉树

  // 先序，中序创建树
  ElemType preOrderMathList[] = { '*','+','1','2','3'};
  int preOrderListMathLength = 5;
  ElemType inOrderMathList1[] = { '1','+','2','*','3' };
  int inOrderListMathLength1 = 5;
  BiTree T2 = PreInOrderCreateTre(preOrderMathList, 0, preOrderListMathLength - 1,
      inOrderMathList1, 0, inOrderListMathLength1 - 1);
  printf("math result: %d\n", getResultExpress(T2));

运行结果：

11、层序遍历

二叉树的层次遍历

• 与某一层所有结点相关的性质判定
• 与判定完全二叉树、求一棵树的最大宽度类似
• 共根（先序、中序、后序），他们从一个结点出发，无法同时访问非共父母结点
• 层次遍历涉及不同的根结点

程序每次只能访问一个顶点，但是需要访问一层的多个顶点，为了在访问当前顶点的时候，其余待访问的同层结点信息不丢失，需要用队列来保存根结点。

void LevelOrder(BiTree T)
{
    LinkQueue Q;
    InitQueue(Q);   // 初始化辅助队列
    BiTree p = NULL;
    EnQueue(Q, T);   // 将根节点入队
    while(!IsEmpty(Q))  // 队列不空则循环
    {
        DeQueue(Q, p);  // 头结点出队
        print_tree_value(p);    // 打印出队头结点
        if(p->lchild != NULL)
            EnQueue(Q, p->lchild);  // 左子树不空，则左子树入队
        if(p->rchild != NULL)
            EnQueue(Q, p->rchild);  // 右子树不空，则右子树入队
    }
}

12、判断是否为完全二叉树

• 一个实结点之前不能存在空结点
• 不管结点是否为空，先压入队列，再出节点
• 如果发现空结点，若队列中还有实结点，那么此树不是完全二叉树
• 反之，队列中剩余的元素都为空结点，则二叉树为完全二叉树

bool isCompleteBiTree(BiTree T)
{
    LinkQueue Q;
    initQueue(Q);   // 初始化队列
    enQueue(Q, T);
    BiTNode* e = NULL;
    // 层次遍历
    while (!isQueueEmpty(Q))    // 队列不为空，说明还存在结点需要层次遍历
    {
        deQueue(Q, e);      // 头结点出队
        if (e == NULL)      // 遇到空结点，跳出循环，判断后序是否存在结点
            break;
        enQueue(Q, e->lchild);  // 不管左子树是否为空，左子树入队
        enQueue(Q, e->rchild);  // 不管右子树是否为空，则右子树入队
    }
    // 判断空结点后是否存在实结点
    while (!isQueueEmpty(Q))
    {
        deQueue(Q, e);      // 头结点出队
        if (e != NULL)
            return false;
    }
    return true;
}

13、求一棵二叉树的最大宽度

• 最大宽度就是结点个数最多的那层的结点树
• 只有知道结点是属于那一层，才能统计那一层的结点数量，所以在压入结点的时候，需要将他的层号压入进入
• 层号发生变化，上一层的结点数量已统计完，判断是不是当前最大

// 求一棵二叉树的最大宽度
int getTreeWidth(BiTree T)
{
    if (T == NULL)
        return 0;
    LinkQueue Q;
    initQueue(Q);
    QueueElemType e;
    e.levelNode = 1;
    e.treeNode = T;
    enQueue(Q, e);

    int maxNodesNumber = 0;   // 当前最大结点数量
    int curNodesNumber = 0;   // 当前一层的结点数量
    int curLevel = 1;   // 当前访问的层号

    while (!isQueueEmpty(Q))
    {
        deQueue(Q, e);
        if (curLevel == e.levelNode)
            curNodesNumber++;
        else    // 说明统计的一层结点都出队列，一层结点统计完成
        {
            if (maxNodesNumber < curNodesNumber)
                maxNodesNumber = curNodesNumber;
            curLevel = e.levelNode; // 当前层号改变为当前元素层号
            curNodesNumber = 1;
        }
        // 压入当前结点的左右孩子
        BiTNode* pNode = e.treeNode;
        if (pNode->lchild != NULL)
        {
            QueueElemType tmp;
            tmp.levelNode = e.levelNode + 1;
            tmp.treeNode = pNode->lchild;
            enQueue(Q, tmp);
        }
        if (pNode->rchild != NULL)
        {
            QueueElemType tmp;
            tmp.levelNode = e.levelNode + 1;
            tmp.treeNode = pNode->rchild;
            enQueue(Q, tmp);
        }
    }
    // 注意：最后一层的最后一个节点的最大数量未更新
    if (maxNodesNumber < curNodesNumber)
        maxNodesNumber = curNodesNumber;
    return maxNodesNumber;
}