数据结构进阶实训十 二叉排序树

Data structure advanced training course notes and algorithm exercises
数据结构进阶实训课程笔记和算法练习

Source Code: https://github.com/MysticalGuest/DataStructure/tree/master/AdvancedJuniorTraining

---

---

题目1

判断二叉树是否为正则二叉树。
  - 正则二叉树的定义：指在二叉树中不存在度为1的分支点。

1.1 算法设计思想

利用二叉树遍历递归的思想；
先判断当前节点是否正则；
然后递归判断该节点的左右子树。

1.2 源代码

// 1代表是正则二叉树，0代表不是
int IsRegular(BiTree T){
    if(T==NULL)
        return 1;
    else if(T->LChild==NULL ^ T->RChild==NULL)
        return 0;
    else{
        IsRegular(T->LChild);
        IsRegular(T->RChild);
    }
}

1.3 运行情况截图

---

题目2

判断二叉树是否为完全二叉树？

2.1 算法设计思想

一个树是否为完全二叉树，每个节点有以下4中情况：

情况一：      情况二：      情况三：      情况四：
  A            A            A             A
 / \          / \          / \           / \
B   C        B  NULL     NULL B        NULL NULL

规律是：

（1）如果当前访问的节点的左右孩子是情况三，说明不是完全二叉树，直接返回false；

（2）如果当前访问的节点的左右孩子是情况1，继续访问其他节点；

（3）如果当前访问的节点的左右孩子是情况2或者情况4，那么我们定义一个状态（接下来访问的所有节点必须全部是叶子节点）。只要遇到情况2或者情况4，这个状态就开启了。

算法就是层次遍历所有节点并做判断。

2.2 源代码

BOOL IsCBT(BiTree bt){
  if(bt==NULL)    // 空树
    return TRUE;
  BOOL leaf = FALSE;
  SeqQueue Q;
  BiTree p;
  InitQueue(&Q);
  EnterQueue(&Q, bt);

  while(!IsEmpty(Q)){
    DeleteQueue(&Q, &p);
    if(p->LChild==NULL && p->RChild!=NULL)   // 情况3: 当前节点有右孩子，没有左孩子
      return FALSE;
    //上述的状态已经发生，但是当前访问到的节点不是叶节点（有左孩子或者右孩子）
    if(leaf && (p->LChild!=NULL||p->RChild!=NULL))
      return FALSE;
    if(p->LChild!=NULL)    //左孩子不为空，加入到队列中去
      EnterQueue(&Q, p->LChild);
    if(p->RChild!=NULL)   //右孩子不为空，加入到队列中去
      EnterQueue(&Q, p->RChild);
    //这个if语句就是判断状态是否要发生
    if((p->LChild!=NULL && p->RChild==NULL)||(p->LChild==NULL && p->RChild==NULL))
      leaf=TRUE;
  }
  return TRUE;
}

2.3 运行情况截图

---

题目3

二叉树二叉链表存储，结点数据域的值为整数，且取值各不相同。
编写代码判断该二叉树是否为二叉排序树。
二叉排序树，又称二叉查找树。它或者是一颗空树，或者是具有下列性质的二叉树。
  - 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  - 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  - 它的的左、右子树也分别为二叉排序树。

3.1 算法设计思想

由于二叉排序树的中序遍历得到的是一个单调递增的序列；

所以根据这个想法，我们可以中序遍历这个二叉树，将得到的序列存入temp数组；

通过检验temp数组的单调递增性来判断这个二叉树是否为二叉排序树。

3.2 源代码

#define N 100
int temp[N];


int i = 0;
void inorder(BiTree root){
    if(root == NULL)
        return;
    if(root->LChild != NULL)
        inorder(root->LChild);
    temp[i++] = root->data;
    if(root->RChild != NULL)
        inorder(root->RChild);
}
int ISBST(int temp[], int k){
  int flag=0;
  for(int i=1; i<k; i++)
      if(temp[i]<temp[i-1])
          return 0;
  return 1;
}

3.3 运行情况截图

---

题目4

二叉树二叉链表存储，结点数据域的值为整数，且取值各不相同。
编写代码判断该二叉排序树是否为平衡二叉排序树。
  - 平衡二叉树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。

4.1 算法设计思想

通过平衡二叉树的定义可以将判断平衡二叉树的条件分为以下2个：

（1）首先是一颗二叉排序树；

（2）每个节点的左右子树的高度差至多为1；

基于以上两个条件写两个方法；

第一个条件思想和上一题一样，判断二叉排序树；

第二个条件通过递归判断每个节点的左右子树高度；

将两个条件返回值综合，就可以判断出。

4.2 源代码

int Deep(BiTree bt){
  int ld=0,rd=0;
  if(bt){
    ld=Deep(bt->LChild)+1;
    rd=Deep(bt->RChild)+1;
  }
  return ld >= rd?ld:rd;
}

