From Walloping Agouti, 1 Year ago, written in C++.
Embed
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef int T;
  6.  
  7. struct Node {
  8.     Node(T value){
  9.         data = value;
  10.         depth = 0;
  11.         height = 0;
  12.         parent = NULL;
  13.         left = NULL;
  14.         right = NULL;
  15.     }
  16.  
  17.     T data;
  18.     int depth;
  19.     int height;
  20.     Node * parent;
  21.     Node * left;
  22.     Node * right;
  23. };
  24.  
  25. bool isRoot(Node * n)
  26. {
  27.         if (n->parent == NULL) return true;
  28.         return false;
  29. }
  30.  
  31. bool isLeave(Node * n)
  32. {
  33.         if (n->left == NULL && n->right == NULL) return true;
  34.         return false;
  35. }
  36.  
  37. void Depth(Node * n)
  38. {
  39.         if (n == NULL)
  40.         {
  41.                 return;
  42.         }
  43.         else if (isRoot(n))
  44.         {
  45.                 n->depth = 0;
  46.                 Depth(n->left);
  47.                 Depth(n->right);
  48.         }
  49.         else
  50.         {
  51.                 Depth(n->left);
  52.                 Depth(n->right);
  53.                 n->depth = n->parent->depth + 1;
  54.         }
  55. }
  56.  
  57. void Height(Node * n)
  58. {
  59.         if (isLeave(n))
  60.         {
  61.                 n->height = 0;
  62.         }
  63.         else
  64.         {
  65.                 Height(n->left);
  66.                 Height(n->right);
  67.                 n->height = max(n->left->height, n->right->height) + 1;
  68.         }
  69. }
  70.  
  71. void inOrder(Node * n)
  72. {
  73.         if (n != NULL)
  74.         {
  75.                 inOrder(n->left);
  76.                 cout << n->data << " " << n->depth << " " << n->height << endl;
  77.                 inOrder(n->right);
  78.         }
  79. }
  80.  
  81. void insertNode(Node * n, int value)
  82. {
  83.         if (n == NULL)
  84.                 n = new Node(value);
  85.         else
  86.         {
  87.                 if (value > n->data)
  88.                 {
  89.                         if (n->right != NULL)
  90.                         {
  91.                                 return insertNode(n->right, value);
  92.                         }
  93.                         else
  94.                         {
  95.                                 Node * newNode = new Node(value);
  96.                                 n->right = newNode;
  97.                                 newNode->parent = n;
  98.                         }
  99.                 }
  100.                 else if (value < n->data)
  101.                 {
  102.                         if (n->left != NULL)
  103.                         {
  104.                                 if (n->left != NULL)
  105.                                 {
  106.                                         return insertNode(n->left, value);
  107.                                 }
  108.                                 else
  109.                                 {
  110.                                         Node * newNode = new Node(value);
  111.                                         n->left = newNode;
  112.                                         newNode->parent = n;
  113.                                 }
  114.                         }
  115.                 }
  116.         }
  117. }
  118.  
  119. Node * buildTestTree2()
  120. {
  121.         Node * n1 = new Node(10);
  122.        
  123.         return n1;
  124. }
  125.  
  126. int main()
  127. {
  128.         Node * root = buildTestTree2();
  129.  
  130.        Depth(root);
  131.        Height(root);
  132.  
  133.        insertNode(root, 5);
  134.        
  135.        inOrder(root); cout << endl;
  136.  
  137.        system("pause");
  138.        return 0;
  139. }