数据结构进阶实训九 二叉树的应用

Data structure advanced training course notes and algorithm exercises

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

---

题目1

建二叉树二叉链表存储
  - 扩展的先序序列（之前采用的方法）
  此次要求：已知两个遍历序列建二叉树（先/中，后/中）
  - 其先、中序遍历序列分别存放在两个数组pre[]和inorder[]中。
  - 其中、后序遍历序列分别存放在两个数组inorder[]和post中。

1.1 算法设计思想

两种建树的思想相同，都是分治的思想；
通过前序遍历，第一个元素就是树的根节点；
然后在重建左子树，找到左子树的根节点，重建右子树，找到右子树的根节点，递归下去；
中序+后续遍历重建树也是如此；
后续序列的最后一个元素就是树的根节点。

1.2 源代码

#include<stdio.h>
#include<Windows.h>

typedef char ElemType;
typedef struct Node{
  ElemType elem;
  struct Node *LChild;
  struct Node *RChild;
}BiTNode, *BiTree;

// 前序+中序重建二叉树
void ReBuildByPreAndInOrder(char *prelist, char *inlist, int len, BiTree *bt){
  if(!prelist || !inlist || len<=0 )    //空树 
    return;
  int i;
  
  // 找到根结点在中序遍历中的位置 
  for(i = 0; i < len; i++){
    if(inlist[i] == prelist[0])     
      break;           
  } 
  
  if(i>=len)
    return;
  
  // 初始化根结点 
  *bt = (BiTNode*)malloc(sizeof(BiTNode));
  if(!bt) // 申请失败
    return;
  (*bt)->LChild = (*bt)->RChild = NULL;
  (*bt)->elem = prelist[0];
  
  // 重建左子树
  ReBuildByPreAndInOrder(prelist+1, inlist, i, &(*bt)->LChild); 
  // 重建右子树 
  ReBuildByPreAndInOrder(prelist+i+1, inlist+i+1, len-i-1, &(*bt)->RChild);
}

// 中序+后序重建二叉树
void ReBuildByInAndPostOrder(char *inlist,char *postlist, int len, BiTree *bt){
  if(!inlist || !postlist || len<=0 )   //空树 
    return;
  int i;
  
  // 找到根结点在中序遍历中的位置 
  for(i = 0; i < len; i++){
    if(inlist[i] == postlist[len-1])      
      break;           
  } 
  
  if(i>=len)
    return;
  
  // 初始化根结点 
  *bt = (BiTNode*)malloc(sizeof(BiTNode));
  if(!bt)
    return;
  (*bt)->LChild = (*bt)->RChild = NULL;
  (*bt)->elem = postlist[len-1];
  
  //重建左子树 
  ReBuildByInAndPostOrder(inlist, postlist, i, &(*bt)->LChild);         
  //重建右子树 
  ReBuildByInAndPostOrder(inlist+i+1, postlist+i, len-i-1, &(*bt)->RChild);
}

void PrintTree(BiTree bt,int nLayer){
  int i;
  if(bt==NULL)
    return;
  PrintTree(bt->RChild,nLayer+1);
  for(i=0;i<nLayer;i++)
    printf(" ");
  printf("%c\n", bt->elem);
  PrintTree(bt->LChild,nLayer+1);
}

void main(){
  char pre[7]={'A', 'B', 'D', 'E', 'C', 'F', 'G'},
    inorder1[7] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'},
    inorder2[9] = {'G', 'D', 'H', 'B', 'A', 'E', 'C', 'I', 'F'},
    post[9] = {'G', 'H', 'D', 'B', 'E', 'I', 'F', 'C', 'A'};
  int i=0;

  /* 前序+中序重建二叉树 */
  printf("Give the preorder and midorder traversal of a binary tree: \nPreorder = ");
  for(i=0; i<7; i++){
    printf("%c  ", pre[i]);
  }
  printf("\nMidorder = ");
  for(i=0; i<7; i++){
    printf("%c  ", inorder1[i]);
  }

  BiTree T1=NULL;
  ReBuildByPreAndInOrder(pre, inorder1, 7, &T1);
  printf("\nThe binary tree constructed by two traversal sequences is: \n");
  PrintTree(T1, 1);
  /* 前序+中序重建二叉树 */

  /* 中序+后序重建二叉树 */
  printf("Give the midorder and postorder traversal of a binary tree: \nMidorder = ");
  for(i=0; i<9; i++){
    printf("%c  ", inorder2[i]);
  }
  printf("\nPostorder = ");
  for(i=0; i<9; i++){
    printf("%c  ", post[i]);
  }

  BiTree T2=NULL;
  ReBuildByInAndPostOrder(inorder2, post, 9, &T2);
  printf("\nThe binary tree constructed by two traversal sequences is: \n");
  PrintTree(T2, 1);
  /* 中序+后序重建二叉树 */

  system("pause");
}

