四叉樹自適應加密

Ⅰ 求四叉樹完整建立和遍歷的運行代碼（c或c++）

一個四叉樹的實現代碼

class QuadTreeCode
{
public:
vector<int> m_Numbers;

/*判斷兩個四叉樹碼是否相等*/
bool operator ==( QuadTreeCode& tempTree )
{
if ( m_Numbers.size()!=tempTree.m_Numbers.size() )
{
return false;
}
else
{
for ( int i=0; i<m_Numbers.size(); i++ )
{
if ( m_Numbers[i]!=tempTree.m_Numbers[i])
{
return false;
}
}
}

return true;
}

/*返回四叉樹碼的長度*/
int GetLength()
{
return m_Numbers.size();
}

int operator[](int Index)
{
return m_Numbers[Index];
}

};

enum ChildType
{
UL = 0,
UR = 3,
LL = 1,
LR = 2
};
template<class T>
class QuadTreeNode
{
public:
T *m_pData;
QuadTreeNode *m_pUpperLeft,*m_pUpperRight,*m_pLowerLeft,*m_pLowerRight;
QuadTreeCode m_Code; //節點在樹中位置的編碼
QuadTreeNode ()
{
m_pData = NULL;
m_pUpperLeft = m_pUpperRight = m_pLowerLeft = m_pLowerRight = NULL;
}

~QuadTreeNode ()
{
delete m_pData;
}

/*返回子成員的地址*/
QuadTreeNode ** GetChild( ChildType ctype )
{
switch( ctype )
{
case ChildType::UL:
return &m_pUpperLeft;
break;

case ChildType::UR:
return &m_pUpperRight;
break;

case ChildType::LL:
return &m_pLowerLeft;
break;

case ChildType::LR:
return &m_pLowerRight;
break;
}
}
};

template<class T>
class QuadTree
{
public:
int m_nTreeDepth; //樹的深度
QuadTreeNode<T> *m_pHeadNode; //樹的頭部
QuadTree()
{
m_nTreeDepth = 0;
m_pHeadNode = NULL;
}

~QuadTree()
{
void (QuadTree::*func)(QuadTreeNode<T> *) ;
func = &QuadTree::DestroyNode;
PostOrderOperation( m_pHeadNode, func );
}

/*
後序遍歷方式操作四叉樹
*/
void PostOrderOperation( QuadTreeNode<T> * ptempNode, void (QuadTree<T>::*NodeOp)( QuadTreeNode<T> * ) )
{
if( ptempNode!=NULL )
{
PostOrderOperation( ptempNode->m_pLowerLeft, NodeOp );
PostOrderOperation( ptempNode->m_pLowerRight, NodeOp );
PostOrderOperation( ptempNode->m_pUpperLeft, NodeOp );
PostOrderOperation( ptempNode->m_pUpperRight, NodeOp );
(this->*NodeOp) ( ptempNode );
}
}

void DestroyNode( QuadTreeNode<T> * ptempNode )
{
delete ptempNode;
}

/*創建樹枝*/
void CreateBranch( QuadTreeNode<T>**ppNode , int TreeDepth, int CurrentDepth )
{
if( CurrentDepth>TreeDepth )
{
return;
}
else
{
QuadTreeNode<T> *pNewNode = new QuadTreeNode<T>;
*ppNode = pNewNode;
QuadTreeNode<T> **pTempNode;
CreateBranch( pNewNode->GetChild(ChildType::UL), TreeDepth, CurrentDepth+1 );
CreateBranch( pNewNode->GetChild(ChildType::UR), TreeDepth, CurrentDepth+1 );
CreateBranch( pNewNode->GetChild(ChildType::LL), TreeDepth, CurrentDepth+1 );
CreateBranch( pNewNode->GetChild(ChildType::LR), TreeDepth, CurrentDepth+1 );
}

}

/*按照四叉樹碼進行操作*/
bool OperateNodeByCode( QuadTreeCode code, void (*Op)( QuadTreeNode<T> *) )
{
QuadTreeNode* ptempNode = m_pHeadNode;
for( int i=0; i<code.GetLength(); i++ )
{
ptempNode = ptempNode->GetChild( code[i] );
if( ptempNode==NULL )
return false;
}
Op( ptempNode );
return true;
}

/*近創建內存結構，數據內容並未賦值*/
void CreateTree( int TreeDepth )
{
m_nTreeDepth = TreeDepth;
CreateBranch( &m_pHeadNode, TreeDepth, 0);
}
//virtual void CreateNode( QuadTreeNode<T> * ptempNode ) const = 0;
};

