C/C++，樹算法——二叉樹的插入(Insert)算法之源程序

1 文本格式

#include<iostream>
using namespace std;

// A BTree node
class BTreeNode
{
?? ?int* keys; // An array of keys
?? ?int t;?? ? // Minimum degree (defines the range for number of keys)
?? ?BTreeNode** C; // An array of child pointers
?? ?int n;?? ? // Current number of keys
?? ?bool leaf; // Is true when node is leaf. Otherwise false
public:
?? ?BTreeNode(int _t, bool _leaf); // Constructor

?? ?// A utility function to insert a new key in the subtree rooted with
?? ?// this node. The assumption is, the node must be non-full when this
?? ?// function is called
?? ?void insertNonFull(int k);

?? ?// A utility function to split the child y of this node. i is index of y in
?? ?// child array C[]. The Child y must be full when this function is called
?? ?void splitChild(int i, BTreeNode* y);

?? ?// A function to traverse all nodes in a subtree rooted with this node
?? ?void traverse();

?? ?// A function to search a key in the subtree rooted with this node.
?? ?BTreeNode* search(int k); // returns NULL if k is not present.

?? ?// Make BTree friend of this so that we can access private members of this
?? ?// class in BTree functions
?? ?friend class BTree;
};

// A BTree
class BTree
{
?? ?BTreeNode* root; // Pointer to root node
?? ?int t; // Minimum degree
public:
?? ?// Constructor (Initializes tree as empty)
?? ?BTree(int _t)
?? ?{
?? ??? ?root = NULL; t = _t;
?? ?}

?? ?// function to traverse the tree
?? ?void traverse()
?? ?{
?? ??? ?if (root != NULL) root->traverse();
?? ?}

?? ?// function to search a key in this tree
?? ?BTreeNode* search(int k)
?? ?{
?? ??? ?return (root == NULL) ? NULL : root->search(k);
?? ?}

?? ?// The main function that inserts a new key in this B-Tree
?? ?void insert(int k);
};

// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1)
{
?? ?// Copy the given minimum degree and leaf property
?? ?t = t1;
?? ?leaf = leaf1;

?? ?// Allocate memory for maximum number of possible keys
?? ?// and child pointers
?? ?keys = new int[2 * t - 1];
?? ?C = new BTreeNode * [2 * t];

?? ?// Initialize the number of keys as 0
?? ?n = 0;
}

// Function to traverse all nodes in a subtree rooted with this node
void BTreeNode::traverse()
{
?? ?// There are n keys and n+1 children, traverse through n keys
?? ?// and first n children
?? ?int i;
?? ?for (i = 0; i < n; i++)
?? ?{
?? ??? ?// If this is not leaf, then before printing key[i],
?? ??? ?// traverse the subtree rooted with child C[i].
?? ??? ?if (leaf == false)
?? ??? ??? ?C[i]->traverse();
?? ??? ?cout << " " << keys[i];
?? ?}

?? ?// Print the subtree rooted with last child
?? ?if (leaf == false)
?? ??? ?C[i]->traverse();
}

// Function to search key k in subtree rooted with this node
BTreeNode* BTreeNode::search(int k)
{
?? ?// Find the first key greater than or equal to k
?? ?int i = 0;
?? ?while (i < n && k > keys[i])
?? ??? ?i++;

?? ?// If the found key is equal to k, return this node
?? ?if (keys[i] == k)
?? ??? ?return this;

?? ?// If key is not found here and this is a leaf node
?? ?if (leaf == true)
?? ??? ?return NULL;

?? ?// Go to the appropriate child
?? ?return C[i]->search(k);
}

