【资料结构】二元搜寻树:添加节点

说明

二元搜寻树:在节点的两个分支中，比较节点大小并存入左右

程式码

#include <stdio.h>#include <stdlib.h>typedef struct tree *tree_p;struct tree {  int data;  tree_p left;  tree_p right;  tree_p back;} tree;tree_p root = NULL, ptr, cur;tree_p add_node(int num);void inorder(tree_p root);void creat(int num);void basic1();

主程式

int main() {  basic1();  inorder(root);  printf("\n------------执行完成------------\n");  creat(6);  printf("\n------------添加节点------------\n");  inorder(root);  printf("\n------------执行完成------------\n");}

函式

void basic1():基本测资

void basic1() {  creat(4);  creat(2);  creat(9);  creat(1);  creat(3);  creat(7);  creat(5);  creat(8);}

void creat(int num):插入节点

进入迴圈判断，利用迴圈判定大小，不断向左右节点移动，当下一个节点为空白时，跳出迴圈，并在下一个节点新增。

void creat(int num) {  ptr = root;  cur = root;  if (root == NULL) {    root = add_node(num);  } else {    while (ptr != NULL) {      cur = ptr;      if (ptr->data < num) {        ptr = ptr->right;      } else if (ptr->data > num) {        ptr = ptr->left;      } else {        printf("same");      }    }    //cur会一直跟在ptr的后一格    //在存入节点时，判断大小选择左右    if (cur->data < num) {      cur->right = add_node(num);      cur->right->back = cur;      //顺便新增back节点指向该节点的前一个位置    } else {      cur->left = add_node(num);      cur->left->back = cur;    }  }}

结果

(中序输出)