int INDEX_RANGE = 100; type Tree_t = struct { *Tree_t t_left, t_right; int t_a, t_b; }; *Tree_t Root; [INDEX_RANGE] *Tree_t B_Index; /* * initialize - set up the tree and index array */ proc initialize()void: unsigned INDEX_RANGE - 1 i; Root := nil; for i from 0 upto INDEX_RANGE - 1 do B_Index[i] := nil; od; corp; /* * freeTree - free the tree (good to do this, just on principle). */ proc freeTree(*Tree_t t)void: if t ~= nil then freeTree(t*.t_left); freeTree(t*.t_right); free(t); fi; corp; /* * insert - insert a pair into the tree. A pointer to the newly inserted * node is returned. (Recursive) */ proc insert(**Tree_t t; int a, b)*Tree_t: *Tree_t temp; if t* = nil then /* Create a new node and make the pointer which is pointed to by 'n' point to the newly created node. */ temp := new(Tree_t); temp*.t_left := nil; temp*.t_right := nil; temp*.t_a := a; temp*.t_b := b; t* := temp; temp elif a = t**.t_a then /* duplicate entry for a. Just use the new value for b. */ t**.t_b := b; t* elif a < t**.t_a then /* new a is less than old one - put it into left subtree */ insert(&t**.t_left, a, b) else /* new a is greater than old one - put it into right subtree */ insert(&t**.t_right, a, b) fi corp; /* * printTree - print out the pairs in order of the first member. Do this by * traversing the tree in "preorder". (Recursive) */ proc printTree(*Tree_t t)void: if t ~= nil then printTree(t*.t_left); writeln(t*.t_a : 6, t*.t_b : 7); printTree(t*.t_right); fi; corp; /* * printIndex - print out the pairs in order of the second member. Do this * by scanning the B_Index array. */ proc printIndex()void: unsigned INDEX_RANGE - 1 i; for i from 0 upto INDEX_RANGE - 1 do if B_Index[i] ~= nil then writeln(B_Index[i]*.t_a : 6, B_Index[i]*.t_b : 7); fi; od; corp; /* * main - initialize the tree, then read in and insert data. */ proc main()void: int a, b; initialize(); while write("pair: "); readln(a, b) do if b < 0 or b >= INDEX_RANGE then writeln("Second pair member out of range - try again."); else B_Index[b] := insert(&Root, a, b); fi; od; writeln("The tree sorted by the first member of the pairs:"); writeln(); printTree(Root); writeln(); writeln("The tree sorted by the second member of the pairs:"); writeln(); printIndex(); /* now go free the entire tree: */ freeTree(Root); corp;