二叉树创建及遍历算法

作者佚名技术来源程序设计浏览发布时间 2012-06-29

进栈*/
　 }
　 if(top!=NULL)
　 {
　　 pt = top->ptree; /*栈顶节点出栈*/
　　 ps = top;
　　 top = top->link;
　　 free(ps); /*释放栈顶节点空间*/
　　 printf("%c　　　 ",pt->data); /*访问根节点*/
　　 pt = pt->rchild; /*遍历节点右子树*/
　 }
　}
}
/*
　二叉查找树静态查找函数static_Search_STree()<非递归算法>
　参数描述：
　 BTNode *head: 二叉查找树的根节点指针
　 int key:　查找关键码
　返回值:
　 static_Search_STree = 键值为key的节点指针(找到)
　 static_Search_STree = NULL(没有找到)
*/
BTNode *static_Search_STree(BTNode *head,int key)
{
　while(head!=NULL)
　{
　 if(head->data == key)
　 {
　　 printf("\n数据域=%d\t地址=%d\t\n",head->data,head);
　　 return(head); /*找到*/
　 }
　 if(head->data > key)
　　 head = head->lchild; /*继续沿左子树搜索*/
　 else
　　 head = head->rchild; /*继续沿右子树搜索*/
　}
　return(NULL); /*没有查找*/
}
/*
　二叉查找树动态查找函数dynamic_Search_STree()<非递归算法>
　参数描述：
　 BTNode *head:　二叉查找树的根节点指针
　 BTNode **parent: 键值为key的节点的父节点指针的指针
　 BTNode **head:　键值为key的节点指针的指针(找到)或NULL(没有找到)
　 int key:　　查找关键码
　注意:
　 *parent == NULL 且 *p == NULL 没有找到(二叉树为空)
　 *parent == NULL 且 *p != NULL 找到(找到根节点)
　 *parent != NULL 且 *p == NULL 没有找到(叶节点)<可在parent后插入节点>
　 *parent != NULL 且 *p != NULL 找到(中间层节点)
*/
void dynamic_Search_STree(BTNode *head,BTNode **parent,BTNode **p,int key)
{
　*parent = NULL;
　*p = head;
　while(*p!=NULL)
　{
　 if((*p)->data == key)
　　 return; /*找到*/
　 *parent = *p; /*以当前节点为父,继续查找*/
　 if((*p)->data > key)
　　 *p = (*p)->lchild; /*继续沿左子树搜索*/
　 else
　　 *p = (*p)->rchild; /*继续沿右子树搜索*/
　}
}
/*
　二叉查找树插入节点函数Insert_Node_STree()<非递归算法>
　参数描述：
　 BTNode *head: 二叉查找树的根节点指针
　 int key:　查找关键码
　返回值:
　 Insert_Node_STree = 1 插入成功
　 Insert_Node_STree = 0 插入失败(节点已经存在)
*/
int Insert_Node_STree(BTNode *head,int key)
{
　BTNode *p,*q,*nnode;
　dynamic_Search_STree(head,&p,&q,key);
　if(q!=NULL)
　 return(0);　 /*节点在树中已经存在*/
　nnode = (BTNode *)malloc(sizeof(BTNode)); /*新建节点*/
　nnode->data = key;
　nnode->lchild = nnode->rchild = NULL;
　if(p==NULL)
　 head = p; /*原树为空,新建节点为查找树*/
　else
　{
　 if(p->data > key)
　　 p->lchild = nnode; /*作为左孩子节点*/
　 else
　　 p->rchild = nnode; /*作为右孩子节点*/
　}
　return(1); /*插入成功*/
}
/*
　二叉查找树插入一批节点函数Insert_Batch_Node_STree()<非递归算法>
　参数描述：
　 BTNode *head: 二叉查找树的根节点指针
　 int array[]: 被插入的数据域数组
　 int n:　　被插入的节点数目
*/
void Insert_Batch_Node_STree(BTNode *head,int array[],int n)
{
　int i;
　for(i=0;i<n;i++)
　{
　 if(!Insert_Node_STree(head,array[i]))
　　 printf("\n插入失败<键值为%d的节点已经存在>！\n",array[i]);
　}
}
//------------------------------

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!

分享到：更多

你可能对下面的文章感兴趣

上一篇: 获取GetLastError返回信息下一篇: 如何在C++中集成Lua脚本(LuaPlus篇)

关于二叉树创建及遍历算法的所有评论

随机推荐