Created
November 4, 2025 14:16
-
-
Save Coutlaw/22a6791bdaabdfb615c49fba01b823db to your computer and use it in GitHub Desktop.
Simple tree in Zig
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| const std = @import("std"); | |
| pub fn Node(comptime T: type) type { | |
| return struct { | |
| value: T, | |
| left_child: ?*Node, | |
| right_child: ?*Node, | |
| const Self = @This(); | |
| pub fn init(value: T) @This() { | |
| return .{ | |
| .left_child = null, | |
| .right_child = null, | |
| .value = value, | |
| }; | |
| } | |
| pub fn change_value(self: *Self, value: T) void { | |
| self.value = value; | |
| } | |
| pub fn is_leaf(self: *Self) bool { | |
| if (self.left_child || self.right_child) { | |
| return false; | |
| } | |
| return true; | |
| } | |
| }; | |
| } | |
| pub fn Tree(comptime T: type) type { | |
| return struct { | |
| root: ?*Node, | |
| allocator: std.mem.Allocator, | |
| const Self = @This(); | |
| pub fn init(allocator: std.mem.Allocator) !@This() { | |
| return .{ | |
| .root = null, | |
| .allocator = allocator, | |
| }; | |
| } | |
| // Chose to leave this as the public method so users don't have to pass in a node reference, | |
| // users are just exposed to the tree interface and not the nodes. | |
| // Also got to do a little tail recursion :) | |
| pub fn insert(self: *Self, value: T) !void { | |
| // Handle empty tree, set root node and move on | |
| if (self.root == null) { | |
| self.root.* = try self.allocator.create(Node(T).init(value)); | |
| return; | |
| } | |
| try insert_traversal(self.root, value); | |
| } | |
| // Used for recursive traversal to insert new values, a non public method | |
| fn insert_traversal(self: *Self, node: ?*Node, value: T) !void { | |
| // Base case, insert the node and refs | |
| if (node == null) { | |
| node.* = try self.allocator.create(Node(T)); | |
| node.*.init(value); | |
| return; | |
| } | |
| // this can't be null, safe to unwrap | |
| const current = node.?.*; | |
| // determine if we should insert left or right of parent node. | |
| if (value < current.value) { | |
| try insert_traversal(current.left_child, value); | |
| } else { | |
| // I chose to handle duplicates as right children, makes debuggin easiser | |
| try insert_traversal(current.right_child, value); | |
| } | |
| } | |
| // Removes the first occurance of a value T | |
| //pub fn remove(self: *Self, value: T) void { | |
| //} | |
| pub fn inorder_traversal_print(self: *Self) void { | |
| inorder_traverse(self.root); | |
| } | |
| fn inorder_traverse(root: ?*Node) void { | |
| if (root) |node| { | |
| if (node.*.left_child) { | |
| inorder_traverse(node.*.left_child); | |
| } | |
| std.debug.print("{d}\n", .{node.*.value}); | |
| if (node.*.right_child) { | |
| inorder_traverse(node.*.right_child); | |
| } | |
| } | |
| } | |
| }; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment