二叉排序树的实现_折半查找方法的实现_c二叉树非递归中序遍历(2)

voidInsert(BSNode*&root,intitem);

//删除:在以root为根的树上插入值为item的结点

voidDelete(BSNode*&root,intitem);

//求最大值:返回以root为根的树中结点的最小值，结点返回给minNode

intMin(BSNode*root,BSNode*&minNode);

//求最小值:返回以root为根的树中结点的最大值，结点返回给maxNode

intMax(BSNode*root,BSNode*&maxNode);

//求双亲结点:返回值为item的结点的双亲结点

BSNode*getParent(BSNode*root,intitem);

//获取中序遍历的前驱结点

BSNode*getInOrderPre(BSNode*root,intitem);

//获取中序遍历的后继结点

BSNode*getInOrderPost(BSNode*root,intitem);

//用栈实现非递归的先序遍历

voidPreOrder(BSNode*root);

//用栈实现非递归的中序遍历

voidInOrder(BSNode*root);

//用栈实现非递归的后序遍历

voidPostOrder(BSNode*root);

};

BSTree::BSTree()

{

root=NULL;

}

//建树:创建一棵结点个数为n的二叉排序树

voidBSTree::CreateTree()

{

intn=0;

Create(root,a,n);

}

//建树:创建一棵结点个数为n的二叉排序树

voidBSTree::Create(BSNode*&root,int*a,intn)//待续，要利用插入算法

{

cout<<"请输入树的结点个数:";

cin>>n;

cout<<endl<<"请依次输入结点的数值："<<endl;

BSNode*newNode=NULL;

for(inti=0;i<n;i++)

{

cin>>a[i];

InsertNode(a[i]);

}

}

//查找:在以root为根的树上查找值为item的结点，返回给Node，找到返回true,否则为false

boolBSTree::FindNode(intitem)

{

BSNode*Node=NULL;

returnFind(root,Node,item);

}

//查找:在以root为根的树上查找值为item的结点，返回给Node，找到返回true,否则为false

boolBSTree::Find(BSNode*&root,BSNode*&findNode,intitem)

{

if(root==NULL)//树空

{

findNode=NULL;//没有找到结点

returnfalse;

}

else

{

if(root->data==item)

{

findNode=root;//找到结点

returntrue;

}

elseif(root->data>item)//数值小于根结点的数值，则在左子树中递归查找

{

returnFind(root->m_lchild,findNode,item);

}

else//数值大于根结点的数值，则在右子树中递归查找

{

returnFind(root->m_rchild,findNode,item);

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25453-2.html