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(测资)
}