New Posts  All Forums:Forum Nav:

c++ binary tree help

post #1 of 4
Thread Starter 
Hello, im having trouble abstracting a tree structure. I have seen pictures but in the code it doesnt seem to look the same in my head.

i have this

struct treeNode
{
dataType data;
node<dataType> *right;
node<dataType> *left;
};

how does that become a tree? doesn't a tree have different levels? Is each insertion a new level? To me it seems confusing. to me it feels like a dual linked list. Thanks.
Valery
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5 2500k GA-P67A-UD4-B3 Radeon 7970 Reference G. Skill Sniper 
Hard DriveOptical DriveOSMonitor
Corsair NOVA SSD 64gb + 500gb Storage + 1TB Storag HP DVD burner Windows 7 64bit 37" 1080p60hz 
KeyboardPowerCaseMouse
Razer Blackwidow Ultimate Rosewill Lightning 1000W Single Rail LianLi PC-K58 Razer Spectre 
Mouse Pad
Razer Goliathus Speed 
  hide details  
Reply
Valery
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5 2500k GA-P67A-UD4-B3 Radeon 7970 Reference G. Skill Sniper 
Hard DriveOptical DriveOSMonitor
Corsair NOVA SSD 64gb + 500gb Storage + 1TB Storag HP DVD burner Windows 7 64bit 37" 1080p60hz 
KeyboardPowerCaseMouse
Razer Blackwidow Ultimate Rosewill Lightning 1000W Single Rail LianLi PC-K58 Razer Spectre 
Mouse Pad
Razer Goliathus Speed 
  hide details  
Reply
post #2 of 4
right and left are both pointers to subtrees. as you insert new nodes, the tree will expand. right and left are 1 level below the root. they can each have their own right and left subtrees which would be 2 levels below root. sorry if that isnt very clear.

http://math.hws.edu/eck/cs225/s03/binary_trees/

halfway down the page they explain how to insert new nodes into the tree.
Fractal Design
(15 items)
 
775 4 life
(15 items)
 
 
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix 
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64 
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W 
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer 
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400 
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi 
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5 
Mouse
Razor Abyssus 
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3 
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ... 
Power
9-cell plus Slice battery 
  hide details  
Reply
Fractal Design
(15 items)
 
775 4 life
(15 items)
 
 
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix 
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64 
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W 
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer 
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400 
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi 
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5 
Mouse
Razor Abyssus 
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3 
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ... 
Power
9-cell plus Slice battery 
  hide details  
Reply
post #3 of 4
Thread Starter 
thanks. I had a bit of an aha moment. You really cleared things up. Now working with trees will be much easier. I wasn't factoring in that the pointers were pointing to other elements just like the root. Now I understand. Thanks a million.
Valery
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5 2500k GA-P67A-UD4-B3 Radeon 7970 Reference G. Skill Sniper 
Hard DriveOptical DriveOSMonitor
Corsair NOVA SSD 64gb + 500gb Storage + 1TB Storag HP DVD burner Windows 7 64bit 37" 1080p60hz 
KeyboardPowerCaseMouse
Razer Blackwidow Ultimate Rosewill Lightning 1000W Single Rail LianLi PC-K58 Razer Spectre 
Mouse Pad
Razer Goliathus Speed 
  hide details  
Reply
Valery
(13 items)
 
  
CPUMotherboardGraphicsRAM
i5 2500k GA-P67A-UD4-B3 Radeon 7970 Reference G. Skill Sniper 
Hard DriveOptical DriveOSMonitor
Corsair NOVA SSD 64gb + 500gb Storage + 1TB Storag HP DVD burner Windows 7 64bit 37" 1080p60hz 
KeyboardPowerCaseMouse
Razer Blackwidow Ultimate Rosewill Lightning 1000W Single Rail LianLi PC-K58 Razer Spectre 
Mouse Pad
Razer Goliathus Speed 
  hide details  
Reply
post #4 of 4
Hey donkru,

I'm going to try to explain how binary trees work in the simplest of ways (even though it's already been explained extremely well by travesty the stud). At least, how I was taught them and it took me less than 2 hours to create a fully functioning program that reads in data from a file, figures out the height of the binary tree, and traverses the tree in-order, pre-order, and post-order.

Technically, a binary tree exists even when there are no nodes and leaves (left and right pointers), right? It's empty, but it's "there". So, the very first thing you should do is initialise a node pointed to by a Node pointer. However, it's going to initialise the data to 0 and the pointers to NULL (or 0 in C++). Thus, it's still empty but also initialised.

Code:
Node *rootPtr = new Node();
So, that's done. Then, you will have to begin inserting data and the pointer to the root into a member function

Code:
BinaryTree t;
t.insert(10, rootPtr);
which will check and see if the tree is empty or not and do work on it. For instance, if the root is not set (root == 0), the data passed into it will be set the root. If it's set, it will compare whether the data is greater than root (inserted to right leaf) or less than root (inserted to left leaf). Since traversing is easily done via recursion, you'd pass something like

Code:
if(data < root->data)
{
   if(ptr->left == 0)  // if left leaf is emtpy
      ptr->left = new Node(data);  // create new node
   else
      t.insert(data, ptr->left);  // otherwise loop again with the ptr pointing to left leaf
}
if the data is less than root or

Code:
t.insert(data, ptr->right);
if the data is greater than root.

*Not guaranteeing 100% accuracy with the statements.
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming