数据结构树顺序存储代码

发布时间: 2022-07-05 11:02:40

⑴ n个节点的完全二叉树顺序存储在一维数组a中,设计一个算法由此数组得到该完全二叉树的二叉链表结构.用c++写

程序代码如下：

#include<iostream>

#include<math.h>

#define MAX 100

using namespace std;

typedef char ElemType;

typedef struct node

{

ElemType data; //数据域

struct node *left; //左孩子指针

struct node *right; //右孩子指针

} BTNode;

//初始化二叉链表结点数组

void InitNodes(BTNode *nodes[], ElemType values[], int size)

{

int i;

for(i=0; i<size; i++)

{

nodes[i] = new BTNode();

nodes[i]->data = values[i];

}

//中序遍历二叉树

void MidOrderTravel(BTNode *root)

{

if(root != NULL)

{

MidOrderTravel(root->left);

cout<<root->data<<" ";

MidOrderTravel(root->right);

}

}

//根据二叉树的顺序存储结构，生成二叉树的二叉链表结构

BTNode *CreateBinaryTree(BTNode *nodes[], int size)

{

BTNode *root;

int i;

if(size < 1)

return NULL;

for(i=0; i<size; i++)

{

if(2*i+1 >= size)

nodes[i]->left = NULL;

else if(nodes[2*i+1]->data == ' ')

nodes[i]->left = NULL;

else

nodes[i]->left = nodes[2*i+1];

if(2*i+2 >= size)

nodes[i]->right = NULL;

else if(nodes[2*i+2]->data == ' ')

nodes[i]->right = NULL;

else

nodes[i]->right = nodes[2*i+2];

}

root = nodes[0];

return root;

}

void main()

{

ElemType values[] = {'A','B','C','D','E','F','G'};

//ElemType values[] = {'A','B','C',' ','D','E'};

BTNode *root;

BTNode *nodes[MAX];

int size = 7; //二叉树的顺序结构的大小

InitNodes(nodes, values, size);

root = CreateBinaryTree(nodes, size);

cout<<"中序遍历序列：";

MidOrderTravel(root);

cout<<end;

}

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

一棵二叉树至多只有最下面的两层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。

(1)数据结构树顺序存储代码扩展阅读

判断一棵树是否是完全二叉树的思路：

1、如果树为空，则直接返回错

2、如果树不为空：层序遍历二叉树；

3、如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；

4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；

5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树。

⑵ 数据结构创建一棵树的c语言代码怎么写

刚刚回答了一个类似的问题，以下代码供参考：
#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef char TElemType;
typedef int Status;
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;

//以下是建立二叉树存储结构，空节点输入作为#结束标识
Status CreateBiTree(BiTree &T) {
//请将该算法补充完整，参见第6章课件算法或课本
char ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;

} // CreateBiTree
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}

