數據結構樹順序存儲代碼

發布時間: 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-09 04:41:00 瀏覽：749

永劫無間伺服器為什麼那麼爛發布：2024-05-09 04:34:38 瀏覽：809

用哪個軟體配置華為企業路由器發布：2024-05-09 04:23:58 瀏覽：520

簡易腳本發布：2024-05-09 04:17:30 瀏覽：801

返校vlog腳本發布：2024-05-09 04:15:53 瀏覽：618

vps雲伺服器免費租用發布：2024-05-09 04:10:42 瀏覽：208

空調壓縮機排量發布：2024-05-09 04:08:42 瀏覽：539

android使用靜態庫發布：2024-05-09 04:05:40 瀏覽：213

原生安卓開機動畫在哪裡發布：2024-05-09 03:52:19 瀏覽：394

微信收藏在哪個文件夾發布：2024-05-09 03:47:03 瀏覽：826

數據結構樹順序存儲代碼

與數據結構樹順序存儲代碼相關的資訊