㈠ 順序存儲是二叉樹常用的存儲結構嗎
二叉樹的存儲結構
二叉樹是非線性結構，即每個數據結點至多隻有一個前驅，但可以有多個後繼。它可採用順序存儲結構和鏈式存儲結構。
1．順序存儲結構
二叉樹的順序存儲，就是用一組連續的存儲單元存放二叉樹中的結點。因此，必須把二叉樹的所有結點安排成為一個恰當的序列，結點在這個序列中的相互位置能反映出結點之間的邏輯關系，用編號的方法從樹根起，自上層至下層，每層自左至右地給所有結點編號,缺點是有可能對存儲空間造成極大的浪費，在最壞的情況下，一個深度為k且只有k個結點的右單支樹需要2k-1個結點存儲空間。依據二叉樹的性質，完全二叉樹和滿二叉樹採用順序存儲比較合適，樹中結點的序號可以唯一地反映出結點之間的邏輯關系，這樣既能夠最大可能地節省存儲空間，又可以利用數組元素的下標值確定結點在二叉樹中的位置，以及結點之間的關系。圖5-5(a)是一棵完全二叉樹，圖5-5（b）給出的圖5-5(a)所示的完全二叉樹的順序存儲結構。
(a) 一棵完全二叉樹 (b) 順序存儲結構
圖5-5 完全二叉樹的順序存儲示意圖
對於一般的二叉樹，如果仍按從上至下和從左到右的順序將樹中的結點順序存儲在一維數組中，則數組元素下標之間的關系不能夠反映二叉樹中結點之間的邏輯關系，只有增添一些並不存在的空結點，使之成為一棵完全二叉樹的形式，然後再用一維數組順序存儲。如圖5-6給出了一棵一般二叉樹改造後的完全二叉樹形態和其順序存儲狀態示意圖。顯然，這種存儲對於需增加許多空結點才能將一棵二叉樹改造成為一棵完全二叉樹的存儲時，會造成空間的大量浪費，不宜用順序存儲結構。最壞的情況是右單支樹，如圖5-7 所示，一棵深度為k的右單支樹，只有k個結點，卻需分配2k－1個存儲單元。
(a) 一棵二叉樹 (b) 改造後的完全二叉樹
(c) 改造後完全二叉樹順序存儲狀態
圖5-6 一般二叉樹及其順序存儲示意圖
(a) 一棵右單支二叉樹 (b) 改造後的右單支樹對應的完全二叉樹
(c) 單支樹改造後完全二叉樹的順序存儲狀態
圖5-7 右單支二叉樹及其順序存儲示意圖
結構5-1二叉樹的順序存儲
#define Maxsize 100 //假設一維數組最多存放100個元素
typedef char Datatype; //假設二叉樹元素的數據類型為字元
typedef struct
{ Datatype bt[Maxsize];
int btnum;
}Btseq;
2．鏈式存儲結構
二叉樹的鏈式存儲結構是指，用鏈表來表示一棵二叉樹，即用鏈來指示元素的邏輯關系。
通常的方法是鏈表中每個結點由三個域組成，數據域和左右指針域，左右指針分別用來給出該結點左孩子和右孩子所在的鏈結點的存儲地址。其結點結構為：
其中，data域存放某結點的數據信息；lchild與rchild分別存放指向左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應指針域值為空（用符號∧或NULL表示）。利用這樣的結點結構表示的二叉樹的鏈式存儲結構被稱為二叉鏈表，如圖5-8所示。
(a) 一棵二叉樹 (b) 二叉鏈表存儲結構
圖5-8 二叉樹的二叉鏈表表示示意圖
為了方便訪問某結點的雙親，還可以給鏈表結點增加一個雙親欄位parent,用來指向其雙親結點。每個結點由四個域組成，其結點結構為：
這種存儲結構既便於查找孩子結點，又便於查找雙親結點；但是，相對於二叉鏈表存儲結構而言，它增加了空間開銷。利用這樣的結點結構表示的二叉樹的鏈式存儲結構被稱為三叉鏈表。
圖5-9給出了圖5-8 (a)所示的一棵二叉樹的三叉鏈表表示。
圖5-9二叉樹的三叉鏈表表示示意圖
盡管在二叉鏈表中無法由結點直接找到其雙親，但由於二叉鏈表結構靈活，操作方便，對於一般情況的二叉樹，甚至比順序存儲結構還節省空間。因此，二叉鏈表是最常用的二叉樹存儲方式。
結構5-2二叉樹的鏈式存儲
#define datatype char //定義二叉樹元素的數據類型為字元
typedef struct node //定義結點由數據域，左右指針組成
{ Datatype data;
struct node *lchild,*rchild;
}Bitree;
㈡ 樹的存儲結構轉換
//聲明樹中的類以及結點結構，文件名為tree.h
#ifndef TREE_H
#define TREE_H
template <class T>//樹中結點採用孩子兄弟表示法
struct TNode
{
T data;
TNode<T> *firstchild, *rightsib;
};
template <class T>
class Tree
{
public:
Tree( ); //構造函數，初始化一棵樹，其前序序列由鍵盤輸入
~Tree(void); //析構函數，釋放樹中各結點的存儲空間
TNode<T>* Getroot( ); //獲得指向根結點的指針
void PreOrder(TNode<T> *root); //前序遍歷樹
void PostOrder(TNode<T> *root); //後序遍歷樹
void LeverOrder(TNode<T> *root); //層序遍歷樹
private:
TNode<T> *root; //指向根結點的頭指針
void Release(TNode<T> *root); //析構函數調用
};
#endif
//定義類中的成員函數，文件名為tree.cpp
#include<iostream>
#include<string>
#include"tree.h"
using namespace std;
/*
*前置條件：樹不存在
*輸 入：無
*功 能：構造一棵樹
*輸 出：無
*後置條件：產生一棵樹
*/
template<class T>
Tree<T>::Tree( )
{
const int MaxSize = 100;
int end = 0;
int front = 0;
int rear = 0; //採用順序隊列，並假定不會發生上溢
int j = 0;
TNode<T>* queue[MaxSize]; //聲明一個隊列
TNode<T>* tempNode; //聲明指向結點類型的指針
TNode<T>* brotherNode; //工作指針
TNode<T>* q;
T ch;
cout<<"請輸入創建一棵樹的根結點數據"<<endl;
cin>>ch;
root = new TNode<T>;
root->data = ch;
root->firstchild = NULL;
root->rightsib = NULL;
queue[rear++] = root;
while (!end) //若繼續創建樹
{
T ch1,ch2;
cout<<"請輸入創建一棵樹的父結點數據和孩子結點數據"<<endl;
cin>>ch1>>ch2;
TNode<T>* p = new TNode<T>; //生成一個結點
p->data = ch2;
p->firstchild = NULL;
p->rightsib = NULL;
queue[rear++] = p;
tempNode = queue[front];//頭結點出隊，同時對頭元素的標識符後移
while(ch1 != tempNode->data)
tempNode = queue[front++];
if(tempNode->firstchild == NULL) tempNode->firstchild = p;
else{
brotherNode = tempNode->firstchild; //工作指針指向結點的第一個孩子
while (brotherNode != NULL) //若第一個孩子有兄弟結點
{
q = brotherNode;
brotherNode = brotherNode->rightsib;//工作指針指向第一個孩子的右兄弟
}
q->rightsib = p;
}
cout<<"創建結束? 如果結束請按1否則請按0 "<<endl;
cin>>end;
}
}
/*
*前置條件：樹已存在
*輸 入：無
*功 能：釋放樹中各結點的存儲空間
*輸 出：無
*後置條件：樹不存在
*/
template<class T>
Tree<T>::~Tree(void)
{
Release(root);
}
/*
*前置條件：樹已存在
*輸 入：無
*功 能：獲取指向樹根結點的指針
*輸 出：指向樹根結點的指針
*後置條件：樹不變
*/
template<class T>
TNode<T>* Tree<T>::Getroot( )
{
return root;
}
/*
*前置條件：樹已存在
*輸 入：無
*功 能：前序遍歷樹
*輸 出：樹中結點的一個線性排列
*後置條件：樹不變
*/
template<class T>
void Tree<T>::PreOrder(TNode<T> *root) //前序遍歷樹
{
if (root == NULL) return; //遞歸調用的結束條件
else{
cout<<root->data; //列印根節點
PreOrder(root->firstchild); //前序遞歸遍歷root的第一個孩子
PreOrder(root->rightsib); //前序遞歸遍歷root的右兄弟
}
}
/*
*前置條件：樹已存在
*輸 入：無
*功 能：後序遍歷樹
*輸 出：樹中結點的一個線性排列
*後置條件：樹不變
*/
template<class T>
void Tree<T>::PostOrder(TNode<T> *root)
{
if (root == NULL) return; //遞歸調用的結束條件
else{
PostOrder(root->firstchild); //後序遞歸遍歷root的第一個孩子
cout<<root->data; //列印出root結點
PostOrder(root->rightsib); //後序遞歸遍歷root的右兄弟
}
}
/*
*前置條件：樹已存在
*輸 入：無
*功 能：層序遍歷樹
*輸 出：樹中結點的一個線性排列
*後置條件：樹不變
*/
template<class T>
void Tree<T>::LeverOrder(TNode<T> *root)
{
const int MAX_QUEUE_SIZE = 100;
int front = 0;
int rear = 0; //採用順序隊列，並假定不會發生上溢
TNode<T>* queue[MAX_QUEUE_SIZE]; //聲明一個隊列
TNode<T>* tempNode; //聲明指向結點類型的指針
TNode<T>* brotherNode; //工作指針
if (root == NULL) return;//循環結束條件
queue[rear++] = root; //否則結點入隊
while (front != rear) //若隊列中有結點
{
tempNode = queue[front++];//頭結點出隊，同時對頭元素的標識符後移
cout<<tempNode->data; //列印出頭結點
brotherNode = tempNode->firstchild; //工作指針指向結點的第一個孩子
while (brotherNode != NULL) //若第一個孩子有兄弟結點
{
queue[rear++] = brotherNode; //第一個孩子結點入隊
brotherNode = brotherNode->rightsib;//工作指針指向第一個孩子的右兄弟
}
}
}
/*
*前置條件：樹已經存在
*輸 入：無
*功 能：釋放樹的存儲空間，析構函數調用
*輸 出：無
*後置條件：樹不存在
*/
template <class T>
void Tree<T>::Release(TNode<T>* root)
{
if (root != NULL){
Release (root->firstchild); //釋放第一個孩子
Release (root->rightsib); //釋放右兄弟
delete root;
}
}
//有關樹的實現的主函數，文件名為treemain.cpp
#include <iostream>
#include <string>
#include"tree.cpp"
using namespace std;
void main()
{
Tree<string> t; //創建一棵樹
TNode<string>* p = t.Getroot( ); //獲取指向根結點的指針
cout<<"------前序遍歷------ "<<endl;
t.PreOrder(p);
cout<<endl;
cout<<"------後序遍歷------ "<<endl;
t.PostOrder(p);
cout<<endl;
cout<<"------層序遍歷------ "<<endl;
t.LeverOrder(p);
cout<<endl;
}
㈢ 樹的存儲結構
常用的有：1、雙親表示，2、孩子鏈表表示，3、雙親孩子鏈表表示，4、孩子兄弟鏈表表示
㈣ 關於樹的孩子兄弟存儲結構
就是孩子兄弟鏈表中該結點的孩子構成的森林，自然是從firstchild開始
自己的高度肯定是孩子的最大高度加1
然後和兄弟的高度比較，留下最大值
㈤ 二叉樹的存儲結構是怎樣的有哪些類型的存儲結構對應的c語言描述是
樓上回答的是樹的存儲，不是二叉樹的存儲，主要如下：
1、順序存儲：適用於完全二叉樹，如果根從1開始編號，則第i結點的左孩子編號為2i，右孩子為2i+1，雙親編號為(i/2）下取整，空間緊密
2、二叉鏈表：適用於普通二叉樹，每個結點除了數據外，還有分別指向左右孩子結點的指針，存儲n個結點有n+1個空指針域，存儲密度小於順序存儲，但是適用范圍廣，缺陷是正常遍歷只能從雙親向孩子，退回來一般需要藉助棧（或者用遞歸，其實也是棧）
3、三叉鏈表：同樣適用於普通二叉樹，結點除了數據外，還有左右孩子與雙親的指針，存儲密度低於二叉鏈表，但是可以非常方便地在二叉樹中遍歷，不需要其他輔助工具
㈥ 樹的存儲表示是什麼
樹的存儲結構根據應用的不同而不同，有的從雙親的角度考慮，引出了雙親表示法，有的從孩子的角度考慮，給出孩子表示法，還有的從孩子和兄弟的角度來討論。這些都是人們在大量的應用中所使用的不同形式的存儲結構，這里介紹常用的雙親表示法、孩子表示法、雙親孩子表示法和孩子兄弟表示法。
1.雙親表示法由樹的定義可知，樹中每個結點都有且僅有一個雙親結點，根據這一特性，可以用一組連續的一維數組來存儲樹中的各個結點（一般按層次存儲），數組中的一個元素對應樹中的一個結點，其中包括結點的數據信息以及該結點的雙親在數組中的下標。樹的這種存儲方法稱為雙親表示法，雙親表示法的結點結構如圖1所示，其中，data表示數據域，存儲樹中結點的數據信息，parent表示指針域，存儲該結點的雙親在數組中的下標。
1.雙親表示法的存儲結構2）雙親表示法示例圖1所示的樹的雙親表示如圖1所示，這是一棵樹及其雙親表示法的存儲結構。根結點A無雙親，所以parent的值為－1，G、H和I的parent值為4，表示它們的雙親是下標為4的結點E。這種存儲結構利用任一結點的雙親是唯一的性質，可以方便地直接找到任一結點的雙親結點，但求結點的孩子結點時需要掃描整個數組。
圖1樹的雙親表示法示例
㈦ 樹的存儲方法主要有哪些
三叉鏈表不就是存儲結構，其具體實現既可以用指針實現，也可以用數組實現 至於遍歷方法可以任意地在二叉樹中上下
㈧ 完全二叉樹的存儲結構通常採用順序存儲結構()
正確。
一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，如果編號為i（1≤i≤n）的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹。
如果對滿二叉樹的結點進行編號, 約定編號從根結點起, 自上而下, 自左而右。則深度為k的, 有n個結點的二叉樹, 當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時, 稱之為完全二叉樹。
(8)樹的存儲結構擴展閱讀：
判斷一棵樹是否是完全二叉樹的思路
1、如果樹為空，則直接返回錯。
2、如果樹不為空：層序遍歷二叉樹。
如果一個結點左右孩子都不為空，則pop該節點，將其左右孩子入隊列。
如果遇到一個結點，左孩子為空，右孩子不為空，則該樹一定不是完全二叉樹。
如果遇到一個結點，左孩子不為空，右孩子為空；或者左右孩子都為空；則該節點之後的隊列中的結點都為葉子節點；該樹才是完全二叉樹，否則就不是完全二叉樹。
㈨ 數據結構，樹的常用存儲方式
存入文本文件，每行：孩子節點-父節點。
這樣也方便用Hadoop進行處理。
㈩ 樹的存儲結構，孩子鏈存儲表示法沒看懂求解釋
對於一般的家譜樹(一般的多叉樹)來說，我們可以很清楚的看出層次關系，樹的層數表示代數（一共多少代人），樹的最後一層表示最後一代人，由於多叉鏈表法表示的不方便，因此被迫無奈採用孩子兄弟表示法(二叉鏈表法).