プログラミングベース-スレッドツリー(Threaded Binary Tree)

40279 ワード

プログラミングベース-スレッドツリー(Threaded Binary Tree)
分類に戻る:すべての記事>>基礎知識
戻る上司:プログラミングベース-ツリー(Binary Tree)
本稿では,手がかりツリーの基礎知識を紹介し,C++で実現する.
この文書を表示する前に、ツリーとツリーの概念を理解するために、データ構造とプログラム言語の基礎が必要です.
この方法では、スタック、キュー、再帰も熟知する必要があります.
文書ディレクトリ

手がかり二叉木概要(Introduction)

2手がかり二叉木の構造(Structure)

3はノードに手がかり(Add Thread)

を加える.

4手がかり二叉木の遍歴(Traversal)

4.1先頭ノード

を取得

4.2後継前駆ノード

を取得する.

4.3中序遍歴(Inorder Traversal)

5主関数とテスト(Main Method and Testing)

5.1主関数(Main Method)

5.2印刷結果(Print Output)

1スレッドツリーの概要(Introduction)
手がかり二叉木:n個の接点を持つ二叉木を仮定し、その中にn+1個の空のポインタが存在し、これらのポインタを利用して何らかの遍歴下の前駆と後継を格納する.このようなポインタを手がかりと呼び、このように形成された二叉木を手がかり二叉木と呼ぶ.
手がかりツリーは3種類に分けられます.

中序手がかり二叉木

前序手がかり二叉木

後続手がかり二叉木

その後のコードは,中序手がかり二叉木を用いて例を挙げ,他の2つの原理は同じであり,これ以上述べない.
2スレッドツリーの構造(Structure)
構造では、左サブツリーと右サブツリーには、左右の子供が後継者であるか、前駆者であるかを示すラベルが必要です.
各ノードの空のピン領域:

左サブツリーポインタ空:前駆ポインタ

を格納

右サブツリーポインタ空:後続ポインタ

を格納

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree

//     ，                  
enum ThreadTag
{
    LeftOrRightChild = 0, //        
    PredecessorOrSuccessor = 1 //      
};

//        
template<typename T>
class ThreadNode
{
    public:
    T element; //   
    ThreadTag leftTag; //    
    ThreadTag rightTag; //    
    ThreadNode<T>* leftChild; //    
    ThreadNode<T>* rightChild; //    

    ThreadNode(const T& e)
    {
        element = e;
        leftTag = ThreadTag::LeftOrRightChild;
        rightTag = ThreadTag::LeftOrRightChild;
        leftChild = 0;
        rightChild = 0;
    }
    ~ThreadNode()
    {
        leftChild = 0;
        rightChild = 0;
    }
};

3ノードに手がかりを加える(Add Thread)
初期化ツリーは説明されません.ここでは、各ノードに手がかりを追加します.
前駆体と後続を保存する必要があるため、前のノードを格納するために変数predNodeが必要です.
手がかりを加えるには、すべてのノードを巡回する必要があります.すなわち,アクセスノード(Visit)を二叉木の中順遍歴で手がかりに入れただけである.
各ノードの空のピンフィールド:

左サブツリーポインタ空:前駆ポインタ

を格納

右サブツリーポインタ空:後続ポインタ

を格納
C++コード:

再帰方式:

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree
//            
template<typename T>
void InitializeInorderThread(ThreadNode<T>* node, ThreadNode<T>*& predNode)
{
    if (node != 0)
    {
        //    
        if (node->leftChild == 0)
        {
            node->leftTag = ThreadTag::PredecessorOrSuccessor;
        }
        else
        {
            node->leftTag = ThreadTag::LeftOrRightChild;
        }

        //    
        if (node->rightChild == 0)
        {
            node->rightTag = ThreadTag::PredecessorOrSuccessor;
        }
        else
        {
            node->rightTag = ThreadTag::LeftOrRightChild;
        }

        InitializeInorderThread(node->leftChild, predNode); //    （L）
        
        //      ， NULL   
        if (node->leftTag == ThreadTag::PredecessorOrSuccessor)
        {
            node->leftChild = predNode;
        }

        //       ，      ， NULL   
        if (predNode != 0 && predNode->rightTag == ThreadTag::PredecessorOrSuccessor)
        {
            predNode->rightChild = node;
        }

        predNode = node;
        InitializeInorderThread(node->rightChild, predNode); //    （R）
    }
}

非再帰方式:

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree
//          
template<typename T>
void InitializeInorderThread(ThreadNode<T>* root)
{
    if (root == 0)
    {
        return;
    }

    std::stack<ThreadNode<T>*> nodeStack;
    ThreadNode<T>* predNode = 0;
    ThreadNode<T>* loopNode = root;

    do
    {
        while (loopNode != 0) //    （L）
        {
            if (loopNode->leftChild == 0)
            {
                loopNode->leftTag = ThreadTag::PredecessorOrSuccessor;
            }
            else
            {
                loopNode->leftTag = ThreadTag::LeftOrRightChild;
            }

            if (loopNode->rightChild == 0)
            {
                loopNode->rightTag = ThreadTag::PredecessorOrSuccessor;
            }
            else
            {
                loopNode->rightTag = ThreadTag::LeftOrRightChild;
            }

            nodeStack.push(loopNode);
            loopNode = loopNode->leftChild;
        }

        if (!nodeStack.empty())
        {
            loopNode = nodeStack.top();
            nodeStack.pop();

            //      ， NULL   
            if (loopNode->leftTag == ThreadTag::PredecessorOrSuccessor)
            {
                loopNode->leftChild = predNode;
            }

            //       ，      ， NULL   
            if (predNode != 0 && predNode->rightTag == ThreadTag::PredecessorOrSuccessor)
            {
                predNode->rightChild = loopNode;
            }

            predNode = loopNode;
            loopNode = loopNode->rightChild; //    （R）
        }
    } while (loopNode != 0 || !nodeStack.empty());
}

