设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 顺序存储二叉树
返回列表 发新帖
查看: 2156|回复: 0

[学习笔记] 顺序存储二叉树

[复制链接]
溯影
发表于 2018-5-1 11:30:57 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
《数据结构C++语言描述》 清华大学出版社    任燕编著

小弟改编程序使之可以运行，同时重载输出运算符，使之更加方便的显示顺序存储的二叉树

但是小弟感觉用这个程序好像有点像是用数组来意淫二叉树一样哈哈，就是一些数学关系

加油！
  1. #include <iostream>
  2. #include <assert.h>
  3. #include <cstdbool>
  4. #include <cstdlib>
  5. #define DEFAULT_SEQTREE 100

  7. using namespace std;

  9. template <typename elemtype>
  10. class SeqTree{
  11. public:
  12.         //顺序存储的树置空
  13.         void clear();

  15.         //取最后一个结点在顺序存储空间的下标
  16.         int getFinalIndex();

  18.         //返回树采用顺序存储的首地址
  19.         elemtype *getInitialAddress();

  21.         //取下标为i的结点（就是第i+1个结点)
  22.         elemtype getNode(int i);

  24.         //重载赋值运算符
  25.         SeqTree operator=(SeqTree<elemtype> right);

  27.         //设置最后一个结点在顺序存储空间的下标
  28.         void setFinalIndex(int i);

  30.         //设置下标为i的结点（就是第i+1个结点）的值
  31.         void setNode(int i, elemtype value);

  33.         //构造函数
  34.         SeqTree();

  36.         //析构函数
  37.         virtual ~SeqTree();

  39.         //拷贝初始化构造函数
  40.         SeqTree(const SeqTree<elemtype> &seqT);

  42.         //重载输出运算符
  43.         template <typename out_put>
  44.         friend ostream& operator<<(ostream& out,SeqTree<out_put> other);


  47. protected:
  48.         elemtype *initialAddress;                //树的顺序存储空间的首地址
  49.         int finalIndex;                                        //按层次存放，最后一个结点在顺序存储空间的下标
  50. };


  53. //把一棵树顺序存储的空间置空
  54. template <typename elemtype>
  55. void SeqTree<elemtype>::clear(){
  56.         if (initialAddress){
  57.                 delete[] initialAddress;
  58.         }
  59.         initialAddress = NULL;
  60.         finalIndex = -1;
  61. }

  63. //取最后一个结点在顺序存储空间的下标
  64. template <typename elemtype>
  65. int SeqTree<elemtype>::getFinalIndex(){
  66.         return finalIndex;
  67. }

  69. //返回树的存储的首地址
  70. template <typename elemtype>
  71. elemtype* SeqTree<elemtype>::getInitialAddress(){
  72.         return initialAddress;
  73. }

  75. //取下标为i的结点
  76. template <typename elemtype>
  77. elemtype SeqTree<elemtype>::getNode(int i){
  78.         if (i<0 || i>finalIndex){                //如果溢出就退出
  79.                 cerr << OVERFLOW;
  80.                 exit(0);
  81.         }

  83.         return initialAddress[i];
  84. }


  87. //重载赋值运算符
  88. template <typename elemtype>
  89. SeqTree<elemtype> SeqTree<elemtype>::operator=(SeqTree<elemtype> right){
  90.         if (this != &right){
  91.                 finalIndex = right.finalIndex;
  92.                 if (finalIndex != -1){
  93.                         // 给左边的树申请一个一样大的存储空间
  94.                         initialAddress = new elemtype[finalIndex + 1];
  95.                         assert(initialAddress != 0);
  96.                         //把右边树的每个结点的数据域赋值给左边
  97.                         for (int i = 0; i <= finalIndex; i++){
  98.                                 initialAddress[i] = right.initialAddress[i];
  99.                         }
  100.                 }
  101.         }

  103.         return *this;                // 返回对象
  104. }


  107. //设置最后一个结点在顺序存储空间的下标
  108. template <typename elemtype>
  109. void SeqTree<elemtype>::setFinalIndex(int i){
  110.         finalIndex = i;
  111. }

  113. //设置下标为i的结点的值
  114. template <typename elemtype>
  115. void SeqTree<elemtype>::setNode(int i, elemtype value){
  116.         initialAddress[i] = value;
  117.         if (i > finalIndex){
  118.                 finalIndex = i;
  119.         }
  120. }

  122. //构造函数
  123. template <typename elemtype>
  124. SeqTree<elemtype>::SeqTree(){
  125.         initialAddress = new elemtype[DEFAULT_SEQTREE];
  126.         finalIndex = -1;
  127. }

  129. //析构函数
  130. template <typename elemtype>
  131. SeqTree<elemtype>::~SeqTree(){
  132.         clear();
  133.         cout << "清除完毕" << endl;
  134. }

  136. //拷贝初始化构造函数
  137. template <typename elemtype>
  138. SeqTree<elemtype>::SeqTree(const SeqTree<elemtype>& other){
  139.         initialAddress = NULL;
  140.         finalIndex = other.finalIndex;

  142.         if (finalIndex != -1){
  143.                 initialAddress = new elemtype[finalIndex + 1];
  144.                 assert(initialAddress != 0);

  146.                 for (int i = 0; i < finalIndex + 1; i++){
  147.                         initialAddress[i] = other.initialAddress[i];
  148.                 }
  149.         }
  150. }

  152. //重载输出运算符
  153. template <typename out_put>
  154. ostream& operator<<(ostream& out, SeqTree<out_put> other){
  155.         if (other.finalIndex != -1){
  156.                 for (int i = 0; i <= other.finalIndex; i++){
  157.                         out << other.initialAddress[i] << "\t";
  158.                 }
  159.                 return out;
  160.         }
  161.         else{
  162.                 cout << "树为空" << endl;
  163.         }
  164. }





  170. int main(void){
  171.         SeqTree<int> seq1;
  172.         for (int i = 0; i < 10; i++){
  173.                 seq1.setNode(i, i * 10);
  174.         }
  175.         cout << seq1 << endl;


  178.         cout << seq1.getNode(0) << endl;
  179.         cout << seq1.getNode(3) << endl;

  181.         SeqTree<int> seq2;
  182.         seq2 = seq1;
  183.         cout << seq2 << endl;//测试赋值运算符的重载
  184.         return 0;
  185. }



复制代码
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-4-16 19:32

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表