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

说明

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

程序码

#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;
    }
  }
}

结果

(中序输出)