Ⅱ 決策樹（Decision Tree）

  決策樹（Decision Tree）是一種基本的分類與回歸方法，其模型呈樹狀結構，在分類問題中，表示基於特徵對實例進行分類的過程。本質上，決策樹模型就是一個定義在特徵空間與類空間上的條件概率分布。決策樹學習通常包括三個步驟： 特徵選擇 、 決策樹的生成 和 決策樹的修剪 。

  分類決策樹模型是一種描述對實例進行分類的樹形結構，決策樹由節點（node）和有向邊（directed edge）組成。節點有兩種類型：內部節點（internal node）和葉節點（leaf node）。內部節點表示一個特徵或屬性，葉節點表示一個類。

  利用決策樹進行分類，從根節點開始，對實例的某一特徵進行測試，根據測試結果將實例分配到其子節點；這時，每一個子節點對應著該特徵的一個取值。如此遞歸地對實例進行測試並分配，直至達到葉節點。最後將實例分到葉節點的類中。

  決策樹是給定特徵條件下類的條件概率分布，這一條件概率分布定義在特徵區間的一個劃分（partiton）上。將特徵空間劃分為互不相交的單元（cell）或區域（region），並在每個單元定義一個類的概率分布就構成了一個條件概率分布。決策樹的一條路徑對應劃分中的一個單元，決策樹所表示的條件概率分布由各個單元給定條件下類的條件概率分布組成。假設X為表示特徵的隨機變數，Y為表示類的隨機變數，那麼這個條件概率分布可以表示成P(Y|X)。X取值於給定劃分下單元的集合，Y取值於類的集合，各葉節點（單元）上的條件概率往往偏向於某一個類，即屬於某一類的概率較大，決策樹分類時將該節點的實例分到條件概率大的那一類去。也就以為著決策樹學習的過程其實也就是由數據集估計條件概率模型的過程，這些基於特徵區間劃分的類的條件概率模型由無窮多個，在進行選擇時，不僅要考慮模型的擬合能力還要考慮其泛化能力。

  為了使模型兼顧模型的擬合和泛化能力，決策樹學習使用正則化的極大似然函數來作為損失函數，以最小化損失函數為目標，尋找最優的模型。顯然從所有可能的決策樹中選取最優決策樹是NP完全問題，所以在實際中通常採用啟發式的方法，近似求解這一最優化問題： 通過遞歸的選擇最優特徵，根據該特徵對訓練數據進行劃分直到使得各個子數據集有一個最好的分類，最終生成特徵樹 。當然，這樣得到的決策樹實際上是次最優（sub-optimal）的。進一步的，由於決策樹的演算法特性，為了防止模型過擬合，需要對已生成的決策樹自下而上進行剪枝，將樹變得更簡單，提升模型的泛化能力。具體來說，就是去掉過於細分的葉節點，使其退回到父節點，甚至更高的節點，然後將父節點或更高的節點改為新的葉節點。如果數據集的特徵較多，也可以在進行決策樹學習之前，對數據集進行特徵篩選。

  由於決策樹是一個條件概率分布，所以深淺不同的決策樹對應著不同復雜度的概率模型，決策樹的生成對應模型的局部選擇，決策樹的剪枝對應著模型的全局選擇。

   熵（Entropy） 的概念最早起源於物理學，最初物理學家用這個概念度量一個熱力學系統的無序程度。在1948年， 克勞德·艾爾伍德·香農 將熱力學的熵，引入到 資訊理論 ，因此它又被稱為 香農熵 。在資訊理論中，熵是對不確定性的量度，在一條信息的熵越高則能傳輸越多的信息，反之，則意味著傳輸的信息越少。

  如果有一枚理想的硬幣，其出現正面和反面的機會相等，則拋硬幣事件的熵等於其能夠達到的最大值。我們無法知道下一個硬幣拋擲的結果是什麼，因此每一次拋硬幣都是不可預測的。因此，使用一枚正常硬幣進行若干次拋擲，這個事件的熵是一 比特 ，因為結果不外乎兩個——正面或者反面，可以表示為 0, 1 編碼，而且兩個結果彼此之間相互獨立。若進行 n 次 獨立實驗 ，則熵為 n ，因為可以用長度為 n 的比特流表示。但是如果一枚硬幣的兩面完全相同，那個這個系列拋硬幣事件的熵等於零，因為 結果能被准確預測 。現實世界裡，我們收集到的數據的熵介於上面兩種情況之間。

  另一個稍微復雜的例子是假設一個 隨機變數 X ，取三種可能值 ，概率分別為 ，那麼編碼平均比特長度是： 。其熵為 。因此<u>熵實際是對隨機變數的比特量和順次發生概率相乘再總和的</u> 數學期望 。

  依據玻爾茲曼H定理，香農把隨機變數X的熵 定義為：

  其中 是隨機變數X的信息量，當隨機變數取自有限樣本時，熵可以表示為：

  若 ，則定義 。

  同理可以定義條件熵 :

  很容易看出，條件熵（conditional entropy） 就是X給定條件下Y的條件概率分布的熵對X的數學期望。當熵和條件熵中的概率有極大似然估計得到時，所對應的熵和條件熵分別稱為檢驗熵（empirical entropy）和經驗條件熵（empirical conditional entropy）.

  熵越大，隨機變數的不確定性就越大，從定義可以驗證:

  當底數 時，熵的單位是 ；當 時，熵的單位是 ;而當 時，熵的單位是 .

  如英語有26個字母，假如每個字母在文章中出現的次數平均的話，每個字母的信息量 為：

  同理常用漢字2500有個，假設每個漢字在文章中出現的次數平均的話，每個漢字的信息量 為：

  事實上每個字母和漢字在文章中出現的次數並不平均，少見字母和罕見漢字具有相對較高的信息量，顯然，由期望的定義，熵是整個消息系統的平均消息量。

  熵可以用來表示數據集的不確定性，熵越大，則數據集的不確定性越大。因此使用 劃分前後數據集熵的差值 量度使用當前特徵對於數據集進行劃分的效果（類似於深度學習的代價函數）。對於待劃分的數據集 ，其劃分前的數據集的熵 是一定的，但是劃分之後的熵 是不定的， 越小說明使用此特徵劃分得到的子集的不確定性越小（也就是純度越高）。因此 越大，說明使用當前特徵劃分數據集 時，純度上升的更快。而我們在構建最優的決策樹的時候總希望能更快速到達純度更高的數據子集，這一點可以參考優化演算法中的梯度下降演算法，每一步沿著負梯度方法最小化損失函數的原因就是負梯度方向是函數值減小最快的方向。同理：在決策樹構建的過程中我們總是希望集合往最快到達純度更高的子集合方向發展，因此我們總是選擇使得信息增益最大的特徵來劃分當前數據集 。

  顯然這種劃分方式是存在弊端的，按信息增益准則的劃分方式，當數據集的某個特徵B取值較多時，依此特徵進行劃分更容易得到純度更高的數據子集，使得 偏小，信息增益會偏大，最終導致信息增益偏向取值較多的特徵。

  設 是 個數據樣本的集合，假定類別屬性具有 個不同的值： ,設 是類 中的樣本數。對於一個給定樣本，它的信息熵為：

  其中， 是任意樣本屬於 的概率，一般可以用 估計。

  設一個屬性A具有 個不同的值 ，利用屬性A將集合 劃分為 個子集 ，其中 包含了集合 中屬性 取 值的樣本。若選擇屬性A為測試屬性，則這些子集就是從集合 的節點生長出來的新的葉節點。設 是子集 中類別為 的樣本數，則根據屬性A劃分樣本的信息熵為：

  其中 , 是子集 中類別為 的樣本的概率。最後，用屬性A劃分樣本子集 後所得的 信息增益(Gain) 為：

  即，<u>屬性A的信息增益=劃分前數據的熵-按屬性A劃分後數據子集的熵</u>。 信息增益（information gain）又稱為互信息（matual information）表示得知特徵X的信息而使得類Y的信息的不確定性減少的程度 。信息增益顯然 越小， 的值越大，說明選擇測試屬性A對於分類提供的信息越多，選擇A之後對分類的不確定程度越小。

  經典演算法 ID3 使用的信息增益特徵選擇准則會使得劃分更偏相遇取值更多的特徵，為了避免這種情況。ID3的提出者 J.Ross Quinlan 提出了 C4.5 ,它在ID3的基礎上將特徵選擇准則由 信息增益 改為了 信息增益率 。在信息增益的基礎之上乘上一個懲罰參數。特徵個數較多時，懲罰參數較小；特徵個數較少時，懲罰參數較大（類似於正則化）。這個懲罰參數就是 分裂信息度量 的倒數 。

  不同於 ID3 和 C4.5 , CART 使用基尼不純度來作為特徵選擇准則。基尼不純度也叫基尼指數 , 表示在樣本集合中一個隨機選中的樣本被分錯的概率 則<u>基尼指數（基尼不純度）= 樣本被選中的概率 * 樣本被分錯的概率</u>。Gini指數越小表示集合中被選中的樣本被分錯的概率越小，也就是說集合的純度越高，反之，集合越不純。

