通用的树搜索算法

‘壹’ 二叉查找树算法

#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、如果遍历整个树还没有找到，结束程序。