[树] 在二分搜索树的一些操作

二月 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);
     }
}

你做同样的，为了在浏览器中之前或之后.

在树中寻找节点关键= 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;
}

发现自己上述非常简单快捷显著.

删除节点键= 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;
}

阅读更多: 跳二叉树成二进制搜索树