樣本集合的基尼指數：
樣本集合 有m個類別， 表示第 個類別的樣本數量,則 的Gini指數為：

基於某個特徵劃分樣本集合S之後的基尼指數：
  CART是一個二叉樹，也就是當使用某個特徵劃分樣本集合後，得到兩個集合：a.等於給定的特徵值的樣本集合 ；b.不等於給定特徵值的樣本集合 。實質上是對擁有多個取值的特徵的二值處理。

對於上述的每一種劃分，都可以計算出基於劃分特=某個特徵值將樣本集合劃分為兩個子集的純度：

因而對於一個具有多個取值（超過2個）的特徵，需要計算以每個取值為劃分點，對樣本集合劃分後子集的純度 ( 表示特徵 的可能取值)然後從所有的劃分可能 中找出Gini指數最小的劃分，這個劃分的劃分點，就是使用特徵 對樣本集合 進行劃分的最佳劃分點。

參考文獻 ：

決策樹--信息增益，信息增益比，Geni指數的理解

【機器學習】深入理解--信息熵（Information Entropy）

統計學習方法 （李航）

  為了便於理解，利用以下數據集分別使用三種方法進行分類：

  在進行具體分析之前，考慮到收入是數值類型，要使用決策樹演算法，需要先對該屬性進行離散化。
  在機器學習演算法中，一些分類演算法（ID3、Apriori等）要求數據是分類屬性形式，因此在處理分類問題時經常需要將一些連續屬性變換為分類屬性。一般來說，連續屬性的離散化都是通過在數據集的值域內設定若干個離散的劃分點，將值域劃分為若干區間，然後用不同的符號或整數數值代表落在每個子區間中的數據值。所以，離散化最核心的兩個問題是：如何確定分類數以及如何將連續屬性映射到這些分類值。常用的離散化方法有 等寬法 ， 等頻法 以及 一維聚類法 等。

