二叉搜索树非递归方式删除节点

《二叉搜索树非递归方式删除节点》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1.#include "stdio.h"  2.#include "iostream.h"  3.typedef struct node  4.{  5. int data ;  6. node*lChild ;  7. node*rChild ;  8.}TreeNode  ;  9.void Insert(TreeNode**root,int data)  //向二叉查找树中插入元素  采用非递归思想  10.{        11. TreeNode * p=*root ;//获得根结点   12. TreeNode*q=new Tre

2、eNode ;//分配一个要插入的新节点   13. q->lChild=q->rChild=NULL ; //新分配节点的左节点=右节点等于NULL  14. q->data=data ;  //保存数据到节点      15. TreeNode *parent =p ; //用于保存父节点   16. while(p!=NULL)  //循环搜索节点    17. {  18.  parent=p ;  //首先parent指向root节点   19.  if(p->data>data)   //如果节点数据大于当前节点  20.   p

3、=p->lChild  ;//如果插入数据小于 节点数据那么指向左节点  我么最终是要找到一个NULL节点   21.  else  22.   p=p->rChild  ;  23. }  24. //如果因为parent总是指向NULL节点的父节点 ,所以parent指向的节点不会为空,如果为空那么说明该树是一颗空的树。  25. if(parent==NULL)   26.  *root=q ; //将分配的节点作为根节点   27. else if(parent->data>data)  28.  parent->lChild=q ;

4、   //rChild=q ;  //>root右插  31.}   32.  33.void InOrder(TreeNode*root)  34.{  35. if(root!=NULL)  36. {  37.  InOrder(root->lChild) ;  38.  printf("%d ",root->data) ;  39.  InOrder(root->rChild) ;  40. }  41.}  鱼跃家庭制氧机http://www.qingyangblog.

5、com1.bool   Find(TreeNode*root,int fData)   //非递归方法查询  2.{  3. if(root==NULL)  4.  return false ;  //搜索树为空返回false    5. while(root!=NULL)  6. {    7.  if(root->data==fData)  8.   return true ;    9.  if(root->data>fData)  10.   root=root->lChild ;  11.  else  12.   root=roo

6、t->rChild ;    13. }  14.      15. return false  ;  16.}  17.  18.  19.void BST_Delete(TreeNode**tp ,int dData)   //删除节点   20.{     21. TreeNode*root=*tp ;  22.    TreeNode* parent =NULL ;//父指针用来表示 是否是根节点    23. while(root!=NULL)  {  //循环查找  24.  if(dDatadata)  //如果删

7、除节点小于根节点数据  25.  {  26.   parent=root ;   //保存前一个节点的指针   27.   root=root->lChild   ;  //dData小于root数据 那么查找左子树   28.  29.  }   30.  else if(dData>root->data)  31.  {  32.   parent=root   ;  33.   root=root->rChild  ; //大于root数据那么查找右节点  34.   35.  36.  }  37.  else     //这里找到

8、了节点 如果即不大于 节点数据 也不小于节点数据 并且节点不是NULL那就说明了 节点查找到了 ,揭晓来我们就需要判断节点并删除了。  38.  {