導航:首頁 > 源碼編譯 > 通用的樹搜索演算法

通用的樹搜索演算法

 發布時間：2022-10-03 20:28:38

『壹』 二叉查找樹演算法

#include <iostream>using namespace std;typedef struct _node{ int data; struct _node *pLeftPtr; struct _node *pRightPtr;}BTreeNode;class BinarySearchTree{public: BinarySearchTree(); ~BinarySearchTree(); bool Create(int* pIntArray,int arrLength); bool Insert(int data); // 查找節點，searchLength為搜索長度，返回值為true表示指定的數據存在，否則不存在 bool Find(int data, int* searchLength); // 中序輸出二叉樹 void MidOutput(); // 釋放內存 void Destroy(); void Delete(int data);protected: bool Insert(BTreeNode* pRoot, int data); bool Find(BTreeNode* pRoot,int data, int *searchLength); void Delete(BTreeNode* &pRoot, int data); void MidOutput(BTreeNode* pRoot); void Destroy(BTreeNode* pRoot);private: BTreeNode* m_pRoot; //二叉搜索樹根節點};BinarySearchTree::BinarySearchTree(){ m_pRoot = NULL;}BinarySearchTree::~BinarySearchTree(){ Destroy();}bool BinarySearchTree::Create(int* pIntArray,int arrLength){ for(int i=0; i<arrLength; i++) { if(!Insert(*(pIntArray+i))) return false; } return true;}bool BinarySearchTree::Insert(BTreeNode* pRoot, int data){ BTreeNode* pNewNode = new BTreeNode; if(pNewNode == NULL) return false; pNewNode->data = data; pNewNode->pLeftPtr = NULL; pNewNode->pRightPtr = NULL; BTreeNode* pCurrentNode = pRoot; BTreeNode* pParentNode = pCurrentNode;// 保存父節點的指針 int flag = 0;// 標記插入節點的位置 if(pCurrentNode == NULL) { m_pRoot = pNewNode; }else{ while(pCurrentNode) { if(data < pCurrentNode->data) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pLeftPtr; flag = 0; }else if(data > pCurrentNode->data){ pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; flag = 1; } } if(flag == 0) { pParentNode->pLeftPtr = pNewNode; }else{ pParentNode->pRightPtr = pNewNode; } } return true; }bool BinarySearchTree::Insert(int data){ return Insert(m_pRoot,data);}bool BinarySearchTree::Find(BTreeNode* pRoot,int data, int *searchLength){ if(pRoot == NULL) { *searchLength = 0; return false; } BTreeNode* pCurrentNode = pRoot; static int length = 0; while(pCurrentNode != NULL) { if(data == pCurrentNode->data) { *searchLength = length; cout<<"數字"<<data<<"存在二叉樹中,查找長度為: "<<endl<<length<<endl; return true; }else if(data < pCurrentNode->data) { length ++; pCurrentNode = pCurrentNode->pLeftPtr; }else{ length ++; pCurrentNode = pCurrentNode->pRightPtr; } } *searchLength = length; cout<<"數字"<<data<<"不在二叉樹中,查找長度為: "<<endl<<length<<endl; length = 0; // 每次查找結束，重新賦值為0 return false;}bool BinarySearchTree::Find(int data, int* searchLength){ return Find(m_pRoot,data,searchLength);}void BinarySearchTree::Destroy(BTreeNode* pRoot){ BTreeNode* pCurrentNode = pRoot; if(pCurrentNode == NULL) return; Destroy(pCurrentNode->pLeftPtr); Destroy(pCurrentNode->pRightPtr); delete pCurrentNode; m_pRoot = NULL;}void BinarySearchTree::Destroy(){ Destroy(m_pRoot);}void BinarySearchTree::MidOutput(BTreeNode* pRoot){ if(pRoot) { MidOutput(pRoot->pLeftPtr); cout<<pRoot->data <<" "; MidOutput(pRoot->pRightPtr); }}void BinarySearchTree::MidOutput(){ MidOutput(m_pRoot);}void BinarySearchTree::Delete(int data){ Delete(m_pRoot,data);}void BinarySearchTree::Delete(BTreeNode* &pRoot, int data){ if(!pRoot) return; else if(data == pRoot->data){ if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr == NULL) // 葉子節點 { delete pRoot; pRoot = NULL; }else if(pRoot->pLeftPtr != NULL && pRoot->pRightPtr == NULL){ // 只有左子樹 BTreeNode* pNode = pRoot->pLeftPtr; delete pRoot; pRoot = pNode; }else if(pRoot->pLeftPtr == NULL && pRoot->pRightPtr != NULL){ // 只有右子樹 BTreeNode* pNode = pRoot->pRightPtr; delete pRoot; pRoot = pNode; }else{ // 有左右子樹 // 找到左子樹的最大節點 BTreeNode* pCurrentNode = pRoot->pLeftPtr; BTreeNode* pParentNode = NULL; while(pCurrentNode->pRightPtr != NULL) { pParentNode = pCurrentNode; pCurrentNode = pCurrentNode->pRightPtr; } pRoot->data = pCurrentNode->data; if(pParentNode) { pParentNode->pRightPtr = pCurrentNode->pLeftPtr; }else{ pRoot->pLeftPtr= pCurrentNode->pLeftPtr; } delete pCurrentNode; } }else if(data < pRoot->data) Delete(pRoot->pLeftPtr, data); else Delete(pRoot->pRightPtr, data);}void main(){ int data[8]; cout<<"請輸入整形數據, 數據用空格隔開, 回車鍵結束輸入"<<endl; for(int i=0; i<8; i++) cin>>data[i]; // int data[8] = {13,15,6,20,14,5,7,18}; BinarySearchTree tree; tree.Create(data,sizeof(data)/sizeof(data[0])); cout<<"插入數據後的二叉樹為: "<<endl; tree.MidOutput(); cout<<endl; int len_1=0; int len_2=0; tree.Find(14,&len_1); tree.Find(21,&len_2); tree.Delete(20); cout<<"刪除數字20後的二叉樹結果: "<<endl; tree.MidOutput(); cout<<endl; tree.Delete(15); cout<<"刪除數字15後的二叉樹結果: "<<endl; tree.MidOutput(); cout<<endl;}

