Код
#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);
}
}
0 1 2 3 5 6 7 8 9
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");
}
}