在實際使用時往往使用Pandas的 cut() 函數實現等寬離散化:

  可以看到與手工計算的離散化結果相同，需要注意的是，<u> 等寬法對於離群點比較敏感，傾向於不均勻地把屬性值分布到各個區間，導致某些區間數據較多，某些區間數據很少，這顯然不利用決策模型的建立。 </u>

使用四個分位數作為邊界點，對區間進行劃分：

<u> 等頻率離散化雖然避免了等寬離散化的數據分布不均勻的問題,卻可能將相同的數據值分到不同的區間以滿足每個區間具有相同數量的屬性取值的要求。 </u>

使用一維聚類的離散化方法後得到數據集為：

  在本次實例中選擇使用基於聚類的離散化方法後得到的數據集進行指標計算。為了預測客戶能否償還債務，使用A（擁有房產）、B（婚姻情況）、C（年收入）等屬性來進行數據集的劃分最終構建決策樹。

單身 ：

離婚 ：

已婚 ：

顯然，由B屬性取值'已婚'劃分得到的子數據集屬於同一個葉節點，無法再進行分類。
接下來，對由B屬性取值'單身'劃分得到的子數據集 再進行最優特徵選擇：

1）計算數據集 總的信息熵，其中4個數據中，能否償還債務為'是'數據有3，'否'數據有1,則總的信息熵：

2）對於A(擁有房產)屬性，其屬性值有'是'和'否'兩種。其中，在A為'是'的前提下，能否償還債務為'是'的有1、'否'的有0；在A為'否'的前提下，能否償還債務為'是'的有2、為'否'的有1，則A屬性的信息熵為：

3)對於B（婚姻情況）屬性，由於已被確定，在這個數據子集信息熵為0