『貳』 樹形結構演算法有哪些

你說的是遍歷樹形結構的演算法吧。如果這是一棵不規則的樹，可以分為廣度和深度搜索。如果是二叉樹，一般有三種：先序遍歷，中序遍歷，後序遍歷。如果裡面的數據是有規則的存儲，如紅黑樹，根據需要可以有不同的演算法。

『叄』 關於二叉搜索樹搜索的遞歸演算法

#include <iostream>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#ifndef NULL
#define NULL 0
#endif

#ifndef MAXSIZE
#define MAXSIZE 10
#endif

typedef struct BST//Binary Search Tree
{
int key;
//maybe there are some other satellites

struct BST* left;
struct BST* right;
struct BST* parent;
} BST;

BST* root=NULL;

void BST_Insert(int key)//add value key to the Binary Search Tree
{
BST* y=NULL;//y records the parent node
BST* x=root;//x records the current node

BST* node = new BST();
node->key = key;
node->left = NULL;
node->right = NULL;
node->parent = NULL;

while(x!=NULL)
{
y=x;

if(key<x->key)
x=x->left;
else
x=x->right;
}

node->parent=y;

if(y==NULL)
root = node;
else
{
if(key<y->key)
y->left=node;
else
y->right=node;
}
}

void BST_Delete(BST* p)
{
if(p)
{
BST_Delete(p->left);
BST_Delete(p->right);
delete p;
}
}

void BST_Build()
{
int temp;

cout<<"Original Input:"<<endl;
for(int i=0;i<MAXSIZE;i++)
{
temp=rand()%MAXSIZE;
cout<<temp<<" ";
BST_Insert(temp);
}
cout<<endl;
}

