binary tree data structure c
C ++のバイナリツリーに関するこの詳細なチュートリアルでは、C ++のバイナリツリーのタイプ、表現、トラバーサル、アプリケーション、および実装について説明します。
二分木は、広く使用されているツリーデータ構造です。ツリーの各ノードに最大で2つの子ノードがある場合、そのツリーはバイナリツリーと呼ばれます。
したがって、一般的な二分木には次のコンポーネントがあります。
- 左のサブツリー
- ルートノード
- 右のサブツリー
=> このシリーズのC ++チュートリアルの完全なリストに注意してください。
学習内容：
C ++の二分木
二分木の図解を以下に示します。
特定の二分木では、任意のレベルのノードの最大数は2です。l-1ここで、「l」はレベル番号です。
したがって、レベル1のルートノードの場合、ノードの最大数= 21-1= 20= 1
二分木のすべてのノードには最大2つのノードがあるため、次のレベルの最大ノードは2 * 2になります。l-1。
ネットワークエンジニアのインタビューの質問250+質問と回答の説明pdf
深さまたは高さがhの二分木が与えられた場合、高さh = 2の二分木のノードの最大数h-1。
したがって、高さ3の二分木（上に表示）では、ノードの最大数= 23-1 = 7。
次に、さまざまなタイプの二分木について説明します。
二分木の種類
以下は、最も一般的なタイプの二分木です。
＃1）完全な二分木
すべてのノードに0個または2個の子がある二分木は、完全な二分木と呼ばれます。
上に示したのは完全な二分木で、リーフノードを除くすべてのノードに2つの子があることがわかります。 Lがリーフノードの数であり、「l」が内部または非リーフノードの数である場合、完全な二分木では、L = l +1です。
＃2）完全な二分木
完全な二分木では、最後のレベルを除くすべてのレベルが満たされ、最後のレベルには左側と同じくらいすべてのノードがあります。
上に示したツリーは完全な二分木です。完全なバイナリツリーの典型的な例は、後のチュートリアルで説明するバイナリヒープです。
＃3）完璧な二分木
二分木は、そのすべての内部ノードに2つの子があり、すべてのリーフノードが同じレベルにある場合に完全と呼ばれます。
上に示した二分木の例は、各ノードに2つの子があり、すべてのリーフノードが同じレベルにあるため、完全な二分木です。
高さhの完全な二分木は2を持っていますh–1ノード数。
＃4）縮退したツリー
各内部ノードに子が1つしかない二分木は、縮退ツリーと呼ばれます。
上に示したツリーは縮退したツリーです。このツリーのパフォーマンスに関する限り、縮退ツリーはリンクリストと同じです。
＃5）平衡二分木
すべてのノードの2つのサブツリーの深さが1を超えて異ならないバイナリツリーは、平衡二分木と呼ばれます。
上記の二分木は、すべてのノードの2つのサブツリーの深さが1以下であるため、平衡二分木です。以降のチュートリアルで説明するAVL木は、一般的な平衡二分木です。
二分木表現
二分木には、2つの方法でメモリが割り当てられます。
＃1）シーケンシャル表現
これは、ツリーデータ構造を格納するための最も簡単な手法です。配列は、ツリーノードを格納するために使用されます。ツリー内のノードの数は、配列のサイズを定義します。ツリーのルートノードは、配列の最初のインデックスに格納されます。
一般に、ノードがiに格納されている場合th場所の場合、左と右の子はそれぞれ2iと2i +1の場所に保存されます。
次の二分木を考えてみましょう。
上記の二分木の順次表現は次のとおりです。
上記の表現では、各ノードの左と右の子がそれぞれ2 *（node_location）と2 *（node_location）+1の場所に格納されていることがわかります。
例えば、 配列内のノード3の位置は3です。したがって、左の子は2 * 3 = 6に配置されます。その右の子は、位置2 * 3 +1 = 7に配置されます。配列でわかるように、子6と7である3つのうちの6つは、配列の6と7の位置に配置されます。
ツリーノードを格納するために使用される配列はメモリ内で多くのスペースを占有するため、ツリーの順次表現は非効率的です。ツリーが成長するにつれて、この表現は非効率になり、管理が困難になります。
この欠点は、ツリーノードをリンクリストに格納することで克服されます。ツリーが空の場合、ルートノードを格納する最初の場所は0に設定されることに注意してください。
＃2）リンクリスト表現
このタイプの表現では、リンクリストを使用してツリーノードを格納します。複数のノードがメモリ内の連続していない場所に散在しており、ノードはツリーのように親子関係を使用して接続されています。
最高のメールプロバイダーです
次の図は、ツリーのリンクリスト表現を示しています。
上記の表現に示されているように、各リンクリストノードには次の3つのコンポーネントがあります。
- 左ポインタ
- データ部分
- 右ポインタ
左ポインタには、ノードの左子へのポインタがあります。右ポインタにはノードの右子へのポインタがありますが、データ部分にはノードの実際のデータが含まれています。特定のノード（リーフノード）の子がない場合、上の図に示すように、そのノードの左右のポインターはnullに設定されます。
C ++でのバイナリツリーの実装
次に、C ++のリンクリスト表現を使用してバイナリツリープログラムを開発します。構造を使用して単一のノードを宣言し、次にクラスを使用して、ノードのリンクリストを作成します。
#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
二分木探索
木に関する基本的なチュートリアルでは、トラバーサルについてすでに説明しました。このセクションでは、バイナリツリーにノードを挿入し、バイナリツリーの3つのトラバーサル（順序、前順序、後順序）すべてを示すプログラムを実装しましょう。
#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(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 bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'< 出力：
インオーダートラバーサル：
A B C D E F G
通信販売のトラバーサル：
G F E D C B A
プレオーダートラバーサル：
A B C D E F G
二分木の応用
二分木は、データを格納するために多くのアプリケーションで使用されます。
二分木の重要なアプリケーションのいくつかを以下に示します。
- 二分探索木： バイナリツリーは、多くの言語ライブラリのセットやマップなど、多くの検索アプリケーションで使用されるバイナリ検索ツリーを構築するために使用されます。
- ハッシュツリー： 主に特殊な画像署名アプリケーションでハッシュを検証するために使用されます。
- ヒープ： ヒープは、ルーター、オペレーティングシステムのプロセッサのスケジューリングなどに使用される優先キューを実装するために使用されます。
- ハフマン符号化： ハフマンコーディングツリーは、圧縮アルゴリズム（画像圧縮など）や暗号化アプリケーションで使用されます。
- 構文木： コンパイラは、プログラムで使用される式を解析するためのバイナリツリーにすぎない構文ツリーを構築することがよくあります。
結論
二分木は、ソフトウェア業界全体で広く使用されているデータ構造です。二分木は、ノードに最大2つの子ノードがあるツリーです。完全な二分木、完全な二分木、完全な二分木、縮退した二分木、バランスの取れた二分木など、さまざまな種類の二分木を見てきました。
バイナリツリーデータは、前のチュートリアルで見たインオーダー、プレオーダー、ポストオーダーのトラバーサル手法を使用してトラバースすることもできます。メモリでは、バイナリツリーはリンクリスト（非連続メモリ）または配列（順次表現）を使用して表すことができます。
配列は多くのスペースを占めるため、リンクリスト表現は配列と比較してより効率的です。
=> ここで最高のC ++トレーニングチュートリアルをチェックしてください。
推奨読書