c++ - What is logic to construct a binary tree? -


i have while loop continuously takes integers until -1 entered. elements must inserted binary tree (not bst). if bst, have condition insert new node. how can construct binary tree?

i mean if nodes 1,2,3,4,5,6..., 1 root, 2 , 3 left , right children of node 1, 4 , 5 left , right children of node 2, , 6 left child of node 3, this:

if(root==null)     root= newnode;  else{     if (root->left==null)          root->left= insert(root->left,element);      else          root->right= insert(root->right,element);  } return root;

how create tree this?

the algorithm outlined whozcraig in comment can realized code:

/* create binary tree nodes presented in bfs order */ #include <cassert> #include <iostream> #include <vector> #include <iomanip>  using std::vector; using std::cout; using std::cin; using std::ostream; using std::setw;  struct node {     int data;     node *left;     node *right;     node(int n) : data(n), left(0), right(0) { } };  void print_bt(const node *root);  int main() {     vector<node> v;     int n;      // read data eof or negative value     while (cin >> n && n >= 0)         v.push_back(node(n));      // create binary tree     (size_t = 0; < v.size()/2; i++)     {         assert(2*i+1 < v.size());         v[i].left = &v[2*i+1];         if (2*i+2 < v.size())             v[i].right = &v[2*i+2];     }      // print binary tree     print_bt(&v[0]);      return 0; }  // print_bt() presents data if mentally rotate // output through 90º clockwise (so root @ top), // left child appears on left , right on right.  reversing // order of left/right leaves confusing. void print_bt(const node *root) {     static int level = 0;     if (root != nullptr)     {         level++;         print_bt(root->right);         cout << setw(4*level) << root->data << '\n';         print_bt(root->left);         level--;     } }

for example, given numbers 1 6 input, produces:

       3            6    1            5        2            4

and given numbers 1 15 input, produces:

              15            7               14        3               13            6               12    1               11            5               10        2                9            4                8

it helps if visualize tree rotated 90º clockwise, 1 @ top.


Comments

Post a Comment

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

i'm implementing inapp billing in android app. works well, however, i'm trying decouple broadcast receiver activity manifest. suggestion in android's trivialdrive sample: // important: dynamically register broadcast messages updated purchases. // register receiver here instead of <receiver> in manifest // because call getpurchases() @ startup, therefore can ignore // broadcasts sent while app isn't running. // note: registering listener in activity bad idea, done here // because sample. regardless, receiver must registered after // iabhelper setup, before first call getpurchases(). currently there's class extends broadcastreceiver : public class iabbroadcastreceiver extends broadcastreceiver { /** * intent action receiver should filter for. */ public static final string action = "com.android.vending.billing.purchases_updated"; private final iabbroadcastlistener mlistener; public iabbroadcastreceiver(iabbroadcastlistener listener) { m...
Read more

python Tkinter Capturing keyboard events save as one single string -

is possible store keyboard events 1 string? code below stores 1 char , prints it. card reader or bar code reader, contains collection of character/ string not 1 character @ time. goal save char pressed text variable. from tkinter import * root = tk() def key(event): text= event.char text+= event.char print ("pressed", text) def callback(event): frame.focus_set() print ("clicked at", event.x, event.y) frame = frame(root, width=100, height=100) frame.bind("<key>", key) frame.bind("<button-1>", callback) frame.pack() root.mainloop() currently, creating text variable , everytime key() function gets called, , text stores last character typed. you can define text module level variable , , use module level text inside key function - text = '' def key(event): global text text+= event.char print("pressed", text)
Read more

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -

here tables: create table customer ( cid int primary key, name varchar(32) ) create table ord ( oid int primary key, cid int foreign key references customer, address varchar(20) ) here's linq-to-sql statement: var aaa = c in db.customer select new { c, o = c.ord.tolist() }; and here's inexplicable query generated linq-to-sql: select [t0].[cid] [cid], [t0].[name] [name], [t1].[oid] [oid], [t1].[cid] [cid2], [t1].[address] [address], (select count(*) [dbo].[ord] [t2] [t2].[cid] = [t0].[cid]) [value] [dbo].[customer] [t0] left outer join [dbo].[ord] [t1] on [t1].[cid] = [t0].[cid] order [t0].[cid], [t1].[oid] i want understand how rid of count(*) part. it's entirely uncalled for! linq needs count(*) in order determine number of entries returned o = c.ord.tolist() .
Read more