void BST_Inorder_Walk(BST* p)
{

if(p)
{
BST_Inorder_Walk(p->left);
cout<<p->key<<" ";
BST_Inorder_Walk(p->right);
}
}

void BST_Preorder_Walk(BST* p)
{

if(p)
{
cout<<p->key<<" ";
BST_Preorder_Walk(p->left);
BST_Preorder_Walk(p->right);
}
}

void BST_Postorder_Walk(BST* p)
{
if(p)
{
BST_Postorder_Walk(p->left);
BST_Postorder_Walk(p->right);
cout<<p->key<<" ";
}
}

void BST_Layer_Walk()
{
queue<BST*> queue;
BST* p;
queue.push(root);

while(!queue.empty())
{
p=queue.front();

queue.pop();
if(p->left)
queue.push(p->left);
if(p->right)
queue.push(p->right);

cout<<p->key<<" ";
}

cout<<endl;
}

void Inorder_Walk(BST* node=root)
{
stack<BST*> stk;

while(!stk.empty()||node)
{
if(node)
{
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
cout<<node->key<<" ";
stk.pop();
node=node->right;
}
}
}

void Preorder_Walk(BST* node=root)
{
stack<BST*> stk;

while(!stk.empty()||node)
{
if(node)
{
cout<<node->key<<" ";
stk.push(node);
node=node->left;
}
else
{
node=stk.top();
stk.pop();
node=node->right;
}
}
}

void Postorder_Walk(BST* node=root)
{
stack<BST*> stk;
BST* p;
int flag = 0;//0 stands for left, 1 stands for right

do
{
while(node)
{
stk.push(node);
node=node->left;
}

p=NULL;
flag=0;

while(!stk.empty()&&(flag==0))
{
node=stk.top();
if(node->right==p)
{
stk.pop();
p=node;
cout<<node->key<<" ";
}
else
{
node= node->right;
flag=1;
}
}
}while(!stk.empty());
}

int main(int argc,char* argv[])
{
int input;

BST_Build();

cout<<"Inorder Walk:"<<endl;
//BST_Inorder_Walk(root);
Inorder_Walk();
cout<<endl;

cout<<"Preorder Walk:"<<endl;
BST_Preorder_Walk(root);
cout<<endl;

cout<<"Stack Preorder Walk:"<<endl;
Preorder_Walk(root);
cout<<endl;

cout<<"Postorder Walk:"<<endl;
BST_Postorder_Walk(root);
cout<<endl;

cout<<"Stack Postorder Walk:"<<endl;
Postorder_Walk(root);
cout<<endl;

cout<<"Layer Walk:"<<endl;
BST_Layer_Walk();

BST_Delete(root);

cout<<endl;
system("pause");
return 0;
}

『肆』 c++二叉搜索樹演算法

#include<iostream>
usingnamespacestd;

typedefstruct_node
{
	intdata;
	struct_node*pLeftPtr;
	struct_node*pRightPtr;
}BTreeNode;

classBinarySearchTree
{
public:
	BinarySearchTree();
	~BinarySearchTree();
	boolCreate(int*pIntArray,intarrLength);
	boolInsert(intdata);
	//查找節點，searchLength為搜索長度，返回值為true表示指定的數據存在，否則不存在
	boolFind(intdata,int*searchLength);
	//中序輸出二叉樹
	voidMidOutput();
	//釋放內存
	voidDestroy();
	voidDelete(intdata);
protected:
	boolInsert(BTreeNode*pRoot,intdata);
	boolFind(BTreeNode*pRoot,intdata,int*searchLength);
	voidDelete(BTreeNode*&pRoot,intdata);
	voidMidOutput(BTreeNode*pRoot);
	voidDestroy(BTreeNode*pRoot);
private:
	BTreeNode*m_pRoot;//二叉搜索樹根節點
};

BinarySearchTree::BinarySearchTree()
{
	m_pRoot=NULL;
}

