ツリーのC/C++実装

22925 ワード
C-C++
ツリーのC/C++実装
【クラスBiTreeでの変数コメント】
rootタイプ:BiTree*は、このノードが属するツリーの最上位ルートノードアドレスを格納し、ノード認証にも使用します.多くのメンバー関数はrootが空であるかどうかを検証し、空が正常でないノードであると判断した場合、それを操作せず、プログラムの安定性を保証します.
Dataタイプ:ElemTypeはノードの値を格納、ElemTypeはintがデフォルトであり、BiTreeを変更することができる.cppのtypedefは他のタイプに変更されました.
Lptrタイプ:BiTree*はノードの左サブノードアドレスを格納し、左サブノードが存在しない場合は空です.
Rptrタイプ:BiTree*はノードの右サブノードアドレスを格納し、右サブノードが存在しない場合は空です.
【クラスBiTreeでの関数コメント】
******ツリー操作関数部分************
bool BiTree::InitTree()ツリーを生成し、スタック領域にルートノードを割り当てる
bool BiTree::ClearTree()は、現在のノードをルートとするツリーのすべての値を初期値にリセットし、初期値はマクロ定義で決定します(ElemTypeがintの場合に使用します).
int BiTree::GetSize()現在のノードをルートとするツリーのノード数を取得する
int BiTree::GetDepth()現在のノードをルートとするツリーの深さを取得する
bool BiTree::IsEmptyTree()現在のノードをルートノードとするツリーが空かどうかを判断するとtrueに戻ります
bool BiTree::DestroyTree()現在のノードをルートノードとするツリーを破壊し、すべてのメモリ領域を解放
bool BiTree::ShowTree()は、ツリー全体を順番に呼び出しvisit()で表示します.
bool BiTree::TraverseTree(bool(*F)()、int flag)は木全体を遍歴し、関数Fに従って操作するとflagはPRE_を取ることができるORDER,IN_ORDER,POST_ORDER
*****ノード操作関数部*********
BiTree*BiTree::GetRoot()現在のノードがある(最上位レベル)ツリーのルートノード値を返します.
bool BiTree::Grow()は、現在のノードに2つの新しいサブノードを追加します.左右のサブノードが存在する場合falseが返されます.
bool BiTree::IsParent()は、現在のノードがルートノード(サブノードを持つ)であるかどうかを判断し、Yesはtrueを返します.
ElemType BiTree::GetValue()現在のノードの値を返します.
bool BiTree::visit()出力ウィンドウに現在のノードの値とその左右のサブノードアドレスを出力
bool BiTree::AssignValue(ElemType value)現在のノードのdataにvalueを割り当てる
BiTree*BiTree::LeftChild()現在のノードの左サブノードポインタを返します.
BiTree*BiTree::RightChild()現在のノードの右サブノードポインタを返します.
bool BiTree::InsertRight(BiTree*r)は、入力rが指すノードを現在のノードの左サブノードとする.現在のノードに左サブノードが既に存在する場合、元の左サブノードをrがノードを指す新しい左ノードとして、現在のノードの左側に1つのノードを挿入する機能を実現する.
bool BiTree::InsertLeft(BiTree*l)は、入力lが指すノードを現在のノードの左サブノードとする.現在のノードに左サブノードが既に存在する場合、元の左サブノードをlがノードを指す新しい左ノードとして、現在のノードの左側に1つのノードを挿入する機能を実現する.
bool BiTree::InsertLeft()関数がリロードされ、パラメータが入力されていない場合、現在のノードに新しい左サブノードが追加されます.
bool BiTree::InsertRight()関数がリロードされ、パラメータが入力されていない場合、現在のノードに新しい右サブノードが追加されます.
bool BiTree::DeleteLeft()現在のノードの左サブノードを削除
bool BiTree::DeleteRight()現在のノードの右サブノードを削除する
/****************************************************************
// Binary Tree Using C/C++
// File: BiTree.cpp
// Time: 2017.6.12 14:24
// Author: JayRoxis
*****************************************************************/

#ifndef __BITREE_H__
#define __BITREE_H__

#include 

// Typedef
typedef int ElemType;  //Change the definition of ElemType

// Define class Bitree
typedef class BiTree{
    private:
        BiTree* root;
        ElemType data;
        BiTree* Lptr;
        BiTree* Rptr;

    public:

        // Tree related
        bool InitTree();
        bool DestroyTree();
        bool ResetTree();
        bool ClearTree();
        bool IsEmptyTree();
        bool ShowTree();
        int GetSize();
        int GetDepth();
        bool TraverseTree(bool (*F)(), int flag);

        // Tree nodes related
        bool Grow();
        BiTree* GetRoot();
        bool IsParent();
        ElemType GetValue();
        bool visit();
        bool AssignValue(ElemType value);
        BiTree* LeftChild();
        BiTree* RightChild();
        bool InsertLeft(BiTree* l);
        bool InsertRight(BiTree* r);
        bool InsertLeft();   // OVERLOAD
        bool InsertRight();  // OVERLOAD
        bool DeleteLeft();
        bool DeleteRight();
        BiTree();

} Bitree;

#endif
/****************************************************************
// Binary Tree Using C/C++
// File: BiTree.cpp
// Time: 2017.6.12 14:23
// Author: JayRoxis
*****************************************************************/

#include <stdio.h>
#include "BiTree.h"

#ifndef __BITREE_CPP__
#define __BITREE_CPP__

#define INIT_DATA 0   // Define the initial value of a tree

#define PRE_ORDER 0   // Define the traverse symbol 
#define IN_ORDER 1
#define POST_ORDER 2
#define LEVEL_ORDER 3


