二叉樹：二叉搜尋樹的建立和插入

二叉搜尋樹又名二叉排序樹。

大概簡略的思維導圖如下，友善記憶特性

基本二叉搜尋樹建立過程如下

/*資料結構如下*/
typedef struct tree
{
  int data;
  struct tree *left = NULL;
  struct tree *right = NULL;
}Tree,*TreeNode;

/*Node 為二叉樹根節點，insert為插入的節點*/
void create_tree(TreeNode *node, Tree *insert) {
  if ((*node) -> data > insert -> data) {
    if ((*node) -> left) {
      create_tree(&(*node) ->left,insert);
    } else {
      (*node) -> left = insert;
    }
  } else {
    if ((*node)  -> right) {
      create_tree(&(*node) ->right, insert);
    } else {
      (*node)  -> right = insert;
    }
  }
}      

查找某一數值是否存在的過程如下:

bool search(Tree *node, int val) {
  if (node -> data == val) {
    return true;
  } 
  if (node -> data > val) {
    if (node -> left) {
      return search(node -> left, val);
    } else {
      return false;
    }
  } else {
    if (node -> right) {
      return search(node -> right, val);
    } else {
      return false;
    }
  }
}      

#include <iostream>
#include <stack>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


using namespace std;

typedef struct tree
{
  int data;
  struct tree *left = NULL;
  struct tree *right = NULL;
}Tree,*TreeNode;

void create_tree(TreeNode *node, Tree *insert) {
  if ((*node) -> data > insert -> data) {
    if ((*node) -> left) {
      create_tree(&(*node) ->left,insert);
    } else {
      (*node) -> left = insert;
    }
  } else {
    if ((*node)  -> right) {
      create_tree(&(*node) ->right, insert);
    } else {
      (*node)  -> right = insert;
    }
  }
}

void preOrder(Tree *node, int layer) {
  if (node == NULL) {
    return;
  }
  for (int i = 0;i < layer; ++i) {
    cout << "----";
  }
  cout << node -> data << endl;
  preOrder(node -> left,layer + 1);
  preOrder(node -> right, layer + 1);
}

bool search(Tree *node, int val) {
  if (node -> data == val) {
    return true;
  } 
  if (node -> data > val) {
    if (node -> left) {
      return search(node -> left, val);
    } else {
      return false;
    }
  } else {
    if (node -> right) {
      return search(node -> right, val);
    } else {
      return false;
    }
  }
}

int main(int argc, char const *argv[])
{
  Tree *node;
  TreeNode root;
  root = (Tree *)malloc(sizeof(tree));
  root -> data = 8;
  root -> left = NULL;
  root -> right = NULL;

  int n;
  int tmp;
  cin >> n;
  for (int i = 0;i < n; ++i) {
    node = (Tree *)malloc(sizeof(tree));
    cin >> tmp;
    node -> data = tmp;
    create_tree(&root, node);
  }

  cout << "preOrder" << endl;
  preOrder(root,0);
  string s = (search(root, 10)==1)?"success":"failed";
  cout << "\nsearch 10 in tree "<< s << endl;
  return 0;
}      

#輸入
5
3 1 19 2 9
#輸出
preOrder
8
----3
--------1
------------2
----19
--------9

search 10 in tree failed

#輸入
5
3 1 10 2 9  
#輸出  
preOrder
8
----3
--------1
------------2
----10
--------9

search 10 in tree success