[ツリー] 二分探索木上のいくつかの操作

2月 22, 2019 nguyenvanquan7826 TTツリー 51 回答

[qads]
二分探索木 (CNPTK) 内の各ノードのバイナリツリーです, キーロックボタンは、ツリーのすべてのノードをより考慮され、木の必須のすべてのノードの小さいキーを左に.
ここで、二分探索木の例である:

コンテンツ
ツリー構造
ツリーに要素を追加
ツリーを入力してください
[参照]ツリー
ツリー内のノードを探す
ツリー内のノードを削除する
コー​​ドの完全なリファレンス

二分探索木
CNPTK上のおかげでキー制約, 発見は、指向になる. さらに, 探索木構造が大幅に高速になったことで. Nは、ツリー内のノードの数、log2N平均約探索コストである場合.

ツリー構造:

typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu
     Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay

だから我々は、ツリー構造ツリーを持っている. 今、私たちはアクションの数がかかります.

もっと 1 ツリー内の要素

ツリーの元素Xを追加すると、CNPTKの制約を満たさなければならない. あなたは木の上のさまざまな場所を追加することができます, 私たちは、同じ検索操作を実行することができますので、あなたが最も便利になりますリーフノードを追加する場合. 検索処理が終了すると、より多くの余地を発見する時間である.

int insertNode(Tree &T, item x)	// chen 1 Node vao cay
{
	if (T != NULL)
	{
		if (T->key == x) return -1; 	// Node nay da co
		if (T->key > x) return insertNode(T->Left, x);	// chen vao Node trai
		else if (T->key < x) return insertNode(T->Right, x);	// chen vao Node phai
	}
	T = (Node *) malloc(sizeof(Node));
	if (T == NULL) return 0;	// khong du bo nho
	T->key = x;
	T->Left = T->Right = NULL;
	return 1;	// ok
}

つまり、蜂だ.

ツリーを入力してください

木が繰り返し挿入を入力している 1 一定の条件にツリーに要素、その後停止. 停止条件入力要素=以下のコードでは、 0.

void CreateTree(Tree &T)		// nhap cay
{
	int x;
	while (1)
	{
		printf("Nhap vao Node: ");
		scanf("%d", &x);
		if (x == 0) break; 	// x = 0 thi thoat
		int check = insertNode(T, x);
		if (check == -1) printf("Node da ton tai!");
		else if (check == 0) printf("Khong du bo nho");

	}
}

インポートが完了しました, なお、多くのそのような人々が、コードはツリーエントリの種類を知らない :3 (私はそのようになっている)

[参照]ツリー

二分探索木上の操作ブラウズツリーは正確にバイナリツリーのようなものです. 特に間の順序を参照するとき, ボタンシーケンスがキーの昇順に一連のボタンを与えるブラウズ. (1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 20, 23)

void LNR(Tree T)
{
     if(T!=NULL)
     {
	  LNR(T->Left);
	  printf("%d   ",T->key);
	  LNR(T->Right);
     }
}

あなたが同じことをする前または後の順序でブラウザ.

ツリー内のノードのkey = xを検索

Node* searchKey(Tree T, item x)		// tim nut co key x
{
	if (T!=NULL)
	{
		if (T->key == x) { Node *P = T; return P;}
		if (T->key > x) return searchKey(T->Left, x);
		if (T->key < x) return searchKey(T->Right, x);
	}
	return NULL;
}

彼自身は、上述した見つけることはかなり非常にシンプルかつ迅速である.

ツリー内のノードのkey = xを削除

ツリーから元素Xを廃棄するCNPTKの制約を確保するため. 持っている 3 終端ノードXの場合に発生することがあり:
– Xはリーフノードである: それは他の要素にフックアップされていないため、単純にXをキャンセル.

二分探索木上のボタンを削除