// Initiating
BiTree::BiTree():root(NULL),data(INIT_DATA),Lptr(NULL),Rptr(NULL){};

/************* Tree related function definition ******************/

// Initiate a binary tree, create the root node
bool BiTree::InitTree(){
    root = (BiTree *)malloc(sizeof(BiTree));
    if (!root)
        return false;
    return true;
} 


// Destroy the binary tree
bool BiTree::DestroyTree(){
    if (root)
        if (ResetTree()){
            free(root);
            root = NULL;
            return true;
        }
    return false;
}


// Reset the binary tree
bool BiTree::ResetTree(){
    if (root){
        if (Lptr){
            Lptr->ResetTree();
            DeleteLeft();
        }
        if (Rptr){
            Rptr->ResetTree();
            DeleteRight();
        }
        return true;
    }
    root->data = 0;
    return false;
}


// Clear the binary tree
bool BiTree::ClearTree(){
    if (root)
        if (AssignValue(INIT_DATA)){
            if (Lptr)
                Lptr->AssignValue(INIT_DATA);
            if (Rptr)
                Rptr->AssignValue(INIT_DATA);
            return true;
        }
    return false;
}


// Determine if the tree is empty
bool BiTree::IsEmptyTree(){
    if (root->Lptr || root->Rptr)
        return false;
    return true;
}


// Traverse the tree
bool BiTree::TraverseTree(bool (*F)(), int flag){
    if (root)
            switch (flag){
            case PRE_ORDER:         // PreOrder
                if (!F())
                    return false;
                if (Lptr)
                    if (!TraverseTree(F, flag))
                        return false;
                if (Rptr)
                    if (!TraverseTree(F, flag))
                        return false;
                return true;
                break;
            case IN_ORDER:          // InOrder              
                if (Lptr)
                    if (!TraverseTree(F, flag))
                        return false;
                if (!F())
                    return false;
                if (Rptr)
                    if (!TraverseTree(F, flag))
                        return false;
                break;
            case POST_ORDER:        // PostOrder
                if (Lptr)
                    if (!TraverseTree(F, flag))
                        return false;
                if (Rptr)
                    if (!TraverseTree(F, flag))
                        return false;
                if (!F())
                        return false;
                return true;
                break;
            case LEVEL_ORDER:       // LevelOrder
                break;
            default:
                return false;

            }
    return false;
}


// Show all the element of the tree
bool BiTree::ShowTree(){
    if (root)
        if (AssignValue(INIT_DATA)){
            if (Lptr)
                Lptr->ShowTree();
            if (Rptr)
                Rptr->ShowTree();
            visit();
            return true;
        }
    return false;
}


// Get the size of the tree
int BiTree::GetSize(){
    if (!root)
        return 0;
    return (Lptr != NULL) * Lptr->GetSize() + (Rptr != NULL) * Rptr->GetSize() + 1;
}


// Get the depth of the tree
int BiTree::GetDepth(){
    if (!root)
        return 0;
    int l = (Lptr != NULL) * Lptr->GetDepth();
    int r = (Rptr != NULL) * Rptr->GetDepth();
    return (l>=r)*l + (r>l)*r + 1;
}


/**************** Node related function definition ******************/

// Get the root of the tree
BiTree* BiTree::GetRoot(){
    return root;
}

// Create a node to a existed tree
bool BiTree::Grow(){
    if (!root)
        return false;
    if (!InsertLeft())
        if (!InsertRight())
            return false;
    return true;
}


// Determine if the node has children
bool BiTree::IsParent(){
    if (Lptr||Rptr)
        return true;
    return false;
}


// Get the value of the node
ElemType BiTree::GetValue(){
    if (!root)
        return false;
    return data;
}


// Print the value of node
bool BiTree::visit(){
    if (!root)
        return false;
    if ((Lptr)||(Rptr))
        printf("%d(%x,%x)
",data,Lptr,Rptr);
    else
        printf("%d
",data);
    return true;
}


// Assign value to the node
bool BiTree::AssignValue(ElemType value){
    if (!root)
        return false;
    data = value;
    if (!data == value)
        return false;
    return true;
}


// Get left child of the node
BiTree* BiTree::LeftChild(){
    return Lptr; 
}


// Get right child of the node
BiTree* BiTree::RightChild(){
    return Rptr; 
}


// Insert/Append an existed node as left child 
bool BiTree::InsertLeft(BiTree* l){
    if ((!root)||(!l))
        return false;
    if (Lptr){
        l->Lptr = Lptr;
    }
    Lptr = l;
    l->root = root;
    return true;
}


// Insert/Append an existed node as right child
bool BiTree::InsertRight(BiTree* r){
    if ((!root)||(!r))
        return false;
    if (Rptr){
        r->Rptr = Rptr;
    }
    Rptr = r;
    r->root = root;
    return true;
}


// OVERLOAD: Insert/Append an new node as left child 
bool BiTree::InsertLeft(){
    if ((!root)||(Lptr))
        return false;
    Lptr = (BiTree *)malloc(sizeof(BiTree));
    return true;
}


// OVERLOAD: Insert/Append an new node as right child 
bool BiTree::InsertRight(){
    if ((!root)||(Rptr))
        return false;
    Rptr = (BiTree *)malloc(sizeof(BiTree));
    return true;
}

// Delete left child of the node
bool BiTree::DeleteLeft(){
    if ((!root)||(!Lptr))
        return false;
    free(Lptr);
    Lptr = NULL;
    return true;
}


// Delete right child of the node
bool BiTree::DeleteRight(){
    if ((!root)||(!Rptr))
        return false;
    free(Rptr);
    Rptr = NULL;
    return true;
}

#endif
C++構造と分析
c++ベースのチェーンテーブルノードの挿入と削除