// The main function that inserts a new key in this B-Tree
void BTree::insert(int k)
{
?? ?// If tree is empty
?? ?if (root == NULL)
?? ?{
?? ??? ?// Allocate memory for root
?? ??? ?root = new BTreeNode(t, true);
?? ??? ?root->keys[0] = k; // Insert key
?? ??? ?root->n = 1; // Update number of keys in root
?? ?}
?? ?else // If tree is not empty
?? ?{
?? ??? ?// If root is full, then tree grows in height
?? ??? ?if (root->n == 2 * t - 1)
?? ??? ?{
?? ??? ??? ?// Allocate memory for new root
?? ??? ??? ?BTreeNode* s = new BTreeNode(t, false);

?? ??? ??? ?// Make old root as child of new root
?? ??? ??? ?s->C[0] = root;

?? ??? ??? ?// Split the old root and move 1 key to the new root
?? ??? ??? ?s->splitChild(0, root);

?? ??? ??? ?// New root has two children now. Decide which of the
?? ??? ??? ?// two children is going to have new key
?? ??? ??? ?int i = 0;
?? ??? ??? ?if (s->keys[0] < k)
?? ??? ??? ??? ?i++;
?? ??? ??? ?s->C[i]->insertNonFull(k);

?? ??? ??? ?// Change root
?? ??? ??? ?root = s;
?? ??? ?}
?? ??? ?else // If root is not full, call insertNonFull for root
?? ??? ??? ?root->insertNonFull(k);
?? ?}
}

// A utility function to insert a new key in this node
// The assumption is, the node must be non-full when this
// function is called
void BTreeNode::insertNonFull(int k)
{
?? ?// Initialize index as index of rightmost element
?? ?int i = n - 1;

?? ?// If this is a leaf node
?? ?if (leaf == true)
?? ?{
?? ??? ?// The following loop does two things
?? ??? ?// a) Finds the location of new key to be inserted
?? ??? ?// b) Moves all greater keys to one place ahead
?? ??? ?while (i >= 0 && keys[i] > k)
?? ??? ?{
?? ??? ??? ?keys[i + 1] = keys[i];
?? ??? ??? ?i--;
?? ??? ?}

?? ??? ?// Insert the new key at found location
?? ??? ?keys[i + 1] = k;
?? ??? ?n = n + 1;
?? ?}
?? ?else // If this node is not leaf
?? ?{
?? ??? ?// Find the child which is going to have the new key
?? ??? ?while (i >= 0 && keys[i] > k)
?? ??? ??? ?i--;

?? ??? ?// See if the found child is full
?? ??? ?if (C[i + 1]->n == 2 * t - 1)
?? ??? ?{
?? ??? ??? ?// If the child is full, then split it
?? ??? ??? ?splitChild(i + 1, C[i + 1]);

?? ??? ??? ?// After split, the middle key of C[i] goes up and
?? ??? ??? ?// C[i] is splitted into two. See which of the two
?? ??? ??? ?// is going to have the new key
?? ??? ??? ?if (keys[i + 1] < k)
?? ??? ??? ??? ?i++;
?? ??? ?}
?? ??? ?C[i + 1]->insertNonFull(k);
?? ?}
}

// A utility function to split the child y of this node
// Note that y must be full when this function is called
void BTreeNode::splitChild(int i, BTreeNode* y)
{
?? ?// Create a new node which is going to store (t-1) keys
?? ?// of y
?? ?BTreeNode* z = new BTreeNode(y->t, y->leaf);
?? ?z->n = t - 1;

?? ?// Copy the last (t-1) keys of y to z
?? ?for (int j = 0; j < t - 1; j++)
?? ??? ?z->keys[j] = y->keys[j + t];

?? ?// Copy the last t children of y to z
?? ?if (y->leaf == false)
?? ?{
?? ??? ?for (int j = 0; j < t; j++)
?? ??? ??? ?z->C[j] = y->C[j + t];
?? ?}

?? ?// Reduce the number of keys in y
?? ?y->n = t - 1;

?? ?// Since this node is going to have a new child,
?? ?// create space of new child
?? ?for (int j = n; j >= i + 1; j--)
?? ??? ?C[j + 1] = C[j];

?? ?// Link the new child to this node
?? ?C[i + 1] = z;

?? ?// A key of y will move to this node. Find the location of
?? ?// new key and move all greater keys one space ahead
?? ?for (int j = n - 1; j >= i; j--)
?? ??? ?keys[j + 1] = keys[j];

?? ?// Copy the middle key of y to this node
?? ?keys[i] = y->keys[t - 1];

?? ?// Increment count of keys in this node
?? ?n = n + 1;
}

