trees c basic terminology
C ++ツリーに関するこの詳細なチュートリアルでは、ツリータイプ、ツリートラバーサル手法、および基本的な用語について、写真とサンプルプログラムを使用して説明します。
このC ++シリーズでは、これまで静的および動的の両方の性質の線形データ構造を見てきました。次に、非線形データ構造に進みます。このカテゴリの最初のデータ構造は「ツリー」です。
ツリーは非線形の階層データ構造です。ツリーは、有向または無向の「エッジ」によって相互に接続されたノードのコレクションです。ノードの1つは「ルートノード」として指定され、残りのノードは子ノードまたはルートノードのリーフノードと呼ばれます。
一般に、各ノードは同じ数の子を持つことができますが、親ノードは1つだけです。
=> C ++トレーニングシリーズ全体をチェックしてください
ツリーのノードは、姉妹ノードと呼ばれる同じレベルにあるか、親子関係を持つことができます。同じ親を持つノードは兄弟ノードです。
学習内容:
配列javaのコピーを作成する方法
C ++のツリー
以下に、さまざまな部分を含むツリーの例を示します。
木に使用するいくつかの基本的な用語の定義を見てみましょう。
- ルートノード: これは、ツリー階層の最上位ノードです。上の図では、ノードAがルートノードです。ルートノードには親がないことに注意してください。
- リーフノード: これは、ツリー階層の最下位ノードです。リーフノードは、子ノードを持たないノードです。これらは外部ノードとも呼ばれます。上記のツリーのノードE、F、G、H、およびCはすべてリーフノードです。
- サブツリー: サブツリーは、ルートがnullでない場合のノードのさまざまな子孫を表します。ツリーは通常、ルートノードと1つ以上のサブツリーで構成されます。上の図では、(B-E、B-F)と(D-G、D-H)はサブツリーです。
- 親ノード: 子ノードと親に向かって上向きのエッジを持つルートノードを除くすべてのノード。
- Ancestor Node: これは、ルートからそのノードへのパス上の先行ノードです。ルートには祖先がないことに注意してください。上の図では、AとBはEの祖先です。
- キー: ノードの値を表します。
- レベル: ノードの生成を表します。ルートノードは常にレベル1にあります。ルートの子ノードはレベル2にあり、ルートの孫はレベル3にあります。一般に、各ノードはその親よりも高いレベルにあります。
- 道: パスは、連続するエッジのシーケンスです。上の図では、EへのパスはA => B-> Eです。
- 程度: ノードの次数は、ノードが持つ子の数を示します。上の図では、BとDの次数はそれぞれ2ですが、Cの次数は0です。
C ++ツリーの種類
ツリーのデータ構造は、下の図に示すように、次のサブタイプに分類できます。
#1)一般的なツリー
一般的なツリーは、ツリーの基本的な表現です。 1つのノードと1つ以上の子ノードがあります。トップレベルノード、つまりルートノードはレベル1に存在し、他のすべてのノードはさまざまなレベルに存在する可能性があります。
一般的なツリーを次の図に示します。
上の図に示すように、一般的なツリーには任意の数のサブツリーを含めることができます。ノードB、C、およびDはレベル2に存在し、兄弟ノードです。同様に、ノードE、F、G、およびHも兄弟ノードです。
異なるレベルに存在するノードは、親子関係を示す場合があります。上の図では、ノードB、C、およびDはAの子です。ノードEおよびFはBの子ですが、ノードGおよびHはDの子です。
一般的なツリーは、C ++実装を使用して以下に示されています。
#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }
出力:
作成される一般的なツリーは次のとおりです。
10
/
20 30
/
40
#2)森
ツリーからルートノードを削除し、次のレベルの要素とルートを結合するエッジを削除すると、次に示すように、互いに素なツリーのセットが取得されます。
上の図では、ルートノードAと、ルートノードをノードB、C、およびDに接続していた3つのエッジを削除することにより、2つのフォレストを取得しました。
#3)二分木
各ノードが最大2つの子ノードを持つツリーデータ構造は、バイナリツリーと呼ばれます。二分木は最も人気のあるツリーデータ構造であり、式の評価、データベースなどのさまざまなアプリケーションで使用されます。
次の図は、二分木を示しています。
上の図では、ノードA、B、およびDにそれぞれ2つの子があることがわかります。各ノードに正確にゼロまたは2つの子があるバイナリツリーは、完全なバイナリツリーと呼ばれます。このツリーには、子が1つあるノードはありません。
完全な二分木には、左から右に塗りつぶされる最低レベルを除いて、完全に塗りつぶされる二分木があります。上に示した二分木は完全な二分木です。
以下は、二分木を示す簡単なプログラムです。ツリーの出力は、入力ツリーの順序どおりの走査シーケンスであることに注意してください。
#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '< 出力:
作成された二分木:
5 10 15 20 30 40 45
#4)二分探索木
順序付けられた二分木は、二分探索木と呼ばれます。二分探索木では、左側のノードはルートノードよりも小さく、右側のノードはルートノード以上です。
ポートトリガーとポートフォワーディングとは
二分探索木の例を以下に示します。
上の図では、左側のノードがすべてルート要素である20未満であることがわかります。一方、右側のノードはルートノードよりも大きくなります。二分探索木は、検索と並べ替えの手法で使用されます。
#5)式ツリー
単純な算術式を評価するために使用される二分木は、式ツリーと呼ばれます。
簡単な式ツリーを以下に示します。
上記のサンプル式ツリーでは、式(a + b)/(a-b)を表します。上図に示すように、ツリーの非リーフノードは式の演算子を表し、リーフノードはオペランドを表します。
式ツリーは、主に代数式を解くために使用されます。
ツリートラバーサルテクニック
配列、リンクリスト、スタック、キューなどの線形データ構造を見てきました。これらすべてのデータ構造には、構造を1つの方法でのみ、つまり線形にトラバースする共通のトラバース手法があります。
ただし、ツリーの場合、以下に示すように、さまざまなトラバーサル手法があります。
#1)順番に: このトラバーサル手法では、左側のサブツリーにノードがなくなるまで、最初に左側のサブツリーをトラバースします。この後、ルートノードにアクセスし、右側のサブツリーでトラバースするノードがなくなるまで、右側のサブツリーをトラバースします。したがって、inOrderトラバーサルの順序は左->ルート->右です。
#2)予約注文: プレオーダートラバーサル手法では、最初にルートノードを処理し、次に左側のサブツリー全体をトラバースし、最後に右側のサブツリーをトラバースします。したがって、プレオーダートラバーサルの順序はroot-> left-> rightです。
#3)ポストオーダー: ポストオーダートラバーサル手法では、左側のサブツリー、右側のサブツリー、最後にルートノードをトラバースします。ポストオーダー手法のトラバーサルの順序は、左->右->ルートです。
nがルートノードであり、「l」と「r」がそれぞれツリーの左ノードと右ノードである場合、ツリー走査アルゴリズムは次のようになります。
順序(lnr)アルゴリズム:
- inOrder(left- Subtree)を使用して左サブツリーをトラバースします。
- ルートノード(n)にアクセスします。
- inOrder(right- subtree)を使用して右サブツリーをトラバースします。
プレオーダー(nlr)アルゴリズム:
- ルートノード(n)にアクセスします。
- preorder(left-subtree)を使用して左サブツリーをトラバースします。
- preorder(right-subtree)を使用して、右のサブツリーをトラバースします。
ポストオーダー(lrn)アルゴリズム:
- postOrder(left-subtree)を使用して左サブツリーをトラバースします。
- postOrder(right-subtree)を使用して右のサブツリーをトラバースします。
- ルートノード(n)にアクセスします。
上記のトラバーサル手法のアルゴリズムから、この手法を特定のツリーに再帰的に適用して、目的の結果を得ることができることがわかります。
次のツリーについて考えてみます。
上記のトラバーサル手法を使用して、上記のツリーのトラバーサルシーケンスを以下に示します。
- インオーダートラバーサル:2 3 5 6 10
- 事前注文トラバーサル:6 3 2 5 10
- PostOrderトラバーサル:2 5 3 10 6
結論
ツリーは、ソフトウェア分野の多くのアプリケーションで使用される非線形の階層データ構造です。
リストをトラバースする方法が1つしかない線形データ構造とは異なり、さまざまな方法でツリーをトラバースできます。このチュートリアルでは、トラバーサル手法とさまざまな種類の木について詳細に調査しました。
推奨読書