首页 > 编程语言 >二叉树用顺序表实现 C++代码实现

二叉树用顺序表实现 C++代码实现

时间:2023-08-27 11:38:26浏览次数:34  
标签:顺序 cout 实现 BITREE C++ SqBiTree int 二叉树


/*二叉树用顺序表实现*/

#include <iostream>
using namespace std;

/*完全二叉树顺序表的定义*/
#define MAX_BITREE_SIZE 100
typedef int SqBiTree[MAX_BITREE_SIZE];

/*创建一个二叉树顺序表*/
void CreateBiTree(SqBiTree &T)
{
    int i;
    cout<<"输入元素个数:";
    cin>>T[0];


    //cout<<T[0];
    for(i=1;i<=T[0];i++)
        cin>>T[i];
}

/*先序非递归遍历*/
void PreOrderBiTree(SqBiTree &T)
{
    int n;
    int i;
    int j;
    n=T[0];

    for(i=1;i<=n;i++)
    {
       if(i==1)
           j=1;
       else if(2*j<=n)
           j=2*j;
       else if(j%2==0&&j<n)
           j=j+1;
       else if(j>1)
       {
           while(j%2!=0||j==n)
               j=j/2;
           j=j+1;
       }//这里是难点,也是关键。
       cout<<T[j]<<" ";
    }
    cout<<endl<<endl;
}

/*后续非递归遍历*/
void PostOrderBiTree(SqBiTree &T)
{
    int i,n,j=1;
    n=T[0];

    for(i=1;i<=n;i++)
    {
        if(i==1)
            while(2*j<=n)
                j=2*j;
        else if(j%2==0&&j<n)
        {
            j=j+1;
            while(2*j<=n)
                j=2*j;
        }
        else if(j>1)
            j=j/2;
        cout<<T[j]<<" ";
    }
    cout<<endl;
}

void main()
{
       SqBiTree T;
       CreateBiTree(T);
       PreOrderBiTree(T);
       PostOrderBiTree(T);
}

书上写的程序代码有些地方是错的,幸亏我多测试了几组数据,找出来了这个错误,但刚开始时,实在不知道这个错误应该怎么去改,因此信心一度受到打击,且放下这个代码好几天,没有理它,今天下午又把它拿出来,静下心来,测试了几组数据,认真的观察了一下规律,就被我给写出来了,呵呵,真是高兴啊,解决了遗留下来的问题。

二叉树的顺序表,一般很少用,只有用到完全二叉树时,才能发挥它的优势,所以,学习二叉树的顺序表还是有一定用处的!

 

标签:顺序,cout,实现,BITREE,C++,SqBiTree,int,二叉树
From: https://blog.51cto.com/u_5173797/7251969

相关文章

  • 哈夫曼树及哈夫曼编码 C++代码实现
     /*哈夫曼编码*/#include<iostream>usingnamespacestd;//********************************//构造哈夫曼树//********************************/*哈夫曼树顺序表的定义*/typedefstruct{intweight;intparent,lchild,rchild;}HTNode;typedefH......
  • 用单链表解决约瑟夫问题 C语言实现
    编号为1,2,3,…,n的n个人按顺序针方向围坐一张圆桌旁,每个人手中持有一个密码(正整数)。首先输入一个正整数作为报数上限值m,然后,从第一个人开始按顺序针方向自1开始顺序报数,报到m的人离开桌子,并将他手中的密码作为新的m值,从顺序针方向的下一个就坐在桌旁的人开始重新从1报数,如此下去,直......
  • 稀疏矩阵的压缩存储及转置,快速转置法,C++代码实现
    /*稀疏矩阵的压缩存储及转置*/#include<iostream>usingnamespacestd;/*三元组顺序表的类型定义*/#defineitemSize100typedefstruct{introw,col;intitem;}thNode;typedefstruct{thNode*data;//data[0]不用intm,n,t;//分别表示行数、列......
  • 选择排序——简单选择排序和堆排序,C++代码实现
    #include<iostream>usingnamespacestd;typedefstruct{ intr[100+1]; intlength;}SqList;//简单选择排序voidSimpleSlectSort(SqList&L){ intmin,i,j; for(i=1;i<L.length;i++) { min=i; for(j=i+1;j<=L.length;j++) if(L.r[j]<L.r[m......
  • 循环队列的定义、入队、出队等操作 C++代码实现
    #include<iostream>usingnamespacestd;/*循环队列的类型定义*/constintQueue_Size=100;typedefstructcirclQueue{char*elem;intrear;intfront;intqueueSize;}circlQueue;/*初始化*/voidinitQueue_C(circlQueue&......
  • 顺序栈的定义、初始化、出栈、入栈等操作 C++代码实现
     #include<iostream>usingnamespacestd;/*顺序栈的定义*/#defineStack_Size100typedefstructsqStack{char*elem;inttop;intstackSize;//栈数组长度}sqStack;/*顺序栈的初始化*/voidinitStack_Sq(sqStack&S){S.elem=ne......
  • 用线性表实现的通讯录管理 C++代码
    /****************************************//*主控菜单处理测试程序main2.c************//***************************************/#include<iostream>#include<string>usingnamespacestd;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10intOK=......
  • 用单链表实现一元多项式相加 C++代码
     #include<iostream>usingnamespacestd;/*结点的定义*/typedefstructLNode{floatcoef;intexp;structLNode*next;}LNode;typedefLNode*Polynomial;/*多项式的初始化*/voidinitDuoX(Polynomial&Px){Px=newLNode;......
  • 双链表的定义、初始化、插入、删除,C++代码实现的算法
    #include<iostream>usingnamespacestd;/*双向链表类型定义*/typedefstructduNode{chardata;structduNode*prior;structduNode*next;}duNode;typedefduNode*duLinklist;//指针类型,故访问它的成员用“->”。/*初始化双向链表*/voidinitLinkl......
  • 链队列的实现,C++代码实现
    /*链队列的实现*/#include<iostream>usingnamespacestd;/*链队列类型定义*/typedefstructQNode{structQNode*next;chardata;}QNode,*queuePtr;//结点的定义typedefstructlinkQueue{queuePtrrear;queuePtrfront;}linkQueue;//队列的定......