BinarySearchTree::~BinarySearchTree()
{
	Destroy();
}

boolBinarySearchTree::Create(int*pIntArray,intarrLength)
{
	for(inti=0;i<arrLength;i++)
	{
		if(!Insert(*(pIntArray+i)))
			returnfalse;
	}
	returntrue;
}

boolBinarySearchTree::Insert(BTreeNode*pRoot,intdata)
{
	BTreeNode*pNewNode=newBTreeNode;
	if(pNewNode==NULL)
		returnfalse;
	pNewNode->data=data;
	pNewNode->pLeftPtr=NULL;
	pNewNode->pRightPtr=NULL;

	BTreeNode*pCurrentNode=pRoot;
	BTreeNode*pParentNode=pCurrentNode;//保存父節點的指針
	intflag=0;//標記插入節點的位置

	if(pCurrentNode==NULL)
	{
		m_pRoot=pNewNode;
	}else{
		while(pCurrentNode)
		{
			if(data<pCurrentNode->data)
			{
				pParentNode=pCurrentNode;
				pCurrentNode=pCurrentNode->pLeftPtr;
				flag=0;
			}elseif(data>pCurrentNode->data){
				pParentNode=pCurrentNode;
				pCurrentNode=pCurrentNode->pRightPtr;
				flag=1;
			}
		}

		if(flag==0)
		{
			pParentNode->pLeftPtr=pNewNode;
		}else{
			pParentNode->pRightPtr=pNewNode;
		}

	}
	returntrue;	
}

boolBinarySearchTree::Insert(intdata)
{
	returnInsert(m_pRoot,data);
}

boolBinarySearchTree::Find(BTreeNode*pRoot,intdata,int*searchLength)
{
	if(pRoot==NULL)
	{
		*searchLength=0;
		returnfalse;
	}

	BTreeNode*pCurrentNode=pRoot;
	staticintlength=0;
	
	while(pCurrentNode!=NULL)
	{
		if(data==pCurrentNode->data)
		{
			*searchLength=length;
			cout<<"數字"<<data<<"存在二叉樹中,查找長度為:"<<endl<<length<<endl;
			returntrue;
		}elseif(data<pCurrentNode->data)
		{
			length++;
			pCurrentNode=pCurrentNode->pLeftPtr;
		}else{
			length++;
			pCurrentNode=pCurrentNode->pRightPtr;
		}
	}
	*searchLength=length;
	cout<<"數字"<<data<<"不在二叉樹中,查找長度為:"<<endl<<length<<endl;
	length=0;//每次查找結束，重新賦值為0
	returnfalse;
}

boolBinarySearchTree::Find(intdata,int*searchLength)
{
	returnFind(m_pRoot,data,searchLength);
}

voidBinarySearchTree::Destroy(BTreeNode*pRoot)
{
	BTreeNode*pCurrentNode=pRoot;
	if(pCurrentNode==NULL)
		return;
	Destroy(pCurrentNode->pLeftPtr);
	Destroy(pCurrentNode->pRightPtr);
	deletepCurrentNode;
	m_pRoot=NULL;
}

voidBinarySearchTree::Destroy()
{
	Destroy(m_pRoot);
}

voidBinarySearchTree::MidOutput(BTreeNode*pRoot)
{
	if(pRoot)
	{
		MidOutput(pRoot->pLeftPtr);
		cout<<pRoot->data<<"";
		MidOutput(pRoot->pRightPtr);
	}
}


voidBinarySearchTree::MidOutput()
{
	MidOutput(m_pRoot);
}

voidBinarySearchTree::Delete(intdata)
{
	Delete(m_pRoot,data);
}