4)對於C（年收入）屬性，其屬性值有'中等輸入'、'低收入'兩種。在C為'中等收入'的前提下，能否償還作為為'是'的有1,為'否'的有0；在C為'低收入'的前提下，能否償還作為為'是'的有2,為'否'的有1;則C屬性的信息熵為：

5）最後分別計算兩個屬性的信息增益值：


信息增益值相同，說明以兩個屬性對數據子集進行劃分後決策樹的純度上升是相同的，此時任選其一成為葉節點即可。
同理，對數據子集 進行最優特徵選擇，發現信息熵為0：
整理得到最終的決策樹：

Ⅲ 設完成二叉樹按層次（同一層自左至右）遍歷的演算法。

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"

typedef char ElemType;//定義二叉樹結點值的類型為字元型
const int MaxLength=10;//結點個數不超過10個

typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;

void CreateBiTree(BiTree &T){//按先序次序輸入，構造二叉鏈表表示的二叉樹T，空格表示空樹
// if(T) return;
char ch;
ch=getchar(); //不能用cin來輸入，在cin中不能識別空格。
if(ch==' ') T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}

void PreOrderTraverse(BiTree T){//先序遍歷
if(T){
cout<<T->data<<' ';
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍歷
if(T){
InOrderTraverse(T->lchild);
cout<<T->data<<' ';
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(BiTree T){//後序遍歷
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<' ';
}
}
void LevelOrderTraverse(BiTree T){//層序遍歷

BiTree Q[MaxLength];
int front=0,rear=0;
BiTree p;
if(T){ //根結點入隊
Q[rear]=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q[front]; //隊頭元素出隊
front=(front+1)%MaxLength;
cout<<p->data<<' ';
if(p->lchild){ //左孩子不為空，入隊
Q[rear]=p->lchild;
rear=(rear+1)%MaxLength;
}
if(p->rchild){ //右孩子不為空，入隊
Q[rear]=p->rchild;
rear=(rear+1)%MaxLength;
}
}

}
//非遞歸的先序遍歷演算法
void NRPreOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{
cout<<p->data;
stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top]; p=p->rchild; }
}
}
}
//非遞歸的中序遍歷演算法
void NRInOrder(BiTree bt)
{ BiTree stack[MaxLength],p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top>0)
{ while(p!=NULL)
{

stack[top]=p;
top++;
p=p->lchild;
}
if (top>0)
{ top--; p=stack[top];cout<<p->data; p=p->rchild; }
}
}
}
//非遞歸的後序遍歷演算法
/*bt是要遍歷樹的根指針，後序遍歷要求在遍歷完左右子樹後，再訪問根。
需要判斷根結點的左右子樹是否均遍歷過。
可採用標記法，結點入棧時，配一個標志tag一同入棧
(1：遍歷左子樹前的現場保護，2：遍歷右子樹前的現場保護)。
首先將bt和tag(為1)入棧，遍歷左子樹；
返回後，修改棧頂tag為2，遍歷右子樹；最後訪問根結點。*/

typedef struct
{
BiTree ptr;
int tag;
}stacknode;

void NRPostOrder(BiTree bt)
{
stacknode s[MaxLength],x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍歷左子樹
{
s[top].ptr = p;
s[top].tag = 1; //標記為左子樹
top++;
p=p->lchild;
}

while (top>0 && s[top-1].tag==2)
{
x = s[--top];
p = x.ptr;
cout<<p->data; //tag為R，表示右子樹訪問完畢，故訪問根結點
}

if (top>0)
{
s[top-1].tag =2; //遍歷右子樹
p=s[top-1].ptr->rchild;
}
}while (top>0);}
}//PostOrderUnrec

int BTDepth(BiTree T){//求二叉樹的深度
if(!T) return 0;
else{
int h1=BTDepth(T->lchild);
int h2=BTDepth(T->rchild);
if(h1>h2) return h1+1;
else return h2+1;
}
}

int Leaf(BiTree T){//求二叉樹的葉子數
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return(Leaf(T->lchild)+Leaf(T->rchild));
}

