C Дерево – Код

2075 / C / Дерево / Код

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

struct node {
  int key_value;
  node *left;
  node *right;
};

node *root = NULL;

void Add(int key, node **leaf);
void Show(node *leaf);
int main() {
  int keys[] = { 5,3,7,1,8,7,6,9,0,2 };
  for (int i = 0; i < 10; i++) {
    Add(keys[i], &root);
  }

  Show(root);
  _getch();
  return 0;
}

void Add(int key, node **leaf) {

  if (*leaf == NULL) {
    *leaf = (node*)malloc(sizeof(node));
    (*leaf)->key_value = key;
    (*leaf)->left = NULL;
    (*leaf)->right = NULL;
  }
  else if (key < (*leaf)->key_value) 
  {
    Add(key, &(*leaf)->left);
  }
  else if (key > (*leaf)->key_value) 
  {
    Add(key, &(*leaf)->right);
  }
}

// in-order, симетричний, по зростанню

void Show(node *leaf) {
  if (leaf != NULL) {
    Show(leaf->left);
    printf(" %d ", leaf->key_value);
    Show(leaf->right);
  }
}

root - корінь дерева, знаходиться на 0 рівні
// Reverse in-order, по спаданню
Show(leaf->right);
printf(" %d ", leaf->key_value);
Show(leaf->left);
 
// Post-order, зворотний порядок
Show(leaf->left);
Show(leaf->right);
printf(" %d ", leaf->key_value);

// Pre-order, прямий порядок
printf(" %d ", leaf->key_value);
Show(leaf->left);
Show(leaf->right);

// Post-order, зворотний порядок
Show(leaf->left);
Show(leaf->right);
printf(" %d ", leaf->key_value);

// Видалити з головою
void destroy(node *root) {
  if (root != NULL) {
  destroy(root->left);
  destroy(root->right);
  free(root);
}

// root = NULL;

}

// Вивести по рівнях
#include <queue>

using namespace std;

void printLevelOrder(node *root)
{
  if (root == NULL) return;
  queue<node *> q;
  q.push(root);

  while (q.empty() == false)
  {
    int nodeCount = q.size();
    while (nodeCount > 0)
    {
      node *node = q.front();
      printf("%d ", node->key_value);
      q.pop();
      if (node->left != NULL)
        q.push(node->left);
      if (node->right != NULL)
        q.push(node->right);
      nodeCount--;
    }
    printf("\n");
  }
}