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