binary tree and in-order traverse in c – dead wild, innit
intro
Oi, you lot! New to C and fancy summat a bit mad? We’re gonna sling together a lil program to make a binary tree—ya know, them branchy things where each spot’s got two kids at most—and then wander through it in-order, left-middle-right style. It’s dead tricky but proper ace—like when I was tryna map out my mates’ pub crawl routes (lost it after the third stop, too smashed). Great for getting your head round pointers and recursion in C without a right faff. Let’s have a butcher’s!
code bit
Here’s the code—nowt posh, just a quick job I chucked together. Shoved it in a box so it don’t look like a total shambles on your blog. take a gander:
#include
struct Node { // lil branch, innit
int data;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data) { // make a new branch
struct Node* node=(struct Node*)malloc(sizeof(struct Node));
node->data=data;
node->left=NULL;
node->right=NULL;
return node;
}
void inOrder(struct Node* root) { // wander in-order
if(root!=NULL) { // keep going if there’s summat
inOrder(root->left); // left first
printf("%d ",root->data); // then middle
inOrder(root->right); // then right
}
}
int main() { // nearly did void, ha!
struct Node* root=newNode(1); // top of the tree
root->left=newNode(2); // left kid
root->right=newNode(3); // right kid
root->left->left=newNode(4); // grandkid
root->left->right=newNode(5); // another grandkid
printf("in-order traverse: ");
inOrder(root); // show it off
printf("\n"); // forgot ; once, ugh!
free(root->left->left); // tidy up
free(root->left->right);
free(root->left);
free(root->right);
free(root);
return 0;
}
what ya get
Here’s what it chucks out when ya run it. I hard-coded a lil tree—worked bang on, mate!
how it works, kinda
Right, let’s have a natter bout this like we’re slumped at the boozer with a pint—or a bag of pork scratchings, coz I’m Hank Marvin again. I’ll spill it like my tatty old notes from when I was faffing with C. It’s a doddle once ya clock it, swear down!
1. them `#include` bits
This is me nicking my toolkit. `
2. `struct Node` malarky
`struct Node` is my lil branch—`int data` for the number, `struct Node* left` and `struct Node* right` for pointers to the kids. Like a family tree, innit!
3. `newNode` funtion
`newNode(int data)` makes a fresh branch. `malloc(sizeof(struct Node))` nabs memory, slaps `data` in, sets `left` and `right` to `NULL`, and chucks it back. Like growing a new twig!
4. `int main()` funtion
Gotta have a “main” to kick off—it’s like the door to my local. `int` means I’m lobbing a number out at the end (that `0` says “sorted, guv!”), and them curly `{}` lads keep it all snug. Nearly wrote `void main()`—old me was a right numpty!
5. making the tree: `root` and pals
`root=newNode(1)` starts the tree—top’s 1. `root->left=newNode(2)` and `root->right=newNode(3)` add kids, then `root->left->left=newNode(4)` and `root->left->right=newNode(5)` chuck in grandkids. Hard-coded a lil tree—1 at top, 2 left, 3 right, 4 and 5 under 2.
6. `inOrder` funtion
Here’s the guts! `inOrder(struct Node* root)` wanders through—`if(root!=NULL)` keeps it going if there’s summat. `inOrder(root->left)` hits the left branch first, `printf("%d ",root->data)` does the middle, then `inOrder(root->right)` hits the right. Recursion makes it bounce around—left, middle, right—like a pub crawl route!
7. chucking it out: `printf` and `inOrder`
`printf("in-order traverse: ")` sets it up, `inOrder(root)` does the wander, `printf("\n")` tidies it. Forgot a `;` once—CODE JUST DIED, and I was proper fuming!
8. `free` and `return 0` to scarper
`free(root->left->left)` and pals tidy up—gotta chuck out all the branches! Then `return 0;` is me legging it, like, “Ta-ta, we’re done!” It’s a C thing—means it all went smooth as a greased weasel.
And that’s yer lot! A cracking lil program to make a binary tree and traverse it in-order. Faff with it—chuck in a daft tree, tweak it to say “tree walk” if ya fancy. First time I ran this, I got 4 2 5 1 3 and thought “that’s bang on!”—dead chuffed, eh! You’re a star already, mate—keep smashing it! 😊
