tree-二元樹的前中後追蹤&&最大最小值&樹葉

實作練習

說明

實習課的一個作業，混合了前中後序的追蹤，找最大最小值，找樹葉點。

有時間再一個一個分開。

函式

get_max_min:將每一次新增的值帶入，找出最大最小值

void get_max_min(int *max, int *min, int num) {
  if (*max < num) {
    *max = num;
  }
  if (*min > num) {
    *min = num;
  }
}

add_node:新增新的節點

tree_p add_node(int word) {
  tree_p add = (tree_p)malloc(sizeof(tree));
  add->data = word;
  add->left = NULL;
  add->right = NULL;
  return add;
}

呼叫這個函式時，會利用malloc產生一個節點空間，並利用存值，最後再回傳。

seach:利用走訪的方式尋找無延伸分支的節點

void seach(tree_p root) {
  if (root != NULL) {
    if (root->left == NULL && root->right == NULL) {
      printf("%d ", root->data);
    }
    //printf("(%d)", root->data);
    seach(root->left);
    seach(root->right);
  }
}

這邊是利用中序追蹤的方法，找出樹葉點(兩個分支皆為空)

show:show出來

void show(tree_p root, int max, int min) {
  printf("\n--------------------------------------\n");
  printf("\nPreorder  :");
  preorder(root);
  printf("\nInorder   :");
  inorder(root);
  printf("\npostorder :");
  postorder(root);
  printf("\nMAX:%d\n", max);
  printf("MIN:%d\n", min);
  printf("LeafNodes :");
  seach(root);
}

程式碼

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree *tree_p;
struct tree {
  int data;
  tree_p left;
  tree_p right;
} tree;

tree_p root;
tree_p ptr = root;
tree_p cur = ptr;
//相關結構與全域

int main() {
  int t = 0, num, max = 0, min = 100;
  while (1) {
    ptr = root;
    printf("Insert a number :");
    scanf("%d", &num);
    //基本輸入
    if (num == 0) {
      break;
    }
    //當輸入值為0時跳脫迴圈
    get_max_min(&max, &min, num);
    //每一次輸入後代入函式，判斷是否是最大最小
    if (root == NULL) {
      root = add_node(num);
    } else {
      while (ptr != NULL) {
        cur = ptr;
        if (ptr->data > num) {
          ptr = ptr->left;
        } else if (ptr->data < num) {
          ptr = ptr->right;
        } else {
          printf("\nalready exit.\n");
          break;
        }
      }
      //當節點沒碰到空白時，會一直往下跑
      //並依據大小值決定左右方向
      //當遇到空白節點時，cur為目前節點
      if (cur->data > num) {
        cur->left = add_node(num);
      } else{
        cur->right = add_node(num);
      }
    }
  }
  show(root, max, min);
  // 18 22 20 32 18 11 9 0(測資)
}