voidBinarySearchTree::Delete(BTreeNode*&pRoot,intdata)
{
	if(!pRoot)
		return;
	elseif(data==pRoot->data){
			if(pRoot->pLeftPtr==NULL&&pRoot->pRightPtr==NULL)//葉子節點
			{
				deletepRoot;
				pRoot=NULL;
			}elseif(pRoot->pLeftPtr!=NULL&&pRoot->pRightPtr==NULL){//只有左子樹
				BTreeNode*pNode=pRoot->pLeftPtr;
				deletepRoot;
				pRoot=pNode;
			}elseif(pRoot->pLeftPtr==NULL&&pRoot->pRightPtr!=NULL){//只有右子樹
				BTreeNode*pNode=pRoot->pRightPtr;
				deletepRoot;
				pRoot=pNode;
			}else{//有左右子樹
				//找到左子樹的最大節點
				BTreeNode*pCurrentNode=pRoot->pLeftPtr;
				BTreeNode*pParentNode=NULL;
				while(pCurrentNode->pRightPtr!=NULL)
				{
					pParentNode=pCurrentNode;
					pCurrentNode=pCurrentNode->pRightPtr;
				}
				
				pRoot->data=pCurrentNode->data;
				if(pParentNode)
				{
					pParentNode->pRightPtr=pCurrentNode->pLeftPtr;
				}else{
					pRoot->pLeftPtr=pCurrentNode->pLeftPtr;
				}
				deletepCurrentNode;
			}
		}elseif(data<pRoot->data)
			Delete(pRoot->pLeftPtr,data);
		else
			Delete(pRoot->pRightPtr,data);
}

voidmain()
{
	intdata[8];
	cout<<"請輸入整形數據,數據用空格隔開,回車鍵結束輸入"<<endl;
	for(inti=0;i<8;i++)
		cin>>data[i];
	//intdata[8]={13,15,6,20,14,5,7,18};
	BinarySearchTreetree;
	tree.Create(data,sizeof(data)/sizeof(data[0]));
	cout<<"插入數據後的二叉樹為:"<<endl;
	tree.MidOutput();
	cout<<endl;

	intlen_1=0;
	intlen_2=0;
	tree.Find(14,&len_1);
	tree.Find(21,&len_2);

	tree.Delete(20);
	cout<<"刪除數字20後的二叉樹結果:"<<endl;
	tree.MidOutput();
	cout<<endl;
	tree.Delete(15);
	cout<<"刪除數字15後的二叉樹結果:"<<endl;
	tree.MidOutput();
	cout<<endl;
}

『伍』 bfs演算法是什麼

廣度優先搜索演算法（英語：Breadth-First Search，縮寫為BFS），又譯作寬度優先搜索，或橫向優先搜索，是一種圖形搜索演算法。

簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。廣度優先搜索的實現一般採用open-closed表。

作法

BFS是一種暴力搜索演算法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能地址，徹底地搜索整張圖，直到找到結果為止。BFS並不使用經驗法則演算法。

從演算法的觀點，所有因為展開節點而得到的子節點都會被加進一個先進先出的隊列中。

一般的實現里，其鄰居節點尚未被檢驗過的節點會被放置在一個被稱為open的容器中（例如隊列或是鏈表），而被檢驗過的節點則被放置在被稱為closed的容器中。


(5)通用的樹搜索演算法擴展閱讀：

廣度優先搜索演算法的應用

廣度優先搜索演算法能用來解決圖論中的許多問題，例如：

1、查找圖中所有連接組件（ConnectedComponent）。一個連接組件是圖中的最大相連子圖。

2、查找連接組件中的所有節點。

3、查找非加權圖中任兩點的最短路徑。

4、測試一圖是否為二分圖。

5、（Reverse）Cuthill–McKee演算法

『陸』 自適應樹搜索協議的詳細過程 作業急需解答

該協議是一種有限爭用（limited-contention）協議，分組競爭。主要是為了避免介質訪問控制子層的沖突太多！
，協議的基本思想是將所有站點組織在一棵二叉樹中（站點在樹葉上），從樹根開始，首先將一個時隙分配給樹根（即樹根下的所有站點都可以在該時隙競爭信道）；如果發生沖突，則按深度優先法，從左到右遞歸地搜索該節點的子節點（即將下一個時隙分配給搜索到的子節點）；如果時隙空閑或者只有一個站點發送（發送成功），則停止搜索該節點；該過程不斷重復，直至將整棵樹搜索一遍；然後從樹根開始新一輪的搜索。
該協議的改進演算法：根據系統負載情況，動態地決定從哪一個節點開始往下搜索。
基本就這些了！

