バイナリツリーの概念
バイナリツリーは、n（n> = 0）ノードの有限セットです。このセットは、空のセット（空のバイナリツリー）であるか、ルートノードと右のサブツリーと呼ばれるルートノードとそれぞれ交差しない2つのバイナリツリーで構成されています。
バイナリツリーの特性
各ノードには最大2つのサブツリーがあるため、バイナリツリーに2度以上のノードはありません。バイナリツリー内の各ノードはオブジェクトであり、各データノードには3つのポインターがあります。つまり、親、左子、右の子供へのポインターです。各ノードは、ポインターを介して互いに接続されています。接続されたポインター間の関係は、すべて父と息子の関係です。
バイナリツリーノードの定義
バイナリツリーノードは次のように定義されています。
コードコピーは次のとおりです。
struct binarytreenode
{
int m_nvalue;
binarytreenode* m_pleft;
binarytreenode* m_pright;
};
バイナリツリーの5つの基本的な形式
空のバイナリツリー
ルートノードは1つだけです
ルートノードには左サブツリーのみがあります
ルートノードには右のサブツリーのみがあります
ルートノードには左と右のサブツリーの両方があります
3つのノードを持つ通常のツリーには2つのケースしかありません：2つまたは3つ。ただし、バイナリツリーは左右を区別する必要があるため、次の5つの形式に進化します。
特別なバイナリツリー
傾斜した木
上記の最後から2番目の小さな写真に示されているように。
完全なバイナリツリー
バイナリツリーでは、すべての分岐ノードが左および右サブツリーを持っていて、すべての葉が同じレイヤーにある場合、そのようなバイナリツリーは完全なバイナリツリーと呼ばれます。下の図に示すように：
完全なバイナリツリー
完全にバイナリツリーは、最後のレイヤーが左側にいっぱいであり、右側がいっぱいであるかどうか、およびレイヤーの残りの部分がいっぱいであることを意味します。 kの深さと2^k -1の複数のノードを持つバイナリツリーは、完全なバイナリツリー（完全なバイナリツリー）です。 Kの深さとスペースがない木です。
完全にバイナリツリーの特性は次のとおりです。
葉のノードは、最低2層でのみ表示できます。
最低の葉は、左側の連続位置に集中する必要があります。
最後から2番目の層では、葉のノードがある場合、右側の連続位置にある必要があります。
ノードの程度が1の場合、ノードには左子のみがあります。
同じノードツリーを持つバイナリツリーの場合、完全なバイナリツリーの深さは最小です。
注：完全なバイナリツリーは完全にバイナリツリーでなければなりませんが、完全にバイナリツリーは完全なバイナリツリーではない場合があります。
アルゴリズムは次のとおりです。
コードコピーは次のとおりです。
bool is_complete（tree *root）
{
キューQ;
ツリー *ptr;
//幅の優先順位トラバーサル（階層トラバーサル）を実行し、nullノードもキューに入れます
Q.Push（root）;
while（（ptr = q.pop（））！= null）
{
Q.push（ptr->左）;
Q.push（ptr-> right）;
}
//アクセスされていないノードがまだあるかどうかを判断します
while（！q.is_empty（））
{
ptr = q.pop（）;
//アクセスされていない非ヌルノードがある場合、ツリーにはボイドがあり、非完全なバイナリツリーです。
if（null！= ptr）
{
falseを返します。
}
}
trueを返します。
}
バイナリツリーの特性
バイナリツリーのプロパティ1：バイナリツリーのi番目の層に最大2^（i-1）ノードがあります（i> = 1）
バイナリツリーのプロパティ2：深さkを持つバイナリツリーは最大2^k-1ノード（k> = 1）を持っています
バイナリツリーのシーケンシャルストレージ構造
バイナリツリーのシーケンシャルストレージ構造は、1次元配列を使用して各ノードをバイナリツリーに保存することであり、ノードのストレージ位置はノード間の論理的な関係を反映できます。
バイナリリンクリスト
シーケンシャルストレージ方法はあまり適用できないため、チェーンストレージ構造を考慮する必要があります。国際的な慣行によると、バイナリツリーストレージは一般にチェーンストレージ構造を採用しています。
バイナリツリーの各ノードには最大2人の子供がいるため、データフィールドと2つのポインターフィールドを設計することは自然な考えです。このようなリンクリストをバイナリリンクリストと呼びます。
バイナリツリーのトラバーサル
バイナリツリーのトラバースとは、ルートノードから特定の順序でバイナリツリー内のすべてのノードにアクセスすることを指し、各ノードに1回しかアクセスされません。
次のように、バイナリツリーを通過するには3つの方法があります。
（1）先行トラバーサル（DLR）、最初にルートノードにアクセスし、次に左サブツリーを通過し、最後に右サブツリーを通過します。省略されたルート - 左 - 右。
（2）順序トラバーサル（LDR）、最初に左サブツリーを通過し、次にルートノードにアクセスし、最後に右サブツリーを通過します。略語メモ：左根右。
（3）ポストオーバートラバーサル（LRD）、最初に左サブツリーを横断し、次に右サブツリーを通過し、最後にルートノードにアクセスします。左右に略された。
プリアンブルトラバーサル：
バイナリツリーが空の場合、空の操作が戻ります。それ以外の場合は、最初にルートノードにアクセスし、以前の順序で左サブツリーを横断し、以前の順序で右サブツリーを横断します。
トラバーサルの順序は次のとおりです。Abdhiejcfkg
コードコピーは次のとおりです。
//正確なトラバーサル
function preorder（node）{
if（！node == null）{
putstr（node.show（）+ ""）;
予約（node.left）;
予約（node.right）;
}
}
注文トラバーサル：
ツリーが空の場合、空の操作が戻り、それ以外の場合はルートノードから始まります（ルートノードが最初にアクセスされないことに注意してください）、ルートノードの左サブツリーは中期に通過し、ルートノードにアクセスし、最後に右サブツリーが中央で移動されます。
トラバーサルの順序は次のとおりです。Hdibejafkcg
コードコピーは次のとおりです。
//再帰的な方法を使用して、ミドルオーバートラバーサルを実装します
function inorder（node）{
if（！（node == null））{
inorder（node.left）; //最初に左サブツリーに追加します
putstr（node.show（）+ ""）; //ルートノードにもう一度追加します
inorder（node.right）; //右サブツリーへの最後のアクセス
}
}
郵便局所走査：
ツリーが空の場合、空の操作が戻ります。それ以外の場合、左右のサブツリーは左から右に通過して、左と右のサブツリーにアクセスし、最後にルートノードにアクセスします。
トラバーサルの順序は：hidjebkfgcaです
コードコピーは次のとおりです。
//ポストオーバートラバーサル
function postorder（node）{
if（！node == null）{
Postorder（node.left）;
Postorder（node.right）;
putstr（node.show（）+ ""）;
}
}
バイナリ検索ツリーを実装します
バイナリルックアップツリー（BST）はノードで構成されているため、次のようにノードノードオブジェクトを定義します。
コードコピーは次のとおりです。
関数ノード（データ、左、右）{
this.data = data;
this.left = left; //左ノードリンクを保存します
this.right = right;
this.show = show;
}
関数show（）{
this.data; //ノードに保存されたデータを表示します
}
最大値と最小値を見つけます
BSTの最小値と最大値を見つけることは非常に単純です。なぜなら、より小さな値は常に左の子供ノードにあり、BSTの最小値を探しているため、最後のノードが見つかるまで左の子供の木を通過するだけです
最小値を見つけます
コードコピーは次のとおりです。
function getmin（）{
var current = this.root;
while（！（current.left == null））{
current = current.left;
}
current.dataを返します。
}
この方法は、BSTの左のサブツリーに沿って1つずつ横断します。BSTの左端ノードに移動します。
コードコピーは次のとおりです。
current.left = null;
この時点で、現在のノードに保存された値は最小値です
最大値を見つけます
BSTで最大値を見つけるには、最後のノードが見つかるまで右サブツリーを通過する必要があり、そのノードに保存された値は最大値です。
コードコピーは次のとおりです。
function getMax（）{
var current = this.root;
while（！（current.right == null））{
current = current.right;
}
current.dataを返します。
}