程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 《數據結構與算法分析》學習筆記（四）——樹ADT，數據結構adt

《數據結構與算法分析》學習筆記（四）——樹ADT，數據結構adt

編輯：C++入門知識

《數據結構與算法分析》學習筆記（四）——樹ADT，數據結構adt

一、二叉樹

1、定義

二叉樹是一棵樹，其中每個節點都不能多於2個兒子。

2、實現

typedef struct TreeNode *PtrToNode;
typedef PtrToNode Tree;
typedef char ElementType;


struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
};

3、通過後序表達式構造一個表達式樹

void bianli(Tree t)
{
    if (t)
    {
        bianli(t->Left);
        cout << t->Element << " ";
        bianli(t->Right);
    }
}

int main()
{

    char c;
    stack<Tree> treeStack;
    
    while (1)
    {
        cout << "Please enter a suffix expression!(the last must is ';')" << endl;
        cin >> c;
        if (c == ';')
        {
            break;
        }
        else
        {
            if (c == '+' || c == '-' || c == '*' || c == '/')
            {
                auto t2 = treeStack.top();
                treeStack.pop();
                auto t1 = treeStack.top();
                treeStack.pop();

                PtrToNode temp2 = new(struct TreeNode);

                temp2->Element = c;
                temp2->Left = t1;
                temp2->Right = t2;

                treeStack.push(temp2);

            }
            else
            {
                PtrToNode temp;
                temp = new(struct TreeNode);
                temp->Element = c;
                temp->Left = temp->Right = nullptr;
                treeStack.push(temp);
            }
        }
    }

    auto t = treeStack.top();
    bianli(t);
    
    return 0;
}

二、查找樹ADT

1、定義

對於樹中的每個節點X，它的左子樹中所有關鍵字值小於X的關鍵字值，它的右子樹中所有關鍵字值大於X的關鍵字值。

2、實現

#ifndef _Tree_H
#define _Tree_H

//結點結構的聲明~
struct TreeNode;

typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

typedef int ElementType;//關鍵字的類型

//一些方法的聲明
SearchTree MakeEmpty(SearchTree T);
Position Find(SearchTree, ElementType X);
Position FindMin(SearchTree T);
Position FindMxa(SearchTree T);
SearchTree Insert(ElementType X, SearchTree T);
SearchTree Delete(ElementType X, SearchTree T);
ElementType Retrieve(Position P);


#endif // !_Tree_H

struct TreeNode           //結點結構實現
{
    ElementType Element;
    SearchTree Left;
    SearchTree Right;

};

3、相關方法的實現

（1）清空~

清空記得要使用後序遍歷的方法，因為後序遍歷才能夠才能夠保證把所有子樹清完。

SearchTree MakeEmpty(SearchTree T)
{
    if (T)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        delete(T);
    }
    return nullptr;
}

（2）查找

就是比結點小的，就遞歸去找左子樹，大的去找右子樹

Position Find(SearchTree T, ElementType X)
{
    if (T)
    {
        if (T->Element == X)
        {
            return T;
        }
        else if (T->Element>X)
        {
            return Find(T->Left, X);
        }
        else
        {
            return Find(T->Right, X);
        }
    }
    
        return nullptr;

}

（3）找到最小的

一種方法就是不斷的遞歸去找它的左子樹，直到最後一個結點。

Position FindMin(SearchTree T)
{
    if (T)
    {
        if (T->Left == nullptr)
        {
            return T;
        }
        else
        {
            return FindMin(T);
        }
    }
    else
    {
        return nullptr;
    }
}

（3）找到最大的

當然，這種簡單的遞歸，可以用一個for循環就可以搞定了。

Position FindMax(SearchTree T)
{
    if (T != nullptr)
    {
        while (T->Right != nullptr)
        {
            T = T->Right;
        }
    }
    return T;
}

（4）插入

SearchTree Insert(ElementType X, SearchTree T)
{
    if (T == nullptr)       //空樹，就插入
    {
        T = new(struct TreeNode);
        if (T = nullptr)
        {
            cout << "Out of Space!" << endl;
        }
        else
        {
            T->Element = X;
            T->Left = T->Right = nullptr;
        }
    }
    else if (T->Element < X)    //比當前結點小的話，就往左邊插入。
    {
        T->Right = Insert(X, T->Right);
    }
    else if (T->Element>X)         //比當前結點大的話，就往後邊插入。
    {
        T->Left = Insert(T->Right);
    }
    else                         //一樣的話就說明已經有了
    {
        cout << "It has existed!" << endl;
    }

    return T;       //記得返回一下下
}

