From 18b53edf4a8b5a31fbc00f63775134a818de7fc6 Mon Sep 17 00:00:00 2001
From: soikk
Date: Sat, 30 Oct 2021 17:17:21 +0200
Subject: A simple collection of tree algorithms made while in school (lol)

---
 trees.c | 162 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 162 insertions(+)
 create mode 100644 trees.c

(limited to 'trees.c')

diff --git a/trees.c b/trees.c
new file mode 100644
index 0000000..590185c
--- /dev/null
+++ b/trees.c
@@ -0,0 +1,162 @@
+#include "trees.h"
+
+
+node_t* createNode(int val){
+  node_t *newNode = malloc(sizeof(node_t));
+  newNode->val = val;
+  newNode->left = NULL;
+  newNode->right = NULL;
+  return newNode;
+}
+tree_t* createTree(){
+  tree_t *newTree = malloc(sizeof(tree_t));
+
+  newTree->root = createNode(0);
+  return newTree;
+}
+
+int addNode(node_t *node, int val, const char lr){
+  if(lr == 'l'){
+    node->left = createNode(val);
+  }else if(lr == 'r'){
+    node->right = createNode(val);
+  }else{
+    return -1;
+  }
+  return 0;
+}
+
+int changeNode(node_t *node, int val){
+  if(node){
+    node->val = val;
+    return 0;
+  }
+  return -1;
+}
+
+void printNode(node_t node){
+  printf("( %d ", node.val);
+  if(node.left != NULL){
+    printf("L");
+    printNode(*node.left);
+  }
+  if(node.right != NULL){
+    printf("R");
+    printNode(*node.right);
+  }
+  printf(") ");
+}
+
+void printTree(tree_t tree){
+  printNode(*tree.root);
+}
+
+int nodeDepth(node_t *node){
+  int t = 0;
+  if(node){
+      int l = nodeDepth(node->left);
+      int r = nodeDepth(node->right);
+    t = 1 + ((l>r)?l:r);
+  }
+  return t;
+}
+int treeDepth(tree_t tree){
+  return nodeDepth(tree.root);
+}
+
+int nodeEndNodeCount(node_t *node){
+  int t = 0, l = 0, r = 0;
+  if(node){
+    if(!node->left && !node->right)
+      return 1;
+    else{
+	l = nodeEndNodeCount(node->left);
+	r = nodeEndNodeCount(node->right);
+    }
+    t = l + r;
+  }
+  return t;
+}
+
+int endNodeCount(tree_t tree){
+  return nodeEndNodeCount(tree.root);
+}
+
+int nodeContainsN(node_t *node, int n){
+  if(node){
+    if(node->val == n)
+      return 1;
+    else
+      return nodeContainsN(node->left, n) + nodeContainsN(node->right, n);
+  }
+  return 0;
+}
+
+int treeContainsN(tree_t tree, int n){
+  return nodeContainsN(tree.root, n);
+}
+
+int nodeNodeCount(node_t *node){
+  int t = 0;
+  if(node)
+    t = 1 + nodeNodeCount(node->left) + nodeNodeCount(node->right);
+  return t;
+}
+
+int nodeCount(tree_t tree){
+  return nodeNodeCount(tree.root);
+}
+
+void putNodeInArray(node_t *node, int *array, int *i){
+  if(node){
+    array = realloc(array, ((*i)+1)*sizeof(int));
+    array[*i] = node->val;
+    (*i)++;
+    putNodeInArray(node->left, array, i);
+    putNodeInArray(node->right, array, i);
+  }
+}
+int putTreeInArray(tree_t tree, int *array){
+  int i = 0;
+  putNodeInArray(tree.root, array, &i);
+  return i;
+}
+
+void sortArray(int *array, int len){
+  int sorted = 0;
+  while(!sorted){
+    int changes = 0;
+    for(int i = 0; i < len-1; i++){
+      if(array[i] > array[i+1]){
+	changes++;
+	array[i] += array[i+1];
+	array[i+1] = array[i] - array[i+1];
+	array[i] -= array[i+1];
+      }
+    }
+    if(!changes)
+      sorted = 1;
+  }
+}
+
+void insertInNode(node_t *node, int *array, int *i){
+  if(node->left)
+    insertInNode(node->left, array, i);
+  node->val = array[*i];
+  *i += 1;
+  if(node->right)
+    insertInNode(node->right, array, i);
+}
+
+void insertInTree(tree_t *tree, int *array){
+  int i = 0;
+  insertInNode(tree->root, array, &i);
+}
+
+void sortTree(tree_t *tree){
+  int *numbers = malloc(1*sizeof(int));
+  int t = putTreeInArray(*tree, numbers);
+  sortArray(numbers, t);
+  insertInTree(tree, numbers);
+  
+}
-- 
cgit v1.2.3