『柒』 有哪位可以舉一個二進制樹形搜索的演算法實例

加法法則：
0＋0＝0，0＋1＝1＋0＝1，1＋1＝10減法，當需要向上一位借數時，必須把上一位的1看成下一位的（2）10。
減法法則：
0
-
0
=
0
1
-
0
=
1
1
-
1
=
0
0
-
1
=
1
有借位，借1當(10)2
0
-
1
-
1
=
0
有借位
1
-
1
-
1
=
1
有借位。乘法法則：
0×0＝0，0×1＝1×0＝0，1×1＝1除法應注意：
0÷0
=
0
0÷1
=
0
1÷0
=
0
(無意義)除法法則：
0÷1＝0，1÷1＝1
二進制與

『捌』 bfs演算法是什麼

bfs演算法寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。

與深度優先搜索的對比

1、把根節點壓入棧中。

2、每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。

3、找到所要找的元素時結束程序。

4、如果遍歷整個樹還沒有找到，結束程序。

閱讀全文

與通用的樹搜索演算法相關的資料

熱點內容
小天才app怎麼升級v242 瀏覽：544
簡單手工解壓玩具製作大全 瀏覽：927
免費編程電子書 瀏覽：869
想玩游戲什麼app最合適 瀏覽：560
安卓手機如何用airportspro 瀏覽：449
怎麼清理idea編譯緩存 瀏覽：951
鏡頭app怎麼推廣 瀏覽：437
什麼app隨便看電視劇 瀏覽：307
2021程序員薪酬 瀏覽：708
糖豆廣場怎麼下載app 瀏覽：213
qtvs2019選哪個編譯器 瀏覽：124
壓縮空氣管能焊嗎 瀏覽：284
linux中yum命令 瀏覽：397
在職演算法工程師 瀏覽：706
電碼加密函數方法有幾種 瀏覽：802
後綴是pdf 瀏覽：720
pr導出壓縮 瀏覽：32
命令語氣 瀏覽：245
脊柱解剖pdf 瀏覽：714
plc入門編程題目及答案 瀏覽：383
  • baicheng
  • suizhou
  • gongzhuling
  • much
  • such
  • within
  • video
  • corner
  • protection
  • engine
  • conclude
  • pursue
  • smart
  • noise
  • slide
  • sand
  • disaster
  • storage
  • celebration
  • basket
  • rat
  • enthusiasm
  • scare
  • amid
  • blend
  • automatically
  • banker
  • fleet
  • cautious
  • prey
  • conceptual
  • picnic
  • interpreter
  • lifelong
  • mist
  • anticipation
  • landlord
  • environmentally
  • computerized
  • monastery
  • retaliation
  • seduce
  • subside
  • mow
  • ventilation
  • adherence
  • sluggish
  • innate
  • gritty
  • yen
  • anxiously
  • conducive
  • schoolchild
  • wrongly
  • yarn
  • rebirth
  • plop
  • mayonnaise
  • eschew
  • dynamite
  • heyday
  • mountainous
  • deftly
  • promulgate
  • scuba
  • apache
  • slang
  • screwdriver
  • cuddle
  • naturalistic
  • restraining
  • institutionalized
  • indelible
  • misread
  • syndicate
  • environmentalism
  • persistently
  • unanticipated
  • expletive
  • roost
  • barometer
  • outrun
  • stalker
  • franciscan
  • rile
  • claimant
  • peeled
  • populism
  • hyperactive
  • cantaloupe
  • tasteless
  • tomography
  • photovoltaic
  • payable
  • messianic
  • autopilot
  • humbly
  • epilepsy
  • premarital
  • adjudicate