（5）刪除

SearchTree Delete(ElementType X, SearchTree T)
{
    if (T == nullptr)        //找到空樹，就停下來
    {
        cout << "Element not found!" << endl;
    }
    else if (X < T->Element)
    {
        Delete(X, T->Left);
    }
    else if (X>T->Element)
    {
        Delete(X, T->Right);
    }
    else if (T->Left&&T->Right)        //子樹都存在的時候，用右子樹中最小的來替代它。
    {
        auto t = FindMin(T->Right);
        T->Element = t->Element;
        T->Right = Delete(T->Element, T->Right);
    }
    else                          //只有一個子樹或者沒有的話，就很簡單，直接替代或者delete
    {
        auto t = T;
        if (T->Left == nullptr)
        {
            T = T->Right;
        }
        else if (T->Right == nullptr)
        {
            T = T->Left;
        }
        else
        {
            delete(T);
        }
    }
}

初中生自學數據結構需要什基礎？

一、數據結構定義的不同表述
數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。通常情況下，精心選擇的數據結構可以帶來更高的運行或者存儲效率。數據結構往往同高效的檢索算法和索引技術有關。
數據結構在計算機科學界至今沒有標准的定義。個人根據各自的理解的不同而有不同的表述方法：
Sartaj Sahni 在他的《數據結構、算法與應用》一書中稱：“數據結構是數據對象，以及存在於該對象的實例和組成實例的數據元素之間的各種聯系。這些聯系可以通過定義相關的函數來給出。”他將數據對象（data object）定義為“一個數據對象是實例或值的集合”。
Clifford A.Shaffer 在《數據結構與算法分析》一書中的定義是：“數據結構是 ADT（抽象數據類型 Abstract Data Type）的物理實現。”
Lobert L.Kruse 在《數據結構與程序設計》一書中，將一個數據結構的設計過程分成抽象層、數據結構層和實現層。其中，抽象層是指抽象數據類型層，它討論數據的邏輯結構及其運算，數據結構層和實現層討論一個數據結構的表示和在計算機內的存儲細節以及運算的實現。
二、數據結構的重要意義
一般認為，一個數據結構是由數據元素依據某種邏輯聯系組織起來的。對數據元素間邏輯關系的描述稱為數據的邏輯結構；數據必須在計算機內存儲，數據的存儲結構是數據結構的實現形式，是其在計算機內的表示；此外討論一個數據結構必須同時討論在該類數據上執行的運算才有意義。
在許多類型的程序的設計中，數據結構的選擇是一個基本的設計考慮因素。許多大型系統的構造經驗表明，系統實現的困難程度和系統構造的質量都嚴重的依賴於是否選擇了最優的數據結構。許多時候，確定了數據結構後，算法就容易得到了。有些時候事情也會反過來，我們根據特定算法來選擇數據結構與之適應。不論哪種情況，選擇合適的數據結構都是非常重要的。
選擇了數據結構，算法也隨之確定，是數據而不是算法是系統構造的關鍵因素。這種洞見導致了許多種軟件設計方法和程序設計語言的出現，面向對象的程序設計語言就是其中之一。
三、數據結構的研究內容

在計算機科學中，數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象（數據元素）以及它們之間的關系和運算等的學科，而且確保經過這些運算後所得到的新結構仍然是原來的結構類型。
“數據結構”作為一門獨立的課程在國外是從1968年才開始設立的。 1968年美國唐·歐·克努特教授開創了數據結構的最初體系，他所著的《計算機程序設計技巧》第一卷《基本算法》是第一本較系統地闡述數據的邏輯結構和存儲結構及其操作的著作。“數據結構”在計算機科學中是一門綜合性的專業基礎課。數據結構是介於數學、計算機硬件和計算機軟件三者之間的一門核心課程。數據結構這一門課的內容不僅是一般程序設計（特別是非數值性程序設計）的基礎，而且是設計和實現編譯程序、操作系統、數據庫系統及其他系統程序的重要基礎。
計算機是一門研究用計算機進行信息表示和處理的科學。這裡面涉及到兩個問題：信息的表示，信息的處理。
而信息的表示和組織又直接關系到處理信息的程序的效率。隨著計算機的普及，信息量的增加，信息范圍的拓寬，使許多系統程序和應用程序的規模很大，結構又相當復雜。因此，為了編寫出一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關系，這就是數據結構這門課所要研究的問題。眾所周知，計算機的程序是對信息進行加工處理。在大多數情況下，這些......余下全文>>