API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 24th, 2014
132
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 14.61 KB | None | 0 0
raw download clone embed print report
  1. /****************************************************************************/
  2.  
  3. /* DSA tree program example D.F. ROSS */
  4.  
  5. /****************************************************************************/
  6.  
  7.  
  8.  
  9. /****************************************************************************/
  10.  
  11. /* include files and global data objects */
  12.  
  13. /****************************************************************************/
  14.  
  15. #include <stdio.h>
  16.  
  17. #include <stdlib.h>
  18.  
  19. #include <math.h>
  20.  
  21.  
  22.  
  23. /****************************************************************************/
  24.  
  25. /* define constants & types */
  26.  
  27. /****************************************************************************/
  28.  
  29. #define ARRLEN 100
  30.  
  31. #define NULLREF NULL
  32.  
  33.  
  34.  
  35. /****************************************************************************/
  36.  
  37. /* tree element definition (this is hidden!) */
  38.  
  39. /****************************************************************************/
  40.  
  41. typedef struct treenode * treeref;
  42.  
  43.  
  44.  
  45. typedef struct treenode
  46.  
  47. {
  48.  
  49. int value;
  50.  
  51. int height;
  52.  
  53. treeref LC;
  54.  
  55. treeref RC;
  56.  
  57. } treenode;
  58.  
  59.  
  60.  
  61. /****************************************************************************/
  62.  
  63. /* define tree instance */
  64.  
  65. /****************************************************************************/
  66.  
  67.  
  68.  
  69. static treeref T = (treeref) NULL;
  70.  
  71.  
  72.  
  73. /****************************************************************************/
  74.  
  75. /* define tree array */
  76.  
  77. /****************************************************************************/
  78.  
  79. static treeref treearray[ARRLEN];
  80.  
  81. /****************************************************************************/
  82.  
  83. /* basic operations on the tree */
  84.  
  85. /****************************************************************************/
  86.  
  87. static int is_empty(treeref T) { return T == NULLREF; }
  88.  
  89.  
  90.  
  91. static int get_value(treeref T) { return T->value; }
  92.  
  93. static int get_height(treeref T) { return T->height; }
  94.  
  95. static treeref get_LC(treeref T) { return T->LC; }
  96.  
  97. static treeref get_RC(treeref T) { return T->RC; }
  98.  
  99.  
  100.  
  101. static treeref set_value(treeref T, int v) { T->value = v; return T; }
  102.  
  103. static treeref set_height(treeref T, int h) { T->height = h; return T; }
  104.  
  105. static treeref set_LC(treeref T, treeref L) { T->LC = L; return T; }
  106.  
  107. static treeref set_RC(treeref T, treeref R) { T->RC = R; return T; }
  108.  
  109.  
  110.  
  111. /****************************************************************************/
  112.  
  113. /* create and initialise an element in the tree */
  114.  
  115. /****************************************************************************/
  116.  
  117. static treeref create_node(int v)
  118.  
  119. {
  120.  
  121. return set_RC(
  122.  
  123. set_LC(
  124.  
  125. set_height(
  126.  
  127. set_value(malloc(sizeof(treenode)), v),
  128.  
  129. 0),
  130.  
  131. NULLREF),
  132.  
  133. NULLREF);
  134.  
  135. }
  136.  
  137. /****************************************************************************/
  138.  
  139. /* basic operations on the tree */
  140.  
  141. /* LC, Node, RC - a RECURSIVE view of the tree */
  142.  
  143. /****************************************************************************/
  144.  
  145. static treeref node(treeref T) { return T; }
  146.  
  147. static treeref LC(treeref T) { return get_LC(T); }
  148.  
  149. static treeref RC(treeref T) { return get_RC(T); }
  150.  
  151.  
  152.  
  153. /****************************************************************************/
  154.  
  155. /* CONStruct a new tree from a LC, Node and RC */
  156.  
  157. /****************************************************************************/
  158.  
  159. static treeref cons(treeref LC, treeref N, treeref RC) {
  160.  
  161. set_LC(N, LC); set_RC(N, RC); return N;
  162.  
  163. }
  164.  
  165.  
  166.  
  167. /****************************************************************************/
  168.  
  169. /* FIND the height of the tree */
  170.  
  171. /****************************************************************************/
  172.  
  173. static int max(int a, int b) { return a>b ? a : b; }
  174.  
  175.  
  176.  
  177. static int b_height(treeref T)
  178.  
  179. {
  180.  
  181. if(T == NULL)
  182.  
  183. return 0;
  184.  
  185. else{
  186.  
  187. T->height = 1 + max(b_height(T->LC), b_height(T->RC));
  188.  
  189. return T->height;
  190.  
  191. }
  192.  
  193. }
  194.  
  195.  
  196.  
  197. /****************************************************************************/
  198.  
  199. /* FIND the minimum value node */
  200.  
  201. /****************************************************************************/
  202.  
  203. int min(treeref T)
  204.  
  205. {
  206.  
  207. if (LC(T) == NULL) return get_value(T);
  208.  
  209. else return min(LC(T));
  210.  
  211. }
  212.  
  213.  
  214.  
  215. /****************************************************************************/
  216.  
  217. /* ADD to the tree in BST order */
  218.  
  219. /****************************************************************************/
  220.  
  221. static treeref b_add(treeref T, treeref N)
  222.  
  223. {
  224.  
  225. return is_empty(T) ? N
  226.  
  227. : is_empty(N) ? T
  228.  
  229. : get_value(node(N)) < get_value(node(T)) ?
  230.  
  231. cons(b_add(LC(T), N), node(T), RC(T))
  232.  
  233. : get_value(node(N)) > get_value(node(T)) ?
  234.  
  235. cons(LC(T), node(T), b_add(RC(T), N))
  236.  
  237. : T;
  238.  
  239. }
  240.  
  241. /****************************************************************************/
  242.  
  243. /* REMove an element from the tree / BST order */
  244.  
  245. /****************************************************************************/
  246.  
  247. static treeref b_rem(treeref T, int v) //Remove given element from tree and return reordered tree
  248.  
  249. {
  250.  
  251. if (T == NULL){
  252.  
  253. printf("\n Value [%d] could NOT be removed! (not found...) ");
  254.  
  255. return NULL;
  256.  
  257. }
  258.  
  259. if (v == get_value(T)) {
  260.  
  261. // Remove node T
  262.  
  263. printf("\n Value [%d] removed! ", v);
  264.  
  265. if (LC(T) == NULL && RC(T) == NULL) return NULL;
  266.  
  267. if (LC(T) == NULL) return RC(T);
  268.  
  269. if (RC(T) == NULL) return LC(T);
  270.  
  271.  
  272.  
  273. // If there is 2 children
  274.  
  275. int tmp = min(RC(T));
  276.  
  277. // Copy tmp to T
  278.  
  279. set_value(T, tmp);
  280.  
  281.  
  282.  
  283. // Delete tmp from T right
  284.  
  285. set_RC(T, (b_rem(RC(T), tmp)));
  286.  
  287. return T;
  288.  
  289.  
  290.  
  291. }
  292.  
  293. else if (v < get_value(T)) return set_LC(T, (b_rem(LC(T), v)));
  294.  
  295. else return set_RC(T, (b_rem(RC(T), v)));
  296.  
  297. }
  298.  
  299. // Simple method, gets unbalanced easy
  300.  
  301. /*
  302.  
  303. if(is_empty(T)){
  304.  
  305. printf("\n Tree empty.. ");
  306.  
  307. return T;
  308.  
  309. }
  310.  
  311.  
  312.  
  313. if(v < get_value(T)){ // Check left child
  314.  
  315. printf("\n Checking left child: %d < %d ", v, get_value(T));
  316.  
  317. return cons(b_rem(LC(T), v), T, RC(T));
  318.  
  319. }
  320.  
  321.  
  322.  
  323. if(v > get_value(T)){ // Check right child
  324.  
  325. printf("\n Checking right child: %d > %d ", v, get_value(T));
  326.  
  327. return cons(LC(T), T, b_rem(RC(T), v));
  328.  
  329. }
  330.  
  331.  
  332.  
  333. return b_add(LC(T), RC(T));
  334.  
  335. */
  336.  
  337.  
  338.  
  339.  
  340.  
  341.  
  342.  
  343. /****************************************************************************/
  344.  
  345. /* FIND an element in the BST (Binary Search Tree) */
  346.  
  347. /****************************************************************************/
  348.  
  349. static int b_findb(treeref T, int v)
  350.  
  351. {
  352.  
  353. if (T == NULL){
  354.  
  355. printf("\n Value NOT found! ");
  356.  
  357. return -1;
  358.  
  359. }
  360.  
  361. if (v == get_value(T)) {
  362.  
  363. printf("\n Value found! ");
  364.  
  365. return 1;
  366.  
  367. }
  368.  
  369. else if (v < get_value(T)) return b_findb(get_LC(T),v);
  370.  
  371. else return b_findb(get_RC(T),v);
  372.  
  373. }
  374.  
  375.  
  376.  
  377. /****************************************************************************/
  378.  
  379. /* FIND the number of elements in the tree (cardinality) */
  380.  
  381. /****************************************************************************/
  382.  
  383. static int b_size(treeref T)
  384.  
  385. {
  386.  
  387. int elements = 1;
  388.  
  389.  
  390.  
  391. if(T == NULL)
  392.  
  393. return 0;
  394.  
  395.  
  396.  
  397. elements+=b_size(T->LC);
  398.  
  399. elements+=b_size(T->RC);
  400.  
  401.  
  402.  
  403. return elements;
  404.  
  405. }
  406.  
  407.  
  408.  
  409. /****************************************************************************/
  410.  
  411. /* display the tree ELEMENT */
  412.  
  413. /****************************************************************************/
  414.  
  415. static void b_disp_el(treeref T)
  416.  
  417. {
  418.  
  419. // if (!is_empty(T)) printf(" %2d[%d] ", get_value(node(T)), b_height(T));
  420.  
  421. if (!is_empty(T)) printf(" %2d ", get_value(node(T)));
  422.  
  423. else printf(" * ");
  424.  
  425. }
  426.  
  427.  
  428.  
  429. /****************************************************************************/
  430.  
  431. /* display the tree (pre-order) */
  432.  
  433. /****************************************************************************/
  434.  
  435. static void b_disp_pre(treeref T) {
  436.  
  437.  
  438.  
  439. if (!is_empty(T)){
  440.  
  441. b_disp_el(node(T));
  442.  
  443. b_disp_pre(LC(T));
  444.  
  445. b_disp_pre(RC(T));
  446.  
  447. }
  448.  
  449. }
  450.  
  451.  
  452.  
  453. /****************************************************************************/
  454.  
  455. /* display the tree (in-order) */
  456.  
  457. /****************************************************************************/
  458.  
  459. static void b_disp_in(treeref T) {
  460.  
  461. if (!is_empty(T)) {
  462.  
  463. b_disp_in(LC(T));
  464.  
  465. b_disp_el(node(T));
  466.  
  467. b_disp_in(RC(T));
  468.  
  469. }
  470.  
  471. }
  472.  
  473. /****************************************************************************/
  474.  
  475. /* display the tree (post-order) */
  476.  
  477. /****************************************************************************/
  478.  
  479. static void b_disp_post(treeref T) {
  480.  
  481. //printf("\n TO BE DONE b_disp_post");
  482.  
  483.  
  484.  
  485. if (!is_empty(T)){
  486.  
  487. b_disp_post(LC(T));
  488.  
  489. b_disp_post(RC(T));
  490.  
  491. b_disp_el(T);
  492.  
  493. }
  494.  
  495. }
  496.  
  497.  
  498.  
  499. /****************************************************************************/
  500.  
  501. /* display the treearray array */
  502.  
  503. /****************************************************************************/
  504.  
  505. static void b_disp_array()
  506.  
  507. {
  508.  
  509. int k, count;
  510.  
  511. printf(" Treearray is: ");
  512.  
  513. for(k = 0; k < 99; k++){
  514.  
  515. if(treearray[k] == NULL)
  516. printf("*");
  517. else
  518.  
  519. {
  520. printf("%d", treearray[k]);
  521. count++;
  522. }
  523. if(count == be_size())
  524. break;
  525.  
  526. }
  527.  
  528. printf("\n");
  529.  
  530. }
  531.  
  532.  
  533.  
  534. /****************************************************************************/
  535.  
  536. /* Tree to array via a treearray (breadth-first search) */
  537.  
  538. /****************************************************************************/
  539.  
  540. /* Transforms a binary tree to a sequence (including NULL (*) references) */
  541.  
  542. /* e.g. the following tree: 5 */
  543.  
  544. /* 2 7 */
  545.  
  546. /* * 3 6 * */
  547.  
  548. /* */
  549.  
  550. /* becomes: [5] [2] [7] [*] [3] [6] [*] */
  551.  
  552. /****************************************************************************/
  553.  
  554. static void T2Q(treeref T, int qpos) {
  555.  
  556.  
  557.  
  558. if(T != NULL){
  559. if(qpos < 99) {
  560.  
  561. treearray[qpos-1] = get_value(T);
  562.  
  563. printf("\n Arr[%d] = [%d]", qpos-1, get_value(T));
  564.  
  565. T2Q(LC(T), qpos*2);
  566.  
  567. T2Q(RC(T), qpos*2+1);
  568. }
  569.  
  570. }
  571.  
  572.  
  573.  
  574. }
  575.  
  576.  
  577.  
  578. /****************************************************************************/
  579.  
  580. /* display the tree in 2D */
  581.  
  582. /****************************************************************************/
  583.  
  584. /* step 1: transform the tree to an array (Q) using T2Q() above */
  585.  
  586. /* e.g. array [5] | [2] [7] | [*] [3] [6] [*] | etc. */
  587.  
  588. /* index (1) | (2) (3) | (4) (5) (6) (7) | (8) ... */
  589.  
  590. /* level (1) | (2) (2) | (3) (3) (3) (3) | (4) ... */
  591.  
  592. /* step 2: then print the nodes at each level of the tree to give */
  593.  
  594. /* 5 */
  595.  
  596. /* 2 7 */
  597.  
  598. /* * 3 6 * */
  599.  
  600. /****************************************************************************/
  601.  
  602. static void b_disp_2D()
  603.  
  604. {
  605.  
  606. T2Q(T, 1);
  607.  
  608.  
  609.  
  610. printf("\n TREE (%d nodes, height %d) is inorder: ", be_size(), be_height());
  611.  
  612. be_disp_in();
  613.  
  614. printf("\n");
  615.  
  616. be_disp_array();
  617.  
  618.  
  619.  
  620. // Pretty print the tree
  621.  
  622. int i = 0, count = 0, j = 1;
  623.  
  624. for(i; i < 99; i++){
  625.  
  626. if(i == (myPow(2, j)-2)/2){ // Indent
  627.  
  628. indent(j);
  629.  
  630. }
  631. if(count == be_size())
  632. break;
  633.  
  634. if(treearray[i] == NULL)
  635. printf("*");
  636. else
  637.  
  638. {
  639. printf("%d", treearray[i]);
  640. count++;
  641. }
  642.  
  643.  
  644. spacing(j); // Spacing on same line
  645.  
  646. if(i == myPow(2, j)-2){ // New line for childs
  647.  
  648. if(j < 6){
  649. printf("\n");
  650.  
  651. j++;
  652. }
  653. else{
  654. break;
  655. }
  656.  
  657. }
  658.  
  659. }
  660.  
  661.  
  662.  
  663. }
  664.  
  665.  
  666.  
  667. /*
  668.  
  669. Example print:
  670.  
  671.  
  672.  
  673. 5
  674.  
  675. 3 7
  676.  
  677. 1 4 6 8
  678.  
  679.  
  680. 2
  681. 4
  682. 8
  683.  
  684.  
  685. TODO: When numbers contain more than 1 digit they will get displaced..
  686.  
  687. */
  688.  
  689.  
  690.  
  691.  
  692.  
  693. void indent(int level){ // Indent calculated 2 ^ (max level - level) - 1
  694.  
  695. int i, n = myPow(2, be_height()-level);
  696.  
  697. for(i=0; i<n-1; i++)
  698.  
  699. printf(" ");
  700.  
  701.  
  702.  
  703. }
  704.  
  705.  
  706. void spacing(int level){ // Spacing calculated 2 ^ (max level - level + 1) - 1
  707.  
  708. int i, n = myPow(2, be_height()-level+1);
  709.  
  710. for(i=0; i<n-1; i++)
  711.  
  712. printf(" ");
  713.  
  714.  
  715.  
  716. }
  717.  
  718.  
  719.  
  720. int myPow(int base, int exponent) {
  721.  
  722. int i, n = 1;
  723.  
  724. for (i = 0; i < exponent; i++) {
  725.  
  726. n *= base;
  727.  
  728. }
  729.  
  730. return n;
  731.  
  732. }
  733.  
  734.  
  735.  
  736. /****************************************************************************/
  737.  
  738. /* public operations on the tree */
  739.  
  740. /****************************************************************************/
  741.  
  742. void be_disp_2D() { b_disp_2D(); }
  743.  
  744. void be_disp_array() { b_disp_array(); }
  745.  
  746.  
  747.  
  748. void be_disp_pre() { b_disp_pre(T); }
  749.  
  750. void be_disp_in() { b_disp_in(T); }
  751.  
  752. void be_disp_post() { b_disp_post(T); }
  753.  
  754.  
  755.  
  756. void be_add(int v) { T = b_add(T, create_node(v)); }
  757.  
  758. void be_rem(int v) { T = b_rem(T, v); }
  759.  
  760.  
  761.  
  762. int be_is_memberb(int v) { return b_findb(T, v); }
  763.  
  764. int be_size() { return b_size(T); }
  765.  
  766. int be_height() { return b_height(T); }
  767.  
  768. /****************************************************************************/
  769.  
  770. /* end of basic functions */
  771.  
  772. /****************************************************************************/
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!