1.3 运行情况截图

---

---

题目2

求二叉树中值为x的节点所在的层号。
二叉树bt采用二叉链表存储；
设计一个算法level（bt,x）求二叉树中值为x的节点所在的层号

2.1 算法设计思想

在求二叉树深度算法的基础上改进算法；
在含有目标节点的子树上查找，到达目标节点即结束递归

2.2 源代码

// 算法1
int layer(BiTree bt, char x){
  int cot = 0;
  if(bt==NULL)
    return cot;
  else if(bt->elem==x){
    cot = 1;
    return cot;
  }
  else{
    // printf("layer(bt->LChild, x): %d\n", layer(bt->LChild, x));
    if(layer(bt->LChild, x)){
      cot = layer(bt->LChild, x)+1;
      return cot;
    }
    // printf("layer(bt->RChild, x): %d\n", layer(bt->RChild, x));
    if(layer(bt->RChild, x)){
      cot = layer(bt->RChild, x)+1;
      return cot;
    }
  }
  return cot;
}

// 算法2
int find_node_level(BiTree bt, char x, int h){
  if (bt == NULL)
    return 0;
  else if (bt->elem == x)
    return h;
  else{
    int l = find_node_level(bt->LChild, x, h+1);
    if (l != 0)
      return l;
    else
      return find_node_level(bt->RChild, x, h+1);
  }
}

// 算法3
void level_in_x(BiTree BT,char x,int level){
  if (BT == NULL){
    return ;
  }
  if(BT->elem == x){
    printf("x in %d",level);
  }
  level++;
  printf("1:%d----\n", level);
  level_in_x(BT->LChild,x,level);
  printf("2:%d----\n", level);
  level_in_x(BT->RChild,x,level);
  printf("3:%d----\n", level);
  level--;
}

2.3 运行情况截图

---

---

题目3

求二叉树的宽度。
利用二叉树层次遍历求二叉树的宽度；
二叉树的宽度即二叉树同层结点数的最大值

3.1 算法设计思想

我利用一个足够大的全局数组来记录遍历过程中的二叉树宽度；
利用一个变量max来记录最大宽度，即为所求；
求宽度的函数依然采用的是先序遍历递归的思想，加一个形参k，对应width数组下标，记录当前深度，来传给子层信息；
如果当前深度k的节点不为空，那么width[k]++，来记录宽度；
max为宽度最大值

3.2 源代码

#define size 100

int width[size];
int max=0;

void MaxWidth(BiTree T,int k){
  if(T==NULL)
    return;
  width[k]++;
  if(max<width[k])
    max=width[k];
  MaxWidth(T->LChild, k+1);
  MaxWidth(T->RChild, k+1);
}

3.3 运行情况截图

---

---

题目4

二叉树bt采用二叉链表存储，设计算法实现采用括号表示法输出该二叉树。
            A
          /   \
        B     C
        /     / \
      D     E   F
        \
        G                        A(B(D(,G)),C(E,F))

4.1 算法设计思想

把题目中的括号表示法A(B(D(,G)),C(E,F))，去掉括号变为：
ABDGCEF
这种写法不是我们熟悉的先序遍历吗！
所以我就在二叉树先序遍历算法的基础上改进算法；

a.在节点的左右子树不为空时输出“（”；
b.当节点右子树不为空时输出“，”；
c.在节点的左右子树不为空时输出“）”

4.2 源代码

void Brackets(BiTree T){
  if (T==NULL)
    return;
  printf("%c", T->elem);
  if(T->LChild!=NULL||T->RChild!=NULL)
    printf("( ");
  Brackets(T->LChild);
  if(T->RChild!=NULL)
    printf(", ", T->elem);
  Brackets(T->RChild);
  if(T->LChild!=NULL||T->RChild!=NULL)
    printf(" )");
}

4.3 运行情况截图

---

---

题目5

求二叉树的路径长度。
二叉树二叉链表存储
二叉树的路径长度即：二叉树中所有结点的路径长度之和。
（结点的路径长度即：从根到结点的分支数）

5.1 算法设计思想

路径长度即为分支数之和；
根据二叉树的性质；
每个节点的头部都有一个分支，除了根节点；
所以分支数之和就是二叉树节点数-1；
那么采用递归的方法求得节点数，就可以求得路劲长度了

5.2 源代码

int Node(BiTree T){
  if (T==NULL)
    return 0;
  else{
    return 1 + Node(T->LChild) + Node(T->RChild);
  }
}

printf("The path length of this binary tree is: %d\n", Node(T)-1);

5.3 运行情况截图

---