C语言实现二叉树的搜索及相关算法示例

2024-02-20 14:17:03 164

本文实例讲述了C语言实现二叉树的搜索及相关算法。分享给大家供大家参考，具体如下：

二叉树（二叉查找树）是这样一类的树，父节点的左边孩子的key都小于它，右边孩子的key都大于它。

二叉树在查找和存储中通常能保持logn的查找、插入、删除，以及前驱、后继，最大值，最小值复杂度，并且不占用额外的空间。

这里演示二叉树的搜索及相关算法：

#include
#include
usingnamespacestd;
classtree_node{
public:
intkey;
tree_node*left;
tree_node*right;
inttag;
tree_node(){
key=0;
left=right=NULL;
tag=0;
}
~tree_node(){}
};
voidvisit(intvalue){
printf("%d\n",value);
}
//插入
tree_node*insert_tree(tree_node*root,tree_node*node){
if(!node){
returnroot;
}
if(!root){
root=node;
returnroot;
}
tree_node*p=root;
while(p){
if(node->keykey){
if(p->left){
p=p->left;
}
else{
p->left=node;
break;
}
}
else{
if(p->right){
p=p->right;
}
else{
p->right=node;
break;
}
}
}
returnroot;
}
//查询key所在node
tree_node*search_tree(tree_node*root,intkey){
tree_node*p=root;
while(p){
if(keykey){
p=p->left;
}
elseif(key>p->key){
p=p->right;
}
else{
returnp;
}
}
returnNULL;
}
//创建树
tree_node*create_tree(tree_node*t,intn){
tree_node*root=t;
for(inti=1;ileft){returnNULL;}
tree_node*p=root->left;
while(p->right){
p=p->right;
}
returnp;
}
//节点后继
tree_node*tree_suc(tree_node*root){
if(!root->right){returnNULL;}
tree_node*p=root->right;
while(p->left){
p=p->left;
}
returnp;
}
//中序遍历
voidtree_walk_mid(tree_node*root){
if(!root){return;}
tree_walk_mid(root->left);
visit(root->key);
tree_walk_mid(root->right);
}
//中序遍历非递归
voidtree_walk_mid_norecursive(tree_node*root){
if(!root){return;}
tree_node*p=root;
stacks;
while(!s.empty()||p){
while(p){
s.push(p);
p=p->left;
}
if(!s.empty()){
p=s.top();
s.pop();
visit(p->key);
p=p->right;
}
}
}
//前序遍历
voidtree_walk_pre(tree_node*root){
if(!root){return;}
visit(root->key);
tree_walk_pre(root->left);
tree_walk_pre(root->right);
}
//前序遍历非递归
voidtree_walk_pre_norecursive(tree_node*root){
if(!root){return;}
stacks;
tree_node*p=root;
s.push(p);
while(!s.empty()){
tree_node*node=s.top();
s.pop();
visit(node->key);
if(node->right){
s.push(node->right);
}
if(node->left){
s.push(node->left);
}
}
}
//后序遍历
voidtree_walk_post(tree_node*root){
if(!root){return;}
tree_walk_post(root->left);
tree_walk_post(root->right);
visit(root->key);
}
//后序遍历非递归
voidtree_walk_post_norecursive(tree_node*root){
if(!root){return;}
stacks;
s.push(root);
while(!s.empty()){
tree_node*node=s.top();
if(node->tag!=1){
node->tag=1;
if(node->right){
s.push(node->right);
}
if(node->left){
s.push(node->left);
}
}
else{
visit(node->key);
s.pop();
}
}
}
//层级遍历非递归
voidtree_walk_level_norecursive(tree_node*root){
if(!root){return;}
queueq;
tree_node*p=root;
q.push(p);
while(!q.empty()){
tree_node*node=q.front();
q.pop();
visit(node->key);
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
}
//拷贝树
tree_node*tree_copy(tree_node*root){
if(!root){returnNULL;}
tree_node*newroot=newtree_node();
newroot->key=root->key;
newroot->left=tree_copy(root->left);
newroot->right=tree_copy(root->right);
returnnewroot;
}
//拷贝树
tree_node*tree_copy_norecursive(tree_node*root){
if(!root){returnNULL;}
tree_node*newroot=newtree_node();
newroot->key=root->key;
stacks1,s2;
tree_node*p1=root;
tree_node*p2=newroot;
s1.push(root);
s2.push(newroot);
while(!s1.empty()){
tree_node*node1=s1.top();
s1.pop();
tree_node*node2=s2.top();
s2.pop();
if(node1->right){
s1.push(node1->right);
tree_node*newnode=newtree_node();
newnode->key=node1->right->key;
node2->right=newnode;
s2.push(newnode);
}
if(node1->left){
s1.push(node1->left);
tree_node*newnode=newtree_node();
newnode->key=node1->left->key;
node2->left=newnode;
s2.push(newnode);
}
}
returnnewroot;
}
intmain(){
tree_nodeT[6];
for(inti=0;i<6;i++){
T[i].key=i*2;
}
T[0].key=5;
tree_node*root=create_tree(T,6);
//tree_walk_mid(root);
//tree_walk_mid_norecursive(root);
//tree_walk_pre(root);
//tree_walk_pre_norecursive(root);
//tree_walk_post(root);
//tree_walk_post_norecursive(root);
//tree_walk_level_norecursive(root);
visit(search_tree(root,6)->key);
visit(tree_pre(root)->key);
visit(tree_suc(root)->key);
//tree_node*newroot=tree_copy_norecursive(root);
//tree_walk_mid(newroot);
return0;
}

希望本文所述对大家C语言程序设计有所帮助。

C语言实现二叉树的搜索及相关算法示例

热门推荐

随机推荐