开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 数据结构 > 查看源码
12_6.c
资源名称：04722-x　[点击查看]
上传用户：wyn840322
上传日期：2007-01-13
资源大小：294k
文件大小：4k
源码类别：

数据结构

开发平台：

C/C++

12_6.c：源码内容
  1. /* ======================================== */
  2. /*    程式实例: 12_6.cpp                    */
  3. /*    二元树类别实作                        */
  4. /* ======================================== */
  5. #include <iostream.h>
  7. struct node                       /* 树的结构宣告       */
  8. {
  9.    int data;                      /* 节点资料           */
  10.    node *left;                    /* 指向左子树的指标   */
  11.    node *right;                   /* 指向右子树的指标   */
  12. };
  14. class binaryTree                  /* 二元树的类别宣告   */
  15. {
  16. private:
  17.    node *head;                    /* 根节点的指标       */
  18.    void inorder(node *ptr);       /* 成员函数:中序走访  */
  19. public:
  20.    binaryTree() { head = NULL; }  /* 建构函数宣告       */
  21.    void insertNode(int d);        /* 插入节点函数宣告   */
  22.    void printTree();              /* 显示二元树的节点   */
  23.    int search(int d);             /* 二元树的走访搜寻   */
  24. };
  26. /* ---------------------------------------- */
  27. /*  成员函数: 二元树中序走访                */
  28. /* ---------------------------------------- */
  29. void binaryTree::inorder(node *ptr)
  30. {
  31.     if ( ptr != NULL )             /* 终止条件           */
  32.     {
  33.        inorder(ptr->left);         /* 左子树             */
  34.        /* 列印节点内容       */
  35.        cout << "[" << ptr->data << "]"; 
  36.        inorder(ptr->right);        /* 右子树             */
  37.     }
  38. };
  40. /* ---------------------------------------- */
  41. /*  插入二元树的节点                        */
  42. /* ---------------------------------------- */
  43. void binaryTree::insertNode(int d)
  44. {
  45.    /* 建立新节点记忆体 */
  46.    node *temp = new node;           /* 建立新节点         */
  47.    node *current;                   /* 目前树节点指标     */
  48.    int inserted = 0;                /* 是否插入新节点     */
  50.    temp->data = d;                  /* 建立节点内容       */
  51.    temp->left = NULL;               /* 设定指标初值       */
  52.    temp->right = NULL;              /* 设定指标初值       */
  53.    if ( head == NULL )              /* 是否是根节点       */
  54.       head = temp;                  /* 根节点指标为新节点 */
  55.    else
  56.    {
  57.       current = head;               /* 保留目前树指标     */
  58.       while( !inserted )
  59.       {
  60.          /* 比较节点值   */
  61.  if ( current->data > temp->data )
  62.  {
  63.     if ( current->left == NULL ) /* 是否是最左的子节点 */
  64.     {
  65.        current->left = temp; /* 接起父子的链结     */
  66.        inserted = 1;         /* 已经插入 */
  67.     }
  68.     else
  69.        current = current->left;    /* 左子树      */
  70.  }
  71.  else
  72.  {
  73.     if ( current->right == NULL ) /* 是否是最右的子节点 */
  74.     {
  75.        current->right = temp; /* 接起父子的链结     */
  76.        inserted = 1;          /* 已经插入  */
  77.     }
  78.     else
  79.        current = current->right;   /* 右子树      */
  80.  }
  81.       }
  82.    }
  83. }
  85. /* ---------------------------------------- */
  86. /*  成员函数: 二元搜寻树的搜寻              */
  87. /* ---------------------------------------- */
  88. int binaryTree::search(int d)
  89. {
  90.    node *temp = head;
  91.    while ( temp != NULL )        /* 主回路             */
  92.    { 
  93.       if ( temp->data == d )     /* 找到了             */
  94.  return 1;
  95.       if ( temp->data < d )      /* 比较资料           */
  96.  temp = temp->right;     /* 右子树             */
  97.       else
  98.  temp = temp->left;      /* 左子树             */
  99.    }
  100.    return 0;                     /* 没有找到           */
  101. }   
  103. /* ---------------------------------------- */
  104. /*  成员函数: 中序走访列印二元树            */
  105. /* ---------------------------------------- */
  106. void binaryTree::printTree()
  107. {
  108.    inorder(head);                 /* 呼叫中序走访函数  */ 
  109. } 
  111. /* ---------------------------------------- */
  112. /*  主程式: 建立二元树且用中序走访列印出来. */
  113. /* ---------------------------------------- */
  114. void main()
  115. {
  116.    binaryTree btree;              /* 建立二元树物件     */
  117.    int i;
  119.    /* 二元树节点资料 */
  120.    int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
  121.    for ( i = 0; i < 9; i++ )      /* 用回路建立树状结构 */
  122.        btree.insertNode(data[i]); /* 插入二元树的节点   */
  123.    cout << "树的节点内容 n";
  124.    btree.printTree();             /* 中序走访二元树     */
  125.    cout << "n请输入搜索的数字: ";/* 输出数字           */
  126.    cin >> i;                      /* 输入数字           */
  127.    if ( btree.search(i) )         /* 搜寻输入的数字     */
  128.       cout << "找到节点! n";
  129.    else
  130.       cout << "没有找到节点! n";
  131. }