– Xのみ 1 ととも​​に (左または右): X Xをキャンセルする前に我々は彼の唯一の子に父親をフック.
– すべてのためのX 2 ととも​​に: これは、Xで直接キャンセルすることはできません十分に持っている 2 ととも​​に. 私は間接的な破壊します. 代わりにXを打ち消す, 我々は、ネットワーク要素Qが見つかります. この要素は、最大値を有する. Qに格納されている情報は、Xでの店舗に転送されます. 後で, ボタンは次のように本当にQをキャンセルされます 2 最初のケース. 問題は、このようなことにQを選択するときにXの代わりに流量Q, 工場はCNPTKまま.
持っている 2 満足な要素:
+ 最小の要素 (一番左の) 苗の上.
+ 最大の要素 (右端の) 左側のツリーに.
選択要素は、プログラミングの気まぐれに完全に依存しているネットワーク要素である. このコードでは、私はほとんどに要素を選択.

ノードが二分木検索を削除します

int delKey(Tree &T, item x)     // xoa nut co key x
{
    if (T==NULL) return 0;
    else if (T->key > x) return delKey(T->Left, x);
    else if (T->key < x) return delKey(T->Right, x);
    else // T->key == x
    {
        if (T->Left == NULL) T = T->Right;    // Node chi co cay con phai
        else if (T->Right == NULL) T = T->Left;   // Node chi co cay con trai
        else // Node co ca 2 con
        {
            Node *Q = T->Left;
            while (Q->Right != NULL)
            {
                Q = Q->Right;
            }
            T->key = Q->key;
            delKey(T->Left, Q->key);
        }
    }
    return 1;
}

だから、ノードを削除終了した.

リファレンスコード:

#include<stdlib.h>
#include<stdio.h>
 
typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu
     Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay
 
int insertNode(Tree &T, item x) // chen 1 Node vao cay
{
    if (T != NULL)
    {
        if (T->key == x) return -1;  // Node nay da co
        if (T->key > x) return insertNode(T->Left, x); // chen vao Node trai
        else if (T->key < x) return insertNode(T->Right, x);   // chen vao Node phai
    }
    T = (Node *) malloc(sizeof(Node));
    if (T == NULL) return 0;    // khong du bo nho
    T->key = x;
    T->Left = T->Right = NULL;
    return 1;   // ok
}
 
void CreateTree(Tree &T)        // nhap cay
{
    int x;
    while (1)
    {
        printf("Nhap vao Node: ");
        scanf("%d", &x);
        if (x == 0) break;  // x = 0 thi thoat
        int check = insertNode(T, x);
        if (check == -1) printf("Node da ton tai!");
        else if (check == 0) printf("Khong du bo nho");
 
    }
}
 
// Duyet theo LNR
void LNR(Tree T)
{
     if(T!=NULL)
     {
      LNR(T->Left);
      printf("%d   ",T->key);
      LNR(T->Right);
     }
}
 
Node* searchKey(Tree T, item x)     // tim nut co key x
{
    if (T!=NULL)
    {
        if (T->key == x) { Node *P = T; return P;}
        if (T->key > x) return searchKey(T->Left, x);
        if (T->key < x) return searchKey(T->Right, x);
    }
    return NULL;
}
 
int delKey(Tree &T, item x)     // xoa nut co key x
{
    if (T==NULL) return 0;
    else if (T->key > x) return delKey(T->Left, x);
    else if (T->key < x) return delKey(T->Right, x);
    else // T->key == x
    {
        if (T->Left == NULL) T = T->Right;    // Node chi co cay con phai
        else if (T->Right == NULL) T = T->Left;   // Node chi co cay con trai
        else // Node co ca 2 con
        {
            Node *Q = T->Left;
            while (Q->Right != NULL)
            {
                Q = Q->Right;
            }
            T->key = Q->key;
            delKey(T->Left, Q->key);
        }
    }
    return 1;
}
 
int main()
{
    Tree T;
    T=NULL; //Tao cay rong
 
    CreateTree(T); //Nhap cay
    //duyet cay
    printf("Duyet cay theo LNR: \n");
    LNR(T);
    printf("\n");
 
    Node *P;
    item x;
    printf("Nhap vao key can tim: ");
    scanf("%d", &x);
    P = searchKey(T, x);
    if (P != NULL) printf("Tim thay key %d\n", P->key);
    else printf("Key %d khong co trong cay\n", x);
 
    if (delKey(T, x)) printf("Xoa thanh cong\n");
    else printf("Khong tim thay key %d can xoan", x);
    printf("Duyet cay theo LNR: \n");
    LNR(T);
    printf("\n");
    return 0;
}

続きを読む: 二分探索木にバイナリツリーをジャンプ