// Driver program to test above functions
int main()
{
?? ?BTree t(3); // A B-Tree with minimum degree 3
?? ?t.insert(10);
?? ?t.insert(20);
?? ?t.insert(5);
?? ?t.insert(6);
?? ?t.insert(12);
?? ?t.insert(30);
?? ?t.insert(7);
?? ?t.insert(17);

?? ?cout << "Traversal of the constructed tree is ";
?? ?t.traverse();

?? ?int k = 6;
?? ?(t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present";

?? ?k = 15;
?? ?(t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present";

?? ?return 0;
}
?

2 代碼格式

#include<iostream>
using namespace std;// A BTree node
class BTreeNode
{int* keys; // An array of keysint t;	 // Minimum degree (defines the range for number of keys)BTreeNode** C; // An array of child pointersint n;	 // Current number of keysbool leaf; // Is true when node is leaf. Otherwise false
public:BTreeNode(int _t, bool _leaf); // Constructor// A utility function to insert a new key in the subtree rooted with// this node. The assumption is, the node must be non-full when this// function is calledvoid insertNonFull(int k);// A utility function to split the child y of this node. i is index of y in// child array C[]. The Child y must be full when this function is calledvoid splitChild(int i, BTreeNode* y);// A function to traverse all nodes in a subtree rooted with this nodevoid traverse();// A function to search a key in the subtree rooted with this node.BTreeNode* search(int k); // returns NULL if k is not present.// Make BTree friend of this so that we can access private members of this// class in BTree functionsfriend class BTree;
};// A BTree
class BTree
{BTreeNode* root; // Pointer to root nodeint t; // Minimum degree
public:// Constructor (Initializes tree as empty)BTree(int _t){root = NULL; t = _t;}// function to traverse the treevoid traverse(){if (root != NULL) root->traverse();}// function to search a key in this treeBTreeNode* search(int k){return (root == NULL) ? NULL : root->search(k);}// The main function that inserts a new key in this B-Treevoid insert(int k);
};// Constructor for BTreeNode class
BTreeNode::BTreeNode(int t1, bool leaf1)
{// Copy the given minimum degree and leaf propertyt = t1;leaf = leaf1;// Allocate memory for maximum number of possible keys// and child pointerskeys = new int[2 * t - 1];C = new BTreeNode * [2 * t];// Initialize the number of keys as 0n = 0;
}// Function to traverse all nodes in a subtree rooted with this node
void BTreeNode::traverse()
{// There are n keys and n+1 children, traverse through n keys// and first n childrenint i;for (i = 0; i < n; i++){// If this is not leaf, then before printing key[i],// traverse the subtree rooted with child C[i].if (leaf == false)C[i]->traverse();cout << " " << keys[i];}// Print the subtree rooted with last childif (leaf == false)C[i]->traverse();
}// Function to search key k in subtree rooted with this node
BTreeNode* BTreeNode::search(int k)
{// Find the first key greater than or equal to kint i = 0;while (i < n && k > keys[i])i++;// If the found key is equal to k, return this nodeif (keys[i] == k)return this;// If key is not found here and this is a leaf nodeif (leaf == true)return NULL;// Go to the appropriate childreturn C[i]->search(k);
}// The main function that inserts a new key in this B-Tree
void BTree::insert(int k)
{// If tree is emptyif (root == NULL){// Allocate memory for rootroot = new BTreeNode(t, true);root->keys[0] = k; // Insert keyroot->n = 1; // Update number of keys in root}else // If tree is not empty{// If root is full, then tree grows in heightif (root->n == 2 * t - 1){// Allocate memory for new rootBTreeNode* s = new BTreeNode(t, false);// Make old root as child of new roots->C[0] = root;// Split the old root and move 1 key to the new roots->splitChild(0, root);// New root has two children now. Decide which of the// two children is going to have new keyint i = 0;if (s->keys[0] < k)i++;s->C[i]->insertNonFull(k);// Change rootroot = s;}else // If root is not full, call insertNonFull for rootroot->insertNonFull(k);}
}// A utility function to insert a new key in this node
// The assumption is, the node must be non-full when this
// function is called
void BTreeNode::insertNonFull(int k)
{// Initialize index as index of rightmost elementint i = n - 1;// If this is a leaf nodeif (leaf == true){// The following loop does two things// a) Finds the location of new key to be inserted// b) Moves all greater keys to one place aheadwhile (i >= 0 && keys[i] > k){keys[i + 1] = keys[i];i--;}// Insert the new key at found locationkeys[i + 1] = k;n = n + 1;}else // If this node is not leaf{// Find the child which is going to have the new keywhile (i >= 0 && keys[i] > k)i--;// See if the found child is fullif (C[i + 1]->n == 2 * t - 1){// If the child is full, then split itsplitChild(i + 1, C[i + 1]);// After split, the middle key of C[i] goes up and// C[i] is splitted into two. See which of the two// is going to have the new keyif (keys[i + 1] < k)i++;}C[i + 1]->insertNonFull(k);}
}// A utility function to split the child y of this node
// Note that y must be full when this function is called
void BTreeNode::splitChild(int i, BTreeNode* y)
{// Create a new node which is going to store (t-1) keys// of yBTreeNode* z = new BTreeNode(y->t, y->leaf);z->n = t - 1;// Copy the last (t-1) keys of y to zfor (int j = 0; j < t - 1; j++)z->keys[j] = y->keys[j + t];// Copy the last t children of y to zif (y->leaf == false){for (int j = 0; j < t; j++)z->C[j] = y->C[j + t];}// Reduce the number of keys in yy->n = t - 1;// Since this node is going to have a new child,// create space of new childfor (int j = n; j >= i + 1; j--)C[j + 1] = C[j];// Link the new child to this nodeC[i + 1] = z;// A key of y will move to this node. Find the location of// new key and move all greater keys one space aheadfor (int j = n - 1; j >= i; j--)keys[j + 1] = keys[j];// Copy the middle key of y to this nodekeys[i] = y->keys[t - 1];// Increment count of keys in this noden = n + 1;
}// Driver program to test above functions
int main()
{BTree t(3); // A B-Tree with minimum degree 3t.insert(10);t.insert(20);t.insert(5);t.insert(6);t.insert(12);t.insert(30);t.insert(7);t.insert(17);cout << "Traversal of the constructed tree is ";t.traverse();int k = 6;(t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present";k = 15;(t.search(k) != NULL) ? cout << "\nPresent" : cout << "\nNot Present";return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/207159.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/207159.shtml
英文地址，請注明出處：http://en.pswp.cn/news/207159.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

.NET中有多少種定時器

.NET中有多少種定時器

.NET中至少有6種定時器&#xff0c;每一種定時器都有它的用途和特點。根據定時器的應用場景&#xff0c;可以分為UI相關的定時器和UI無關的定時器。本文將簡單介紹這6種定時器的基本用法和特點。 UI定時器 .NET中的UI定時器主要是WinForm、WPF以及WebForm中的定時器。分別為&am…
閱讀更多...
dell服務器重啟后顯示器黑屏

dell服務器重啟后顯示器黑屏

1.硬件層面&#xff1a;觀察主機的指示燈 &#xff08;1&#xff09;指示燈偏黃&#xff0c;硬件存在問題&#xff08;內存條有靜電&#xff0c;拔出后用橡皮擦擦拭&#xff1b;或GPU松動&#xff09; a.電源指示燈黃&#xff0c;閃爍三下再閃爍一下&#xff0c;扣下主板上的紐…
閱讀更多...
Python Appium Selenium 查殺進程的實用方法

Python Appium Selenium 查殺進程的實用方法

一、前置說明 在自動化過程中&#xff0c;經常需要在命令行中執行一些操作&#xff0c;比如啟動應用、查殺應用等&#xff0c;因此可以封裝成一個CommandExecutor來專門處理這些事情。 二、操作步驟 # cmd_util.pyimport logging import os import platform import shutil i…
閱讀更多...
Java編程中通用的正則表達式（二）

Java編程中通用的正則表達式（二）

正則表達式&#xff0c;又稱正則式、規則表達式、正規表達式、正則模式或簡稱正則&#xff0c;是一種用來匹配字符串的工具。它是一種字符串模式的表示方法&#xff0c;可以用來檢索、替換和驗證文本。正則表達式是一個字符串&#xff0c;它描述了一些字符的組合&#xff0c;這…
閱讀更多...
dockers安裝rabbitmq

dockers安裝rabbitmq

RabbitMQ: easy to use, flexible messaging and streaming — RabbitMQhttps://www.rabbitmq.com/ Downloading and Installing RabbitMQ — RabbitMQ docker run -it --rm --name rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq:3.12-management 之后參照&#xff1a;dock…
閱讀更多...
高低壓配電智能監控系統

高低壓配電智能監控系統

高低壓配電智能監控系統是一種綜合運用物聯網、云計算、大數據和人工智能等技術的智能化監控系統&#xff0c;主要用于對高低壓配電設備進行實時監測、數據采集、故障預警和遠程管理。 該系統通過安裝智能傳感器、智能設備、網絡通訊技術等手段&#xff0c;依托電易云-智慧電力…
閱讀更多...
解決“由于找不到msvcr110.dll無法繼續執行”的錯誤問題，一鍵修復msvcr110.dll丟失

解決“由于找不到msvcr110.dll無法繼續執行”的錯誤問題，一鍵修復msvcr110.dll丟失

當你遇到“由于找不到msvcr110.dll無法繼續執行”的錯誤時&#xff0c;通常是因為你的電腦缺少相關的msvcr110.dll文件。如果你的電腦中缺失了msvcr110.dll文件丟失那么可以根據下面的方法嘗試解決msvcr110.dll丟失的問題。 一.解決msvcr110.dll丟失的方法 使用dll修復工具 D…
閱讀更多...
設計圖中時序圖

設計圖中時序圖

設計圖中的時序圖通常用于展示兩個或多個對象之間的交互和消息傳遞的順序。它是一種用于描述軟件或系統中的并發性和時序行為的工具。 以下是一個簡單的時序圖的示例&#xff1a; 首先&#xff0c;在時序圖中創建兩個對象&#xff0c;例如"對象A"和"對象B&quo…
閱讀更多...
學習筆記9——JUC三種量級的鎖機制

學習筆記9——JUC三種量級的鎖機制

學習筆記系列開頭慣例發布一些尋親消息 鏈接&#xff1a;https://baobeihuijia.com/bbhj/contents/3/197325.html 多線程訪問共享資源沖突 臨界區&#xff1a;一段代碼塊存在對共享資源的多線程讀寫操作&#xff0c;稱這段代碼塊為臨界區 競態條件&#xff1a;多個線程在臨界…
閱讀更多...
Linux OpenMP使用總結

Linux OpenMP使用總結

當涉及到編寫 Linux OpenMP 程序時&#xff0c;以下是體會&#xff1a; 了解 OpenMP 基礎&#xff1a;在使用 OpenMP 進行并行編程之前&#xff0c;確保您了解并行編程的基本概念和 OpenMP 的工作原理。您可以參考 OpenMP 的官方文檔或其他相關資源來獲取更多信息。配置 OpenM…
閱讀更多...
#HarmonyOS：@Styles裝飾器：定義組件重用樣式

#HarmonyOS：@Styles裝飾器：定義組件重用樣式

Styles可以定義在組件內或全局&#xff0c;在全局定義時需在方法名前面添加function關鍵字&#xff0c;組件內定義時則不需要添加function關鍵字。 組件內Styles的優先級高于全局Styles。 框架優先找當前組件內的Styles&#xff0c;如果找不到&#xff0c;則會全局查找。 // …
閱讀更多...
GO設計模式——3、抽象工廠模式（創建型）

GO設計模式——3、抽象工廠模式（創建型）

目錄 抽象工廠模式&#xff08;Abstract Factory Pattern&#xff09; 抽象工廠模式的核心角色 優缺點 代碼實現 抽象工廠模式&#xff08;Abstract Factory Pattern&#xff09; 抽象工廠模式&#xff08;Abstract Factory Pattern&#xff09;是圍繞一個超級工廠創建其他…
閱讀更多...
單詞倒排

單詞倒排

對字符串中的所有單詞進行倒排。 說明&#xff1a; 1、構成單詞的字符只有26個大寫或小寫英文字母&#xff1b; 2、非構成單詞的字符均視為單詞間隔符&#xff1b; 3、要求倒排后的單詞間隔符以一個空格表示&#xff1b;如果原字符串中相鄰單詞間有多個間隔符時&#xff0c;倒排…
閱讀更多...
yolo目標檢測+目標跟蹤+車輛計數+車輛分割+車道線變更檢測+速度估計

yolo目標檢測+目標跟蹤+車輛計數+車輛分割+車道線變更檢測+速度估計

這個項目使用YOLO進行車輛檢測&#xff0c;使用SORT&#xff08;簡單在線實時跟蹤器&#xff09;進行車輛跟蹤。該項目實現了以下任務&#xff1a; 車輛計數車道分割車道變更檢測速度估計將所有這些詳細信息轉儲到CSV文件中 車輛計數是指在道路上安裝相應設備&#xff0c;通過…
閱讀更多...
windows下 Tomcat啟動黑框隱藏

windows下 Tomcat啟動黑框隱藏

進入到 tomcat/bin 目錄下&#xff0c;找到此文件 setclasspath.bat &#xff0c;右鍵文本打開 找到此屬性 &#xff1a; set _RUNJAVA"%JRE_HOME%\bin\java.exe"修改成以下屬性&#xff0c;保存文件&#xff0c;重啟啟動tomcat會發現黑框不默認彈出了&#xff1a; …
閱讀更多...
使用hutool工具生成非對稱加密公私密鑰以及使用案例

使用hutool工具生成非對稱加密公私密鑰以及使用案例

1.導入hutool依賴 <dependency><groupId>cn.hutool</groupId><artifactId>hutool-all</artifactId><version>5.8.18</version></dependency>2.直接復制代碼 package com.common.utils;import cn.hutool.core.codec.Base64; i…
閱讀更多...
僅需30秒完美復刻任何人的聲音 - 最強AI音頻11Labs

僅需30秒完美復刻任何人的聲音 - 最強AI音頻11Labs

我的用詞一直都挺克制的&#xff0c;基本不會用到“最強”這個字眼。 但是這一次的這個AI應用&#xff0c;是我認為在TTS&#xff08;文字轉音頻&#xff09;這個領域&#xff0c;當之無愧的“最強”。 ElevenLabs&#xff0c;簡稱11Labs。 僅需30秒到5分鐘左右的極少的數據集…
閱讀更多...
機器學習-分類問題

機器學習-分類問題

前言 《機器學習-回歸問題》知道了回歸問題的處理方式,分類問題才是機器學習的重點.從數據角度講,回歸問題可以轉換為分類問題的微分 邏輯回歸 邏輯回歸&#xff08;Logistics Regression&#xff09;,邏輯回歸雖然帶有回歸字樣&#xff0c;但是邏輯回歸屬于分類算法。但只可…
閱讀更多...
極大提升GPT-4等模型推理效率，微軟、清華開源全新框架

極大提升GPT-4等模型推理效率，微軟、清華開源全新框架

隨著用戶需求的增多&#xff0c;GPT-4、Claude等模型在文本生成、理解、總結等方面的能力越來越優秀。但推理的效率并不高&#xff0c;因為&#xff0c;多數主流模型采用的是“順序生成詞”方法&#xff0c;會導致GPU利用率很低并帶來高延遲。 為了解決這一難題&#xff0c;清…
閱讀更多...
美國Linux服務器的iptables防火墻介紹

美國Linux服務器的iptables防火墻介紹

美國Linux服務器防火墻一般分為硬件防火墻和軟件防火墻&#xff0c;但不論是硬件防火墻還是軟件防火墻&#xff0c;都需要通過使用硬件作為聯機的介質&#xff0c;也需要使用軟件來設定美國Linux服務器安全政策&#xff0c;因此可以從使用的硬件與操作系統來加以區分。硬件防火…
閱讀更多...
最新文章

Copyright @ 2022~2023