Welcome, guest | Sign In | My Account | Store | Cart

This contains the insertion and deletion implement for the tri-nary tree data structure.

C++, 111 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
/*
 *
 * Implement insert and delete in a tri-nary tree
 *
 */


#include <iostream>

// data structure of Tri-Nary tree node
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *middle;
  TreeNode *right;
  TreeNode(int value):
    val(value), left(NULL), middle(NULL), right(NULL) {}
};

// data structure of Tri-Nary tree
class Tri_Nary_Tree {
  private:
    TreeNode *root;
    void insertNode(TreeNode *node, int value);
    TreeNode* deleteNode(TreeNode *node, int value);
    TreeNode* findSuccessor(TreeNode *node);
  public:
    Tri_Nary_Tree():root(NULL) {}
    void insertNode(int value);
    void deleteNode(int value);
};

void Tri_Nary_Tree::insertNode(int value) {
  if (root == NULL)
    root = new TreeNode(value);
  else
    insertNode(root, value);
}

void Tri_Nary_Tree::insertNode(TreeNode *node, int value) {
  if (node->val < value) {
    if (node->right)
      insertNode(node->right, value);
    else
      node->right = new TreeNode(value);
  }
  else if (node->val > value) {
    if (node->left)
      insertNode(node->left, value);
    else
      node->left = new TreeNode(value);
  }
  else {
    if (node->middle)
      insertNode(node->middle, value);
    else
      node->middle = new TreeNode(value);
  }
}

inline void Tri_Nary_Tree::deleteNode(int value) {
  root = deleteNode(root, value);
}

TreeNode* Tri_Nary_Tree::deleteNode(TreeNode *node, int value) {

  if (node == NULL)
    return node;

  if (node->val == value) {
    // three child nodes are all NULL
    if (node->left == NULL && node->right == NULL && node->middle == NULL) {
      delete node;
      return NULL;
    }
    if (node->middle) {
      node->middle = deleteNode(node->middle, value);
    }
    else {
      if (node->left && node->right) {  // both left and right exist
        TreeNode *successor_node = findSuccessor(node->right);
        node->val = successor_node->val;
        node->right = deleteNode(node->right, successor_node->val);
      }
      else if (node->left) {    // right child is empty
        TreeNode *new_node = node->left;
        delete node;
        return new_node;
      }
      else {                   // left child is empty
        TreeNode *new_node = node->right;
        delete node;
        return new_node;
      }
    }
  }
  else if (node->val < value)
    node->right = deleteNode(node->right, value);
  else
    node->left = deleteNode(node->left, value);

  return node;
}

// find the successor (in inorder traversal) in right child
TreeNode* Tri_Nary_Tree::findSuccessor(TreeNode *node) {
  if (node->left == NULL)
    return node;
  else
    return findSuccessor(node->left);
}
Created by Chen on Fri, 7 Feb 2014 (MIT)
C++ recipes (21)
Chen's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks