08-1. ツリーの概要

ひせんけいデータこうぞう

ツリーアクセス

ツリーは階層関係を表す資料構造です

木が表現できる

枝を引く


[決定ツリー]

ツリー用語の概要

ノード:node
ツリー内のコンポーネントのA、B、C、D、Eなどの要素

幹線:edge
ノードとノードを接続するベースライン

ルートノード:ルートノード
ツリー上部のAと同じノード

ターミナルノード:terminal node
ノード

内部ノード:内部ノード
A、B等のノード(端末ノードを除く)

終端ノードはブレードノードとも呼ばれる.
内部ノードは端末ノードではなく、非端末ノードとも呼ばれる

ノードAは、ノードB,C,Dの親である

ノードB,C,DはノードAのサブノード(サブノード)

ノードB,C,Dは同一の親ノードであり、互いに兄弟ノード

親ノード
特定のノードの上にあるすべてのノード

子孫ノード(Dependent node)
特定のノードの下にあるすべてのノード

バイナリツリーとサブツリー

サブツリー
大木に属する大木

バイナリツリー

-ルートノードを中心に2つのサブツリーに分割
-分割された2つのサブツリーもバイナリツリー

Ex)

空セットノードはバイナリツリーの判定でノードとして認定される

完全バイナリツリーと完全バイナリツリー

レベル:階層番号

高さ:ツリーの最上位レベル

飽和バイナリツリー:すべてのレベルが満たされており、より多くのノードを追加するには、レベル

を上げる必要があります.

完全バイナリツリー:すべてのレベルが飽和バイナリツリーのように満たされているわけではありませんが、ノードはシームレスに埋め込まれたバイナリツリーです.
上から下、左から右の順に塗りつぶします.

一般バイナリツリー

08-2. バイナリツリーの実装

バイナリツリーの実装方法:配列または接続リスト

ツリーを表現するには、接続リストが柔軟になります.

ただし,ツリーが完了した後に非常に頻繁にナビゲーションを行うツリーであれば,配列を用いて実現する.探索は簡単で速いので

タイトルファイルで定義されている構造体について

 #ifndef __BINARY_TREE_H__
 #define __BINARY_TREE_H__
 
 typedef int BData;
 
 typedef struct _bTreeNode
 {
     BTdata data;
     struct _bTreeNode * left;
     struct _bTreeNode * right;
 } BTreeNode;
 
 BTreeNode * MakeBTreeNode(void);
 BTData GetData(BTreeNode *bt);
 void SetData(BTreeNode *bt, BTData data);
 
 BTreeNode * GetLeftSubTree(BTreeNode * bt);
 BTreeNode * GetRightSubTree(BTreeNode * bt);
 
 void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
 void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);
 
 #endif

ヘッダファイルで宣言された関数の機能

BTreeNode * MakeBTreeNode(void);:ノードの作成

BTData GetData(BTreeNode * bt);:ノードに格納されているデータを返す

void SetData(BTreeNode * bt, BTData data);:ノード

にデータを保存

BTreeNode * GetLeftSubTree(BTreeNode * bt);:左サブツリーアドレス値

を返します.

BTreeNode * GetRightSubTree(BTreeNode * bt);:右側サブツリーアドレス値

を返します.
バイナリツリー構造のADT

BTreeNode * MakeBTreeNode(void);

バイナリツリーノードを生成し、そのアドレス値

を返す

BTData GetData(BTreeNode * bt);

ノードに格納されたデータを返す

void SetData(BTreeNode * bt, BTData data);

ノードにデータを格納します.格納データ転送の値

BTreeNode * GetLeftSubTree(BTreeNode * bt);

左サブツリーのアドレス値を返す

BTreeNode * GetRightSubTree(BTreeNode * bt);

は、右側のサブツリーのアドレス値

を返します.

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);

左側サブツリーに接続

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

接続右側サブツリー

バイナリツリーの実装

#include <stdio.h>
#include <stdlib.h>
#include "BinaryTree.h"

BTreeNode * MakeBTreeNode(void)
{
    BTreeNode *nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

BTData GetData(BTreeNode * bt)
{
    return bt->data;
}

void SetData(BTreeNode * bt, BTData data)
{
    bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);
        
    main->left = sub;
}

void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->right != NULL)
        free(main->right);
    
    main->right = sub;
}

08-3. バイナリツリーを巡回

巡回の3つの方法

Preorder Traversal:ルートノードを最初に選択

Inorder Traversal:ルートノード間

Postorder Transversal:ルートノードを最後に

巡回の再帰表現

1手順:左側のサブツリーを巡回

2フェーズ:ルートノードへのアクセス

3ステップ:右側のサブツリーを巡る

void InorderTraverse(BTreeNode * bt) // 이진 트리 전체를 중위 순회하는 함수
{
    InorderTraverse(bt->left); // 1단계 왼쪽 서브 트리의 순회
    printf(“%d \n”, bt->data); // 2단계 루트 노드의 방문
    InorderTraverse(bt->right); // 3단계 오른쪽 서브 트리의 순회
}

家に帰る条件は定義されていません
ノードへのアクセスはデータの出力のみです
家に帰る条件

1手順:左側のサブツリーを巡回(ノードN)

2フェーズ:ルートノードへのアクセス(ノードL)

3ステップ:右側のサブツリーを巡回(サブセットノード)

void InorderTraverse(BTreeNode * bt) // 이진 트리 전체를 중위 순회하는 함수
{
    if(bt == NULL) // bt가 NULL이면 재귀 탈출!
        return;

    InorderTraverse(bt->left); // 1단계 왼쪽 서브 트리의 순회
    printf(“%d \n”, bt->data); // 2단계 루트 노드의 방문
    InorderTraverse(bt->right); // 3단계 오른쪽 서브 트리의 순회
}

フォワードツアー

void PreorderTraverse(BTreeNode * bt)
{
    if(bt == NULL)
        return;
    
    printf(“%d \n”, bt->data); // 전위 순회이므로 루트 노드 먼저 방문
    PreorderTraverse(bt->left);
    PreorderTraverse(bt->right);
}

後巡

void PostorderTraverse(BTreeNode * bt) 
{
    if(bt == NULL)
        return;
   
    PostorderTraverse(bt->left);
    PostorderTraverse(bt->right);
    printf(“%d \n”, bt->data); // 후위 순회이므로 루트 노드 나중에 방문!
}

08-4. 「式ツリー」(Expression Tree)の実装

ルートノードに格納された演算子を演算し、2つのサブノードに格納された2つの被演算子を演算する

中位マークの修飾->後位マークの修飾->修飾ツリー

式ツリーの実装に必要なツールとヘッダファイルの定義

#ifndef __EXPRESSION_TREE_H__
#define __EXPRESSION_TREE_H__

#include "BinaryTree2.h"

BTreeNode * MakeExpTree(char exp[]);    // 수식 트리 구성
int EvaluateExpTree(BTreeNode * bt);    // 수식 트리 계산

void ShowPrefixTypeExp(BTreeNode * bt); //전위 표기법 기반 출력
void ShowInfixTypeExp(BTreeNode * bt);  // 중위 표기법 기반 출력
void ShowPostfixTypeExp(BTreeNode * bt);    //후위 표기법 기반 출력

#endif

接尾辞

演算子を左から右にリスト

2つの被演算子列は、演算子の前に

式ツリーの構成方法

被演算子に遭遇したときにスタック

に無条件に移行

演算子に遭遇した場合、スタックから2つの被演算子を取り出し、サブノード

に接続します.

サブノードを接続して作成されたツリーはスタック

に戻ります.

BTreeNode * MakeExpTree(char exp[])
{
    Stack stack;
    BTreeNode * pnode;
    
    int expLen = strlen(exp);
    int i;
    StackInit(&stack);
    
    for(i = 0; i < expLen; i++)
    {
        pnode = MakeBTreeNode();
        
        if(isdigit(exp[i])) // 피연산자라면 ...
        {
            SetData(pnode, exp[i]-'0'); //문자를 정수로 바꿔서 저장
        }
        else    // 연산자라면...
        {
            MakeRightSubTree(pnode, SPop(&stack));
            MakeLeftSubTree(pnode, SPop(&stack));
            SetData(pnode, exp[i]);
        }
        
        SPush(&stack, pnode);
    }
    
    return SPop(&stack);
}

式ツリーを巡回

電位走査出力データ:電位マークの修飾

中位数サイクル出力データ:中位数の式

後列データ出力結果:後列シンボルの修飾

void ShowPrefixTypeExp(BTreeNode * bt) // 전위 표기법의 수식으로
{
    PreorderTraverse(bt, ShowNodeData);
}

void ShowInfixTypeExp(BTreeNode * bt) // 중위 표기법의 수식으로
{
    InorderTraverse(bt, ShowNodeData);
}

void ShowPostfixTypeExp(BTreeNode * bt) // 후위 표기법의 수식으로
{
    PostorderTraverse(bt, ShowNodeData);
}

数式ツリーの計算

int EvaluateExpTree(BTreeNode * bt)
{
    int op1, op2;

    if(GetLeftSubTree(bt) == NULL && GetRightSubTree(bt) == NULL) // 단말 노드라면
        return GetData(bt);

    op1 = GetData(GetLeftSubTree(bt)); // 첫 번째 피연산자
    op2 = GetData(GetRightSubTree(bt)); // 두 번째 피연산자

    switch(GetData(bt)) // 연산자를 확인하여 연산을 진행
    {
        case ‘+’ :
            return op1+op2;
        case ‘-‘ :
            return op1-op2;
        case ‘*’ :
            return op1*op2;
        case ‘/‘ :
            return op1/op2;
    }
    
    return 0;
}