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

二叉排序树的实现

nullinsertdeletetreeclass算法

二叉排序树（Binary Sort Tree）又称二叉查找树。 它是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

二叉排序树是一种动态树表。二叉排序树的实现

vs2008运行正确，如有误，请各位大牛指正！

实现代码如下：

[cpp] view plaincopyprint?

//MyBiSortTree.cpp:定义控制台应用程序的入口点。二叉排序树的实现

//二叉查找树的各种操作

//实现功能：建树，查找，插入，删除，求最大值最小值，求双亲结点

//，获取中序遍历的前驱结点后继结点，用栈实现非递归的先序中序后序遍历算法，

#include"stdafx.h"

#include<iostream>

usingnamespacestd;

inta[100];//存放结点数据的数组

constintSTACK_MAXSIZE=30;

//二叉排序树的结点类型

classBSNode

{

public:

BSNode(){};

BSNode(intitem):data(item),m_lchild(NULL),m_rchild(NULL){}

intdata;//数据域

BSNode*m_lchild;//左孩子

BSNode*m_rchild;//右孩子

};

//二叉排序树类型

classBSTree

{

public://定义接口

BSTree();

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

voidCreateTree();

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

boolFindNode(intitem);

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

voidInsertNode(intitem);

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

voidDeleteNode(intitem);

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

intMinNode();

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

intMaxNode();

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

BSNode*GetParent(intitem);

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

BSNode*GetInOrderPre(intitem);

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

BSNode*GetInOrderPost(intitem);

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

voidPreOrderVisit();

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

voidInOrderVisit();

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

voidPostOrderVisit();

private:

BSNode*root;//树的根结点

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

voidCreate(BSNode*&root,int*a,intn);

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

boolFind(BSNode*&root,BSNode*&Node,intitem);

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

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