int NodeCount(BiTree T){//求二叉樹的結點總數
if(!T) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

void main(){
BiTree T;
T=NULL;
int select;
//cout<<"請按先序次序輸入各結點的值，以空格表示空樹(輸入時可連續輸入):"<<endl;
// CreateBiTree(T);
while(1){
cout<<"\n\n請選擇要執行的操作:\n";
cout<<"1.創建二叉樹\n";
cout<<"2.二叉樹的遞歸遍歷演算法（前、中、後）\n";
cout<<"3.二叉樹的層次遍歷演算法\n";
cout<<"4.求二叉樹的深度\n";
cout<<"5.求二叉樹的葉子結點\n";
cout<<"6.求二叉樹的結點總數\n";
cout<<"7.二叉樹的非遞歸遍歷演算法（前、中、後）\n"; //此項可選做
cout<<"0.退出\n";
cin>>select;
switch(select){
case 0:return;
case 1:
cout<<"請按先序次序輸入各結點的值，以空格表示空樹(輸入時可連續輸入):"<<endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n先序遍歷:\n";
PreOrderTraverse(T);
cout<<"\n中序遍歷:\n";
InOrderTraverse(T);
cout<<"\n後序遍歷:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout<<"\n層序遍歷:\n";
LevelOrderTraverse(T);
break;
case 4:
cout<<"二叉樹的深度為:\n";
cout<<BTDepth(T);
break;
case 5:
cout<<"\n葉子節點數:\n";
cout<<Leaf(T);
break;
case 6:
cout<<"總節點數:\n";
cout<<NodeCount(T);
break;
case 7:
if(!T) cout<<"未建立樹，請先建樹！";
else{
cout<<"\n先序遍歷:\n";
NRPreOrder(T);
cout<<"\n中序遍歷:\n";
NRInOrder(T);
cout<<"\n後序遍歷:\n";
NRPostOrder(T);
}
break;
default:
cout<<"請確認選擇項:\n";
}//end switch
}//end while

}
參考資料：找來的，你看看吧！

Ⅳ 劃分樹、傾斜樹、線段樹、平衡樹哪個不是數據結構

傾斜樹不是。
數據結構中提到的樹如下所示：
基礎類：二叉搜索（排序）樹,線索二叉樹,哈夫曼樹（最優二叉樹）,二叉堆
平衡樹類：AVL,紅黑樹,2-3樹,2-3-4樹,B樹,B+樹,B-樹,treap,SBT.
優先隊列類：左高樹（左偏樹,可並堆,斜堆）,雙端堆,斐波那契堆
集合類：並查集
區間樹類：線段樹,劃分樹,歸並樹,樹狀數組
字母樹類：字典樹,後綴樹.AC自動機演算法
動態樹類：伸展樹
計算幾何類：KD-tree （塊狀樹）,4叉樹
RMQ轉LCA：笛卡爾樹
圖論相關：最小生成樹,無根樹
其它：敗者樹,博弈樹

Ⅳ 設二叉樹T的度為4，其中度為1，2，3，4的結點的個數分別為4，2，1，1。則T中的葉子結點的個數為

葉子結點個數為8。

假設度為0的結點個數為n0,假設總的結點個數為N。

則依據邊來算結點總數為（邊的總數加1等於N）：

N=1*4+2*2+3*1+4*1+1=4+4+3+4+1=16(1)。

按照結點來算結點總數為（各度數結點的總和等於N）：

N=n0+4+2+1+1=n0+8(2)。

(2)-(1)得n0-8=0,因此n0=8即葉子結點個數為8。

除法的法則：

數的整除要記住，除式各項都要是整數。但是除數不等於0，商是整數無余。a÷b時可以說，數b能夠整除a，數a能被b整除。a是數b的倍數，b是數a的約數。如果要是求約數就去除以自然數，如果要是求倍數就去乘自然數。

能被2、5、3整除的數個位是0和5，一定能被5整除。個位是2、4、6、8、0，一定能被2整除。各個數位數字和，如果要是3倍數，一定能被3整除。

Ⅵ 一顆二叉樹前序遍歷和中序遍歷分別是ABDEGCFH、DBGEACHF,則此後序遍歷是請高手解釋怎麼得的，說明原理！

後序遍歷是DGEBHFCA。

前序遍歷的第一個節點為根節點，由前序遍歷可知，A為根節點。中序遍歷的根節點前面的節點均為左子樹的節點，所以左子樹上的節點為DBGE。

去掉根節點和左子樹節點，右子數節點為CHF。前序遍歷的第二個節點為B，由2知B為左子樹節點，所以B為左子樹的根節點。

在二叉樹中，求後序遍歷，先左後右再根，即首先遍歷左子樹，然後遍歷右子樹，最後訪問根結點。則該二叉樹的後序遍歷是DGEBHFCA。

(6)四叉樹自適應加密擴展閱讀：

除了先序遍歷、中序遍歷、後序遍歷外，還可以對二叉樹進行層序遍歷。設二叉樹的根節點所在層數為1，層序遍歷就是從所在二叉樹的根節點出發。

首先訪問第一層的樹根節點，然後從左到右訪問第2層上的節點，接著是第三層的節點，以此類推，自上而下，自左至右逐層訪問樹的結點的過程就是層序遍歷。

Ⅶ Fluent加密網格具體步驟,看到很多人說Fluent可以自適應加密網格，在adpat中可以實現，哪位高手告訴下具體

1、首先啟動FLUENT Meshing軟體。

Ⅷ 將一棵有100個結點的完全二叉樹從根這一層開始

將一棵有100個結點的完全二叉樹從根這一層開始，每一層上從左到右依次對結點進行編號，根結點的編號為1，則編號為49的結點的左孩子編號為98。

如果對滿二叉樹的結點進行編號，約定編號從根結點起，自上而下，自左而右。則深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應時，稱之為完全二叉樹。

(8)四叉樹自適應加密擴展閱讀：

葉子結點只能出現在最下層和次下層，且最下層的葉子結點集中在樹的左部。需要注意的是，滿二叉樹肯定是完全二叉樹，而完全二叉樹不一定是滿二叉樹。

如果遇到一個結點，左孩子不為空，右孩子為空；或者左右孩子都為空；則該節點之後的隊列中的結點都為葉子節點；該樹才是完全二叉樹，否則就不是完全二叉樹。

Ⅸ 地理信息系統計算題~跪求解題過程

答：
2，3，0，0，0； 2，2，2，0，0； 4，4，2，0，0； 4，4，4，2，0 。

1）、點：3， 面：4、0；線：2。
2）、假設方向代碼分別表示為：東=0，東北=1，北=2，西北=3，西=4，西南=5，南=6，東南=7。寫出線狀地物的鏈式編碼。 1，1，6，0，0，6，7
3）、行方向寫出一種遊程編碼方案。
（2，1），（3，1），（0，3）；（2，3），（0，2）；（4，2），（2，1），（0，2）；（4，3），（2，1），（0，1）
4）、最多分3層，最大層數是10。

Ⅹ 加密技術有哪幾種

採用密碼技術對信息加密，是最常用的安全交易手段。在電子商務中獲得廣泛應用的加密技術有以下兩種：

（1）公共密鑰和私用密鑰（public key and private key）

這一加密方法亦稱為RSA編碼法，是由Rivest、Shamir和Adlernan三人所研究發明的。它利用兩個很大的質數相乘所產生的乘積來加密。這兩個質數無論哪一個先與原文件編碼相乘，對文件加密，均可由另一個質數再相乘來解密。但要用一個質數來求出另一個質數，則是十分困難的。因此將這一對質數稱為密鑰對(Key Pair)。在加密應用時，某個用戶總是將一個密鑰公開，讓需發信的人員將信息用其公共密鑰加密後發給該用戶，而一旦信息加密後，只有用該用戶一個人知道的私用密鑰才能解密。具有數字憑證身份的人員的公共密鑰可在網上查到，亦可在請對方發信息時主動將公共密鑰傳給對方，這樣保證在Internet上傳輸信息的保密和安全。

（2）數字摘要(digital digest)

這一加密方法亦稱安全Hash編碼法（SHA:Secure Hash Algorithm）或MD5(MD Standards for Message Digest)，由Ron Rivest所設計。該編碼法採用單向Hash函數將需加密的明文「摘要」成一串128bit的密文，這一串密文亦稱為數字指紋(Finger Print)，它有固定的長度，且不同的明文摘要成密文，其結果總是不同的，而同樣的明文其摘要必定一致。這樣這摘要便可成為驗證明文是否是「真身」的「指紋」了。

上述兩種方法可結合起來使用，數字簽名就是上述兩法結合使用的實例。

3.2數字簽名(digital signature)

在書面文件上簽名是確認文件的一種手段，簽名的作用有兩點，一是因為自己的簽名難以否認，從而確認了文件已簽署這一事實；二是因為簽名不易仿冒，從而確定了文件是真的這一事實。數字簽名與書面文件簽名有相同之處，採用數字簽名，也能確認以下兩點：

a. 信息是由簽名者發送的。

b. 信息在傳輸過程中未曾作過任何修改。

這樣數字簽名就可用來防止電子信息因易被修改而有人作偽；或冒用別人名義發送信息；或發出（收到）信件後又加以否認等情況發生。

數字簽名採用了雙重加密的方法來實現防偽、防賴。其原理為：

（1） 被發送文件用SHA編碼加密產生128bit的數字摘要（見上節）。

（2） 發送方用自己的私用密鑰對摘要再加密，這就形成了數字簽名。

（3） 將原文和加密的摘要同時傳給對方。

（4） 對方用發送方的公共密鑰對摘要解密，同時對收到的文件用SHA編碼加密產生又一摘要。

（5） 將解密後的摘要和收到的文件在接收方重新加密產生的摘要相互對比。如兩者一致，則說明傳送過程中信息沒有被破壞或篡改過。否則不然。

3.3數字時間戳(digital time-stamp)

交易文件中，時間是十分重要的信息。在書面合同中，文件簽署的日期和簽名一樣均是十分重要的防止文件被偽造和篡改的關鍵性內容。

在電子交易中，同樣需對交易文件的日期和時間信息採取安全措施，而數字時間戳服務(DTS：digital time-stamp service)就能提供電子文件發表時間的安全保護。

數字時間戳服務（DTS）是網上安全服務項目，由專門的機構提供。時間戳（time-stamp）是一個經加密後形成的憑證文檔，它包括三個部分：1）需加時間戳的文件的摘要(digest)，2）DTS收到文件的日期和時間，3）DTS的數字簽名。

時間戳產生的過程為：用戶首先將需要加時間戳的文件用HASH編碼加密形成摘要，然後將該摘要發送到DTS，DTS在加入了收到文件摘要的日期和時間信息後再對該文件加密（數字簽名），然後送回用戶。由Bellcore創造的DTS採用如下的過程：加密時將摘要信息歸並到二叉樹的數據結構；再將二叉樹的根值發表在報紙上，這樣更有效地為文件發表時間提供了佐證。注意，書面簽署文件的時間是由簽署人自己寫上的，而數字時間戳則不然，它是由認證單位DTS來加的，以DTS收到文件的時間為依據。因此，時間戳也可作為科學家的科學發明文獻的時間認證。

3.4數字憑證(digital certificate, digital ID)

數字憑證又稱為數字證書，是用電子手段來證實一個用戶的身份和對網路資源的訪問的許可權。在網上的電子交易中，如雙方出示了各自的數字憑證，並用它來進行交易操作，那麼雙方都可不必為對方身份的真偽擔心。數字憑證可用於電子郵件、電子商務、群件、電子基金轉移等各種用途。

數字憑證的內部格式是由CCITT X.509國際標准所規定的，它包含了以下幾點：

(1) 憑證擁有者的姓名，

(2) 憑證擁有者的公共密鑰，

(3) 公共密鑰的有效期，

(4) 頒發數字憑證的單位，

(5) 數字憑證的序列號（Serial number），

(6) 頒發數字憑證單位的數字簽名。

數字憑證有三種類型：

(1) 個人憑證(Personal Digital ID)：它僅僅為某一個用戶提供憑證，以幫助其個人在網上進行安全交易操作。個人身份的數字憑證通常是安裝在客戶端的瀏覽器內的。並通過安全的電子郵件（S/MIME）來進行交易操作。

(2) 企業（伺服器）憑證（Server ID）：它通常為網上的某個Web伺服器提供憑證，擁有Web伺服器的企業就可以用具有憑證的萬維網站點(Web Site)來進行安全電子交易。有憑證的Web伺服器會自動地將其與客戶端Web瀏覽器通信的信息加密。

(3) 軟體（開發者）憑證（Developer ID）：它通常為Internet中被下載的軟體提供憑證，該憑證用於和微軟公司Authenticode技術（合法化軟體）結合的軟體，以使用戶在下載軟體時能獲得所需的信息。

上述三類憑證中前二類是常用的憑證，第三類則用於較特殊的場合，大部分認證中心提供前兩類憑證，能提供各類憑證的認證中心並不普遍