BiTree pre=NULL;
BOOL ISAVL(BiTree root){
  int lcd=0,rcd=0;
  if(root!=NULL){
    int l = ISAVL(root->LChild);
    // printf("pre: %d\n", pre->data);
    lcd=Deep(root->LChild);   // 左子树的深度
    rcd=Deep(root->RChild);   // 右子树的深度
    // printf("Deep(root->LChild): %d\n", Deep(root->LChild));
    // printf("Deep(root->RChild): %d\n", Deep(root->RChild));
    // printf("root: %d\n", root->data);
    if(abs(lcd-rcd)>1){   // 条件1:每一个节点的左子树和右子树的高度差至多等于1
      return FALSE;
    }
    if(pre!=NULL){
      if(pre->data > root->data){    // 条件2:中序遍历的前驱节点大于后面节点的值,就不是平衡二叉树
        return FALSE;
      }
    }
    pre=root;
    int r = ISAVL(root->RChild);
    return l && r;
  }
  return TRUE;
}

4.3 运行情况截图

---

题目5

编写代码完成：输入一棵二叉树，输出它的镜像。

5.1 算法设计思想

利用二叉树遍历递归的思想；

先交换左右子树；

然后分别镜像左右子树。

5.2 源代码

void swap(BiTree *node1, BiTree *node2){
  BiTree temp;
  temp = *node1;
  *node1=*node2;
  *node2=temp;
}

void Mirror(BiTree *bt){
  if((*bt)==NULL)
    return;
  swap(&((*bt)->LChild), &((*bt)->RChild));
  Mirror(&((*bt)->LChild));

  Mirror(&((*bt)->RChild));

}

5.3 运行情况截图

---

题目6

输入：一个整数和一棵二叉树（树中结点的数据值为int）；
输出：二叉树中结点值的和为输入的的整数的所有路径。
路径的定义：从树的根结点开始往下一直到叶子结点形成的，称为一条路径。

6.1 算法设计思想

用先序遍历的方式访问节点，使用栈数组ResultStack存储满足条件的路径，使用栈SeqStack存储当前路径节点。

遍历二叉树的过程：按先序遍历顺序访问每一个节点，访问每个结点时，将结点添加到SeqStack中。

如果当前结点是叶子结点，则判断当前路径是否是符合条件的路径，符合条件的路径存入到栈数组ResultStack；

如果当前结点不是叶子结点，则递归当前节点的左右子节点。

6.2 源代码

SeqStack ResultStack[10];
int i=0;

void SumPath(BiTree bt, SeqStack *S, int value){
  BiTree p;
  Push(S, bt);
  if(bt){
    if(!bt->LChild && !bt->LChild){
      if(value == bt->data){
        ResultStack[i] = *S;
        i++;
      }
    }
    else{
      SumPath(bt->LChild, S, value-bt->data);
      SumPath(bt->RChild, S, value-bt->data);
    }
    if(!IsEmpty(*S))
      Pop(S, &p);
  }
}

6.3 运行情况截图

---

题目7

输入：一个整数数组，判断该数组是否为某二叉排序树的后序遍历序列；
输出：若是，则返回true，若不是，则返回false；
   假设该数组中的任何两个数值都互不相同。

7.1 算法设计思想

后续遍历中，最后一个数字是根结点，将数组中的数字分为两部分：

第一部分是左子树的值，它的值都比根结点小；

另一部分是右子树的值，它的值都比根结点大；

后续遍历（5,7,6,9,11,10,8）的最后一个结点是8，所以在这个数组中，5,7,6都比8小时该数的左子树；而9,11,10都比8大，是该树的右子树。

我们以同样的方法来分析其左子树和右子树5,7,6，其中6将左子树分为5和7两部分；10将右子树9和11分为两部分。所以这个序列就是一个后续遍历序列。但是（7,4,5,6）就不是它的一个后续遍历序列。因为6大于7，所以也就是说7,4,5都是其右子树，但是很不幸还有4比6小，所以不可能是一个后续遍历。

7.2 源代码

BOOL VerifySequenceOfBST(int *array,int length){
  if(array==NULL || length<=0)
    return FALSE;
  int root=array[length-1];
  int i=0;    //左子树的结点小于根节点；
  for(;i<length-1;i++){
    if(array[i]>root)
      break;    //找完了全部的左子树的序列；
  }
  int j=i;//右子树的结点大于根结点；
  for(;j<length-1;j++){
    if(array[j]<root)
      return FALSE;
  }
  BOOL left=TRUE;
  if(i>0)
    left=VerifySequenceOfBST(array,i);
  BOOL right=TRUE;
  if(j<length-1)
    right=VerifySequenceOfBST(array+i,length-i-1);
  return left && right;
}

7.3 运行情况截图

---