4手がかり二叉木の遍歴(Traversal)
私たちは手がかりが多くなったので、遍歴はもっと楽になり、手がかりに基づいて一つ一つ行うだけでいいです.
以下では、中順遍歴を例に挙げます.
4.1先頭ノードの取得(First and Last Node)

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree
//          
template<typename T>
ThreadNode<T>* ThreadTreeInorderFirstNode(ThreadNode<T>* root)
{
    if (root == 0)
    {
        return 0;
    }

    ThreadNode<T>* first = root;
    while (first->leftTag == ThreadTag::LeftOrRightChild)
    {
        first = first->leftChild;
    }
    return first;
}

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree
//           
template<typename T>
ThreadNode<T>* ThreadTreeInorderLastNode(ThreadNode<T>* root)
{
    if (root == 0)
    {
        return 0;
    }

    ThreadNode<T>* last = root;
    while (last->rightTag == ThreadTag::LeftOrRightChild)
    {
        last = last->rightChild;
    }
    return last;
}

4.2後継前駆ノードの取得(Successor and Predecessor Node)

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree
//         
template<typename T>
ThreadNode<T>* ThreadTreeInorderSuccessor(ThreadNode<T>* node)
{
    if (node == 0)
    {
        return 0;
    }

    if (node->rightTag == ThreadTag::LeftOrRightChild) //       
    {
        return ThreadTreeInorderFirstNode(node->rightChild); //             
    }
    else //        ，   
    {
        return node->rightChild; //   
    }
}

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree
//         
template<typename T>
ThreadNode<T>* ThreadTreeInorderPredecessor(ThreadNode<T>* node)
{
    if (node == 0)
    {
        return 0;
    }

    if (node->leftTag == ThreadTag::LeftOrRightChild) //       
    {
        //              （            ）
        return ThreadTreeInorderLastNode(node->leftChild);
    }
    else //        ，   
    {
        return node->leftChild; //   
    }
}

4.3中序遍歴(Inorder Traversal)

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree

//     
template<typename T>
void ThreadTreeInorderTraversal(ThreadNode<T>* root, void(*pVisit)(ThreadNode<T>&))
{
    for (ThreadNode<T>* node = ThreadTreeInorderFirstNode(root);
         node != 0; 
         node = ThreadTreeInorderSuccessor(node))
    {
        (*pVisit)(*node);
    }
}

//       
template<typename T>
void ThreadTreeInorderTraversalReverse(ThreadNode<T>* root, void(*pVisit)(ThreadNode<T>&))
{
    for (ThreadNode<T>* node = ThreadTreeInorderLastNode(root);
         node != 0;
         node = ThreadTreeInorderPredecessor(node))
    {
        (*pVisit)(*node);
    }
}

5主関数とテスト(Main Method and Testing)
テストのスレッドツリーは次のとおりです.
A
B
C
NULL
D
E
NULL
5.1主関数(Main Method)

// Author: https://blog.csdn.net/DarkRabbit
// Threaded Binary Tree

#include "threaded_binary_tree.h"
#include 
using namespace std;
using namespace BinaryTrees;

typedef ThreadNode<int>* ThreadedBinaryTree;

//       
void PrintVisitedElement(ThreadNode<int>& node)
{
    cout << (char)(node.element);
}

int main()
{
    ThreadedBinaryTree tree = new ThreadNode<int>('A');
    tree->leftChild = new ThreadNode<int>('B');
    tree->rightChild = new ThreadNode<int>('C');
    tree->leftChild->rightChild = new ThreadNode<int>('D');
    tree->rightChild->leftChild = new ThreadNode<int>('E');

    InitializeInorderThread(tree); //    

    //ThreadNode* pred = 0;
    //InitializeInorderThread(tree, pred); //   

    ThreadTreeInorderTraversal(tree, PrintVisitedElement);
    cout << endl;
    ThreadTreeInorderTraversalReverse(tree, PrintVisitedElement);
    cout << endl;

    delete tree->rightChild->leftChild;
    delete tree->leftChild->rightChild;
    delete tree->rightChild;
    delete tree->leftChild;
    delete tree;

    //system("pause"); VC++
    return 0;
}

5.2印刷結果(Print Output)

BDAEC
CEADB

       . . .

WPFでチャートを描くならScottPlotがおすすめ！

Prism(WPF)でNLogでもMicrosoft.Extensions.Logging.ILoggerにしたい