void Inorder(BiTree T)
{ // 中序遍历二叉树
//请将该算法补充完整，参见第6章课件算法
if(T)
{
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
void Postorder(BiTree T)
{ // 后序遍历二叉树
//请将该算法补充完整，参见第6章课件算法
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}

//以下是求叶子结点数
void CountLeaf(BiTree T,int& count){
//请将该算法补充完整，参见第6章课件算法
if(T){
if((!T->lchild)&&(!T->rchild))
count++;
CountLeaf(T->lchild,count);
CountLeaf(T->rchild,count);
}
}

//以下是求二叉树的深度
int Depth(BiTree T ){
//请将该算法补充完整，参见第6章课件算法
int depthval,depthLeft,depthRight;
if(!T) depthval=0;
else{
depthLeft = Depth(T->lchild);
depthRight = Depth(T->rchild);
if(depthLeft>depthRight)depthval = 1+depthLeft;
else depthval = 1+depthRight;
}
return depthval;
}

void main(){
BiTree T;
int s=0,d;
printf("\n creat of the bitree:\n");
CreateBiTree(T);
printf("\n output result of Preorder:\n");
Preorder(T);
CountLeaf(T,s);
d=Depth(T);
printf("\n leaves=%d\n",s);
printf("\n depth=%d\n",d);
}

⑶ 求数据结构 B-树与B+树及其操作的代码（C语言版）

那个叫二叉树啊
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
一、树的概述
树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。
（一）树的定义
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、......Tn，而且，
这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；
3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
5.树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5.
2
二叉树
1.二叉树的基本形态：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

⑷ 求数据结构顺序表完整代码

#include<stdio.h>#include<stdlib.h>#define OK 1#define ERROR 0#define OVERFLOW -2#define LIST_INIT_SIZE 100 /*线性表存储空间的初始分配量*/#define LISTINCREMENT 10 /*线性表存储空间的分配增量*/typedef int ElemType ;typedef int Status;typedef struct { ElemType * elem; /*存储空间基址*/ int length; /*当前长度*/ int listsize; /*当前分配的存储容量（以sizeof(ElemType)为单位）*/}SqList; Status InitList_Sq(SqList *LA){ /*构造一个空的线性表L。*/ (*LA).elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!(*LA).elem) exit (OVERFLOW); (*LA).length=0; (*LA).listsize=LIST_INIT_SIZE; return OK;} Status ListInsert_Sq(SqList *LA, int i, ElemType e){/*在顺序线性表L中第i个位置之前插入新的元素e, //i的合法值为1≤i≤Listlength_Sq(L)+1*/ ElemType *newbase, *q, *p;int n=0; /*定义局部变量*/ if(i<1||i> (*LA).length+1) return ERROR; /*值不合法*/ if((*LA).length>=(*LA).listsize){ /*当前空间已满，增加分配*/ newbase=(ElemType*)realloc((*LA).elem, ((*LA).listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit (OVERFLOW); /*存储分配失败*/ (*LA).elem=newbase; /*新基址*/ (*LA).listsize+=LISTINCREMENT;} /*增加存储容量*/ q=&((*LA).elem[i-1]); /*q为插入位置*/ for(p=&((*LA).elem[(*LA).length-1]);p>=q;--p){*(p+1)=*p;++n;} /*插入位置及之后的元素右移*/ printf("n=%d\n",n); *q=e; /*插入e*/ ++(*LA).length; return OK;} Status ListDelete_Sq(SqList *LA, int i, ElemType *e){/*在顺序线性表L中删除第i个元素，并用e返回其值 //i的合法值为1≤i≤Listlength_Sq(L)*/ ElemType *q, *p;int n=0; /*定义局部变量*/ if((i<1)||(i>(*LA).length)) return ERROR ; /*i值不合法*/ p=&((*LA).elem[i-1]); /*p为被删除元素的位置*/ *e=*p; /*被删除元素的值赋给e*/ q=(*LA).elem+(*LA).length-1; /*表尾元素的位置*/ for(++p;p<=q;++p) {*(p-1)=*p;++n;} /*被删除元素之后的元素左移*/ printf("n=%d\n",n); --(*LA).length; /*表长减1*/ return OK;} Status BuildList_Sq(SqList *LA){/*不断调用插入函数,在表尾插入数据元素，建立线性表*/ int i,e; scanf("%d",&e); while(e!=-1) {i=(*LA).length+1; /*表尾*/ ListInsert_Sq(LA,i,e); /*表尾插入*/ scanf("%d",&e);} return OK;} Status PrintList_Sq(SqList *LA){/*输出线性表*/ int i,len; len=(*LA).length; /*L长度->len*/ for(i=0;i<len;i++) printf("addr=%u, val=%d\n",&((*LA).elem[i]),(*LA).elem[i]); return OK;} void main( ){ SqList *LA; /*定义顺序表变量La*/ ElemType a, *e; printf("start...\n"); LA=(SqList *) malloc (1*sizeof(SqList)); InitList_Sq(LA); /*1创建空表*/ BuildList_Sq(LA); /*2建立非空表*/ PrintList_Sq(LA); /*显示表*/ scanf("%d",&a); /*输入要插入的元素*/ ListInsert_Sq(LA,1,a); /*3插入元素a*/ PrintList_Sq(LA); /*显示表*/ e=(ElemType *) malloc(1*sizeof(ElemType)); printf("\n"); ListDelete_Sq(LA,2,e); /*4 删除元素*/ PrintList_Sq(LA); /*显示表*/ printf("\n completed \n");}

⑸ 数据结构课程设计二叉排序树的实现用顺序和二叉链表作存储结构

用顺序和二叉链表作存储结构
（1）以回车('\\n')为输入结束标志,输入数列L/*以下是用c++
实现的二叉排序树的源代码*/
#include<iostream.h>
typedef

⑹ 数据结构的顺序表的代码

⑺ 输出二叉树树形的数据结构程序代码怎么写

下面这个算法能帮你：
/*二叉树的建立与遍历

以二叉链表作为存储结构，定义二叉树类型 bitree；

实现二叉树的以下运算

建立 create( ) 输入二叉树的结点元素，建立二叉链表。

选择一种遍历方式（先序、中序、后序）遍历这棵二叉树。 */
#include <stdio.h>
struct node
{
char data;
struct node *lchild,*rchild;
};

/****************************二叉树的创建*****************************/
struct node *creat_bintree(struct node *t)
{
char ch;
printf("\n 按照先序序列输入二叉树的每个值，空格代表空树:");
ch=getchar();
getchar();
if( ch==' ')
t=NULL;
else
{
t = (struct node *)malloc(sizeof(struct node));
t->data=ch;
t->lchild = creat_bintree( t->lchild );
t->rchild = creat_bintree( t->rchild );
}
return(t);
}
/****************************二叉树的先序遍历*****************************/
void preorder(struct node *t )
{
if (t)
{
putchar(t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/****************************二叉树的中序遍历*****************************/
void inorder(struct node *t )
{
if (t)
{
inorder(t->lchild);
putchar(t->data);
inorder(t->rchild);
}
}
/****************************二叉树的后序遍历*****************************/
void postorder(struct node *t )
{
if (t)
{
postorder(t->lchild);
postorder(t->rchild);
putchar(t->data);
}
}

void main()
{
struct node *t;
t=creat_bintree(t);
if (t)
{
printf("\n after preorder:\n");
preorder(t);
printf("\n after inorder:\n");
inorder(t);
printf("\n after postorder:\n");
postorder(t);
}
}

⑻ 算法与数据结构二叉树的顺序存储代码

1.应该是按照完全二叉树存的吧。这样的话，
2。根节点可以设置为1，（如果设成0的话，以后的所有值-1就可以了）
3，如果一个节点是x它左孩子是2*x,右孩子是2*x+1
4,所有叶子节点是，假设共有K个节点，这样则最后一个有叶子节点的是k/2,所以叶子节点就是[k/2+1,k];
5,顺序输出就可以了。

⑼ c语言二叉树的数组顺序存储

用数组存的话很简单
根节点存为a1
比如说当前节点为ai
那么左儿子存为a2*i
那么右儿子存为a2*i+1
这样可以保证每个点都存了并且无重复

阅读全文

热点内容

我的世界创造房子服务器发布：2024-05-20 06:48:36 浏览：818

小米笔记本存储不够发布：2024-05-20 06:32:53 浏览：784

dirt5需要什么配置发布：2024-05-20 06:02:58 浏览：543

怎么把电脑锁上密码发布：2024-05-20 05:19:09 浏览：985

安卓为什么连上wifi后没有网络发布：2024-05-20 05:17:50 浏览：419

安卓usb在设置哪里发布：2024-05-20 05:03:03 浏览：187

绥化编程发布：2024-05-20 04:59:44 浏览：991

基本原理和从头计算法发布：2024-05-20 04:50:32 浏览：30

配置情况指的是什么发布：2024-05-20 04:48:14 浏览：497

那个程序用来编译源文件发布：2024-05-20 04:46:45 浏览：551

数据结构树顺序存储代码

与数据结构树顺序存储代码相关的资讯