写了一天终于用C++的方式把 A*算法撸出来了,写完后才发现如果有拐角的地方有4种方式需要不同的处理他.

  起点和到达点的位置关系和对角的方向关系的不同所以判断的条件也不同了.暂时没有找到更好的方法,如果有谁知道可以联系我.算法实现原理:http://www.cnblogs.com/technology/archive/2011/05/26/2058842.html代码如下:

</pre>

#include "stdafx.h"
#include "iostream"
#include <list>
#include <cstdlib>
#include <string>
#define STEP 10
#define ANGLE 14
#define ROW 10
#define COL 10
using namespace std;

struct Point
{

Point(int x,int y)
 {
 X=x;
 Y=y;
 F=0;
 G=0;
 H=0;
 parent=NULL;
 }
 Point()
 {

}
 void CalcF()
 {
 F=G+H;
 }

bool operator<(Point p2)
 {
 if (F<p2.F)
 return true;
 return false;
 }

Point *parent;
 int F;
 int G;
 int H;
 int X;
 int Y;
};

class CFindPath
{
public:
 CFindPath();
 CFindPath(int map[][COL]);
 ~CFindPath();
 Point *GetPath(Point start,Point end,bool isAagle);//获取路径链表;
 list<Point> GetSurroundPoint(Point &,bool);//获取周围可到达的点;
 bool IsCanReach(int x,int y);//判断是否是墙壁;
 void ChangePoint(Point start,Point point);//改变已在开启列表的点;
 void AddPoint(Point start,Point end,Point point);//添加不在开启列表的点;
 int CalculateG(Point,Point );//计算G
 int CalculateH(Point end,Point point);//计算H
 bool IsCanReach(Point start,int x,int y,bool isAngle);//判断是否可到达;
 Point *FindOpenListPoint(Point p);
 Point *FindColseListPoint(Point p);
 Point *FPoint(Point p);
private:
 list<Point> openList;//开启列表;
 list<Point> colseList;//关闭列表;
 list<Point> temList;
 int points[ROW][COL];
};

CFindPath::CFindPath()
{

}
CFindPath::CFindPath(int map[][COL])
{
 for(int i=0;i<ROW;i++)
 for(int j=0;j<COL;j++)
 points[i][j]=map[i][j];
}
CFindPath::~CFindPath()
{
 delete points;
}

&nbsp;

Point* CFindPath::GetPath(Point start,Point end,bool isAngle)//核心算法A*路径查找,isAngle表示是否可以越过拐角;
{
 openList.push_back(start);
 while (!openList.empty())
 {
 openList.sort();//根据F值由小到大排序;
 Point temp=openList.front();//取出F值最小的;
 colseList.push_back(temp);//加入到关闭列表;
 openList.pop_front();//开启列表中删除F值最小的;
 list<Point> surroundPoints=GetSurroundPoint(temp,isAngle);//取出周围可到达的点;
 while (!surroundPoints.empty())//对每个可到达的周围的点进行判断;
 {
 Point point=surroundPoints.front();
 if(FindOpenListPoint(point))//若开启列表中存在这个点;
 ChangePoint(temp,point);//判断是否是最优路径如果是改变父结点若不是则什么也不做;
 else
 AddPoint(temp,end,point);//若不在开启列表则加入;
 surroundPoints.pop_front();
 }
 if(FindOpenListPoint(end))
 return FindOpenListPoint(end);
 }
 return FindOpenListPoint(end);
}

&nbsp;

void CFindPath::ChangePoint(Point start,Point point)//改变点的父结点重新计算F值;
 {

 int G=CalculateG(start,point);
 if(G<point.G)
 { point.parent=new Point(start);
 point.G=G;
 point.CalcF();
 }
 }

void CFindPath::AddPoint(Point start,Point end,Point point)//添加点到开启列表;
 {
 point.parent=new Point(start);
 point.G=CalculateG(start,point);
 point.H=CalculateH(end,point);
 point.CalcF();
 openList.push_back(point);
 }

int CFindPath::CalculateG(Point start,Point point)//计算G值
 {

 int parentG=0;
 int G=(abs(point.X-start.X)+abs(point.Y-start.Y))!=2?STEP:ANGLE;
 if(point.parent)
 parentG=point.parent->G!=0?point.parent->G:0;
 return G+parentG;

}

int CFindPath::CalculateH(Point end,Point point)//计算H值;
 {
 int step=abs(point.X-end.X)+abs(point.Y-end.Y);
 return step*STEP;

}

Point* CFindPath::FindOpenListPoint(Point p)//查找点是否在开启列表中;
 {
 list<Point>::iterator i;
 for(i=openList.begin();i!=openList.end();i++)
 {
 if(p.X==i->X&&p.Y==i->Y)
 {
 return &*i;
 }
 }
 return NULL;
 }

list<Point> CFindPath::GetSurroundPoint(Point &p,bool isAngle)//获取周围可到达结点;
{ list<Point> temPoints;

for(int i=p.X-1;i<=(p.X+1>=ROW?p.X:p.X+1);i++)
 for(int j=p.Y-1;j<=(p.Y+1>=COL?p.Y:p.Y+1);j++)
 {
 if(IsCanReach(p,i,j,isAngle))
 {

 Point mPoint(i,j);
 temPoints.push_back(mPoint);
 }
 }
 return temPoints;
}
 Point *CFindPath::FindColseListPoint(Point p)
 {

list<Point>::iterator i;
 for(i=colseList.begin();i!=colseList.end();i++)
 {
 if(p.X==i->X&&p.Y==i->Y)
 {
 return &*i;
 }
 }
 return NULL;
 }

bool CFindPath::IsCanReach(Point start,int x,int y,bool isAngle)//判断点是否可以到达
{
 Point point;
 point.X=x;
 point.Y=y;
 if(!IsCanReach(x,y)||FindColseListPoint(point))
 {
 return false;
 }
 else
 {
 if(abs(x-start.X)+abs(y-start.Y)==1)
 return true;
 else
 {
 if(isAngle)//如果可以拐角直接返回
 return isAngle;

//以下为4种不同拐角的情况判断
 if(x<start.X&&y<start.Y) //(到点) 0 | 1 //到点和起点的位置有4种情况所以有4种不同的拐角
 { // -----|-----
 if(points[start.X][y]==0&&points[x][start.Y]==0) // 1 | 0(起点)
 return true; //
 }
 else if(x<start.X&&y>start.Y)
 {
 if(points[x][start.Y]==0&&points[start.X][y]==0)
 return true;
 }
 else if(x>start.X&&y<start.Y)
 {
 if(points[start.X][y]==0&&points[x][start.Y]==0)
 return true;
 }
 else if(x>start.X&&y>start.Y)
 {
 if(points[x][start.Y]==0&&points[start.X][y]==0)
 return true;

}
 return false;

 }
 }
}

bool CFindPath::IsCanReach(int x,int y)//判断点是否可以通过
{
 return points[x][y]==0;
}
int main(int argc, char* argv[])
{
 int map[10][10]={//地图//0 1 2 3 4 5 6 7 8 9
 /*0*/{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
 /*1*/{ 1, 0, 0, 1, 1, 0, 1, 0, 0, 0},
 /*2*/{ 1, 0, 1, 1, 1, 0, 0, 0, 0, 0},
 /*3*/{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 1},
 /*4*/{ 1, 1, 1, 1, 0, 0, 0, 0, 1, 1},
 /*5*/{ 1, 1, 0, 1, 0, 0, 0, 0, 0, 0},
 /*6*/{ 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
 /*7*/{ 1, 1, 0, 0, 1, 1, 0, 0, 0, 1},
 /*8*/{ 1, 1, 0, 0, 1, 0, 0, 1, 0, 1},
 /*9*/{ 1, 1, 1, 0, 1, 1, 1, 1, 0, 1}
 };
 CFindPath path(map);//初始化地图;
 Point start(1,1);//起点;
 Point end(9,8);//终点
 Point *point=new Point();
 point=path.GetPath(start,end,false);
 if(point==NULL)
 {
 cout<<"无法到达终点!"<<endl;
 }
 else
 {
 while (point!=NULL)
 {
 cout<<point->X<<","<<point->Y<<endl;
 point=point->parent;
 }
 }
 delete point;
 point=NULL;
 getchar();
 return 0;
}

&nbsp;
<pre>

以上代码在VS2012上测试通过.

#include "stdafx.h"

#include "iostream"
using namespace std;

//非递归查找
int HalfFind(int arr[],int size,int key)
{
 int low=0;
 int high=size-1;
 int mid=0;
 int result=-1;
 while (low<=high)
 { mid=(low+high)/2;
 if(key==arr[mid])
 {
 result=arr[mid];
 break;
 }
 else if(key>mid)
 low=mid+1;
 else
 high=mid-1;
 }
 return result;
}

//递归查找
int HalfFind(int arr[],int low,int high,int key)
{

if(low<=high)
 {

int mid=(low+high)/2;
 if(arr[mid]==key)
 {
 return arr[mid];

}
 else if(key>arr[mid])
 HalfFind(arr,mid+1,high,key);
 else
 HalfFind(arr,low,mid-1,key);
 }
 else
 return -1;
}
int main(int argc, _TCHAR* argv[])
{
 int test[10]={1,2,3,4,5,6,7,8,9,10};
 cout<<HalfFind(test,10,1)<<endl;
 cout<<HalfFind(test,0,9,1)<<endl;
 getchar();
 return 0;
}

本代码来自互联网,如有侵权,立删.

#include "stdafx.h"
#include <iostream>
#define BLACK 0
#define RED 1
#define NULL 0
typedef int BOOL;

typedef struct RBTreeNode
{
 int key;
 int color;
 struct RBTreeNode *parent, *left, *right;
 RBTreeNode(){}
 RBTreeNode(int k):key(k){ // 创建新结点默认颜色为红色
 color = RED;
 parent = NULL;
 left = NULL;
 right = NULL;}
}RBTree, RBTreeNode;

class CRBTree
{
public:
 CRBTree();
 virtual ~CRBTree();

 void RB_InitLeafNode();
 BOOL RB_Insert(int keyVal);
 BOOL RB_Delete(int keyVal);
 RBTreeNode *RB_Find(int keyVal);
 void RB_Print();
 int RB_GetSize()const { return m_Size; }
private:
 void RB_Insert_FixedUp(RBTreeNode *&pNode);
 void RB_Del_FixedUp(RBTreeNode *&pNode);
 void RB_Left_Rotate(RBTreeNode *&pNode);
 void RB_Right_Rotate(RBTreeNode *&pNode);
 void RB_Print(RBTreeNode *&pNode);
 void RB_SwapTwoNodes(RBTreeNode *&pNode1, RBTreeNode *&pNode2);
 void RB_EmptyTree(RBTreeNode *&pNode);
private:
 RBTree *m_root; //根结点
 RBTreeNode *m_NIL; // 空结点
 int m_Size;
};

using namespace std;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
// 构造函数
CRBTree::CRBTree()
{
 m_root = m_NIL = NULL;
 m_Size = 0;
}

// 析构函数
CRBTree::~CRBTree()
{
 RB_EmptyTree(m_root);
 delete m_NIL;
 m_root = m_NIL = NULL;
 cout << "Empty the tree!\n";
}

// 初始化叶子结点
void CRBTree::RB_InitLeafNode()
{
 m_root = new RBTree(-1);
 m_NIL = new RBTreeNode(-1);
 m_NIL->color = BLACK; // 叶子结点颜色都为黑色
 m_NIL->parent = NULL;
 m_NIL->left = m_NIL->right = NULL;
 m_root = m_NIL;
 m_root->parent = m_NIL;
}

// 插入树结点
BOOL CRBTree::RB_Insert( int keyVal )
{
 RBTreeNode *pNewNode = new RBTreeNode(keyVal);
 pNewNode->left = m_NIL;
 pNewNode->right = m_NIL;
 RBTreeNode *pNode = m_root;
 RBTreeNode *pPreNode = m_NIL;
 while(pNode != m_NIL) // 树不为空
 {
 pPreNode = pNode;
 if (keyVal < pNode->key)
 {
 pNode = pNode->left;
 }
 else if (keyVal > pNode->key)
 {
 pNode = pNode->right;
 }
 else{
 delete pNewNode;
 return 0;
 }
 }
 pNewNode->parent = pPreNode;
 if (pPreNode == m_NIL) // 树为空
 {
 pNewNode->color = BLACK;
 m_root = pNewNode;
 }
 else
 {
 if (keyVal < pPreNode->key)
 {
 pPreNode->left = pNewNode;
 }
 else
 pPreNode->right = pNewNode;
 }
 m_Size++;
 cout << "Insert "<< m_Size << " node: " << keyVal << " succeeded!\n";
 RB_Insert_FixedUp(pNewNode);
 return 1;
}

// 删除树结点
BOOL CRBTree::RB_Delete( int keyVal )
{
 RBTreeNode *pDelNode, *pPreNode = m_NIL;
 if (m_root == m_NIL)
 {
 return 0;
 }
// pDelNode = m_root;
// while(pDelNode != m_NIL)
// {
// if (keyVal < pDelNode->key)
// {
// pPreNode = pDelNode;
// pDelNode = pDelNode->left;
// }
// else if (keyVal > pDelNode->key)
// {
// pPreNode = pDelNode;
// pDelNode = pDelNode->right;
// }
// else
// break;
// }
 pDelNode = RB_Find(keyVal);
 if (pDelNode == NULL)
 {
 return 0; // 没有此结点
 }
 pPreNode = pDelNode->parent;
 //从该结点的左子树找出最大的结点或从右子树找出最小的结点， 两者的值进行替换
 RBTreeNode *pTemp;
 RBTreeNode *pDelChild;
 if (pDelNode->left != m_NIL && pDelNode->right != m_NIL)
 { // 有两个子结点，查找左子树
 pTemp = pDelNode->left;
 while(pTemp->right != m_NIL)
 {
 pTemp = pTemp->right;
 }

 RB_SwapTwoNodes(pTemp, pDelNode);

 pDelChild = pTemp->left;
 pDelChild->parent = pTemp->parent;
 if (pTemp->parent->left == pTemp)
 {
 pTemp->parent->left = pDelChild;
 }
 else
 pTemp->parent->right = pDelChild;
 }
 else if (pDelNode->left == m_NIL && pDelNode->right == m_NIL)
 { // 要删除的结点是叶子结点
 if (pPreNode == m_NIL)
 {
 delete m_root;
 m_root = m_NIL;
 m_Size--;
 return 1;
 }
 else
 {
 if (pDelNode == pDelNode->parent->left)
 {
 pPreNode->left = m_NIL;
 }
 else
 pPreNode->right = m_NIL;
 pDelChild = m_NIL;
 pDelChild->parent = pDelNode->parent;
 pTemp = pDelNode;
 }
 }
 else // 有一个子结点
 {
 if (pDelNode->left != m_NIL)
 {
 pDelChild = pDelNode->left;
 }
 else
 {
 pDelChild = pDelNode->right;
 }
 if (pDelChild == pPreNode->left)
 {
 pDelChild->parent = pPreNode;
 pPreNode->left = pDelChild;
 }
 else
 {
 pDelChild->parent = pPreNode;
 pPreNode->right = pDelChild;
 }
 pTemp = pDelNode;
 }
 if (pTemp->color == BLACK)
 {
 RB_Del_FixedUp(pDelChild);
 }
 cout << "Deleted node: " << pTemp->key << endl;
 delete pTemp;
 m_Size--;
 return 1;
}

// 查找指定结点，成功 放回该结点，否则返回NULL
RBTreeNode * CRBTree::RB_Find( int keyVal )
{
 RBTreeNode *pNode;
 if (m_root == m_NIL)
 {
 return NULL;
 }
 pNode = m_root;
 while(pNode != m_NIL)
 {
 if (keyVal < pNode->key)
 {
 pNode = pNode->left;
 }
 else if (keyVal > pNode->key)
 {
 pNode = pNode->right;
 }
 else{
 cout << "Find node: " << keyVal << "succeeded!\n";
 return pNode;
 }
 }
 return NULL;
}

// 插入结点后形成的新结构不满足红黑树性质和对其进行处理
void CRBTree::RB_Insert_FixedUp( RBTreeNode *&pNode )
{
 while (pNode->parent->color == RED)
 {
 RBTreeNode *pNodeParent = pNode->parent;
 RBTreeNode *pNodePaBro;
 if (pNodeParent->parent->left == pNodeParent)
 pNodePaBro = pNodeParent->parent->right;
 else
 pNodePaBro = pNodeParent->parent->left;
 if (pNodePaBro->color == RED)
 { // 父结点和叔结点都是红色 ==>> 父--黑 叔--黑 祖父--红
 pNodeParent->color = BLACK;
 pNodePaBro->color = BLACK;
 pNodeParent->parent->color = RED;
 pNode = pNode->parent->parent;
 if (pNode == m_NIL)
 {
 m_root->color = BLACK;
 return ;
 }
 }
 /// 红父 黑叔结点 或者没有叔结点
 else if(pNodeParent->parent->left == pNodeParent && pNodeParent->left == pNode)
 {
 pNodeParent->color = BLACK;
 pNodeParent->parent->color = RED;
 cout<<"右旋转"<<endl;
 RB_Right_Rotate(pNode->parent->parent);
 break;
 }
 else if (pNodeParent->parent->left == pNodeParent && pNodeParent->right == pNode)
 {
 pNode = pNode->parent;
 RB_Left_Rotate(pNode);
 }
 else if (pNodeParent->parent->right == pNodeParent && pNodeParent->left == pNode)
 {
 pNode = pNode->parent;
 RB_Right_Rotate(pNode);
 }
 else
 {
 pNodeParent->color = BLACK;
 pNodeParent->parent->color = RED;
 RB_Left_Rotate(pNode->parent->parent);
 break;
 }
 }// while
 m_root->color = BLACK;
}

// 删除结点后形成的新结构不满足红黑树性质和对其进行处理
void CRBTree::RB_Del_FixedUp( RBTreeNode *&pNode )
{
 int nLRFlag;
 RBTreeNode *pBroNode;
 while(pNode != m_root && pNode->color == BLACK)
 {
 if (pNode->parent->left == pNode)
 {
 nLRFlag = 0;
 pBroNode = pNode->parent->right;
 }
 else
 {
 nLRFlag = 1;
 pBroNode = pNode->parent->left;
 }

 //1 父-red 无兄 子-red ==>> 子-black
 //2 父-black 兄-red ==>> 父-red 兄-black 旋转父结点
 if (pBroNode->color == RED)
 {
 pNode->parent->color = BLACK;
 pBroNode->color = BLACK;
 if (nLRFlag == 0)
 {
 RB_Left_Rotate(pNode->parent);
 }
 else
 RB_Right_Rotate(pNode->parent);
 }
 //3 兄-black 两黑侄 ==>> 兄=红 子=黑 红父=黑 往上遍历(黑父)
 else if (pBroNode->left->color == BLACK && pBroNode->right->color == BLACK)
 {
 pNode->color = BLACK;
 pBroNode->color = RED;
 pNode->parent->color = BLACK;
 pNode = pNode->parent; // 往上遍历
 }
 //4 兄-black 左黑侄右红侄 ==>> 兄=父色 父=黑 侄=黑 (子=黑) 左旋转父节点
 else if (pBroNode->left->color == BLACK && pBroNode->right->color == RED)
 {
 if (nLRFlag == 0)
 {
 pBroNode->color = pNode->parent->color;
 pNode->parent->color = BLACK;
 pNode->color = BLACK;
 pBroNode->right->color = BLACK;
 RB_Left_Rotate(pNode->parent);
 break;
 }
 else
 {
 RBTreeNode *pPa = pNode->parent;
 pBroNode->left->color = pNode->parent->color;
 pNode->parent->color = BLACK;
 RB_Left_Rotate(pBroNode);
 RB_Right_Rotate(pPa);
 break;
 }
 }
 //5 兄-black 左红侄右黑侄 ==>> 侄=父色 父=黑 右旋转兄 左旋转父
 else if (pBroNode->left->color == RED && pBroNode->right->color == BLACK)
 {

 if (nLRFlag == 0)
 {
 RBTreeNode *pPa = pNode->parent;
 pBroNode->left->color = pNode->parent->color;
 pNode->parent->color = BLACK;
 RB_Right_Rotate(pBroNode);
 RB_Left_Rotate(pPa);
 break;
 }
 else
 {
 pBroNode->color = pNode->parent->color;
 pNode->parent->color = BLACK;
 pNode->color = BLACK;
 pBroNode->right->color = BLACK;
 RB_Right_Rotate(pNode->parent);
 break;
 }
 }
 else //两红侄的情况 转换成一黑一红的情况
 {
 if (nLRFlag == 0)
 {
 pBroNode->left->color = BLACK;
 }
 else
 {
 pBroNode->right->color = BLACK;
 }
 }
 }
 pNode->color = BLACK; //子 ==> black
 return;
}

// 左旋处理
void CRBTree::RB_Left_Rotate( RBTreeNode *&pNode )
{
 RBTreeNode *pNodeA = pNode->parent;
 RBTreeNode *pNodeB = pNode->right;
 pNode->right = pNodeB->left;
 pNodeB->left->parent = pNode;
 pNodeB->left = pNode;
 pNode->parent = pNodeB;

 if (pNode == pNodeA->left)
 { // 父子不同边
 pNodeA->left = pNodeB;
 pNodeB->parent = pNodeA;
 }
 else if (pNode ==pNodeA->right)
 {
 pNodeA->right = pNodeB;
 pNodeB->parent = pNodeA;
 }
 else // m_root == m_NIL
 {
 if (pNodeA == m_NIL)
 { // pNode 原本为根结点
 pNodeB->parent = m_NIL;
 m_root = pNodeB;
 }
 }
 cout << "RB_Left_Rotate()\n";
}

// 右旋处理函数
void CRBTree::RB_Right_Rotate( RBTreeNode *&pNode )
{
 RBTreeNode *pNodeA = pNode->parent;
 RBTreeNode *pNodeB = pNode->left;
 pNode->left = pNodeB->right;
 pNodeB->right->parent = pNode;
 pNodeB->right = pNode;
 pNode->parent = pNodeB;

 if (pNode == pNodeA->right)
 { // 父子不同边
 pNodeA->right = pNodeB;
 pNodeB->parent = pNodeA;
 cout<<"父子不同边"<<endl;
 }
 else if (pNode==pNodeA->left)
 {
 pNodeA->left = pNodeB;
 pNodeB->parent = pNodeA;
 }
 else // m_root == m_NIL
 {
 if (pNodeA == m_NIL)
 { // pNodeA 原本为父结点
 pNodeB->parent = m_NIL;
 m_root = pNodeB;
 }
 }
 cout << "RB_Right_Rotate()\n";
}

void CRBTree::RB_Print()
{
 if (m_root == m_NIL)
 {
 cout << "树为空！\n";
 return ;
 }
 RB_Print(m_root);
 cout << endl;
}

void CRBTree::RB_Print( RBTreeNode *&pNode )
{
 if (pNode != m_NIL)
 {
 cout << pNode->key << "(" << pNode->color << ") ";
 RB_Print(pNode->left);
 RB_Print(pNode->right);
 }
}

void CRBTree::RB_SwapTwoNodes( RBTreeNode *&pNode1, RBTreeNode *&pNode2 )
{
 int t = pNode1->key;
 pNode1->key = pNode2->key;
 pNode2->key = t;
}

void CRBTree::RB_EmptyTree( RBTreeNode *&pNode )
{
 if (pNode != m_NIL)
 {
 RB_EmptyTree(pNode->left);
 RB_EmptyTree(pNode->right);
 delete pNode;
 }
}
void Fun_Test()
{
 CRBTree tree;
 tree.RB_InitLeafNode();
 tree.RB_Insert(10);
 tree.RB_Insert(14);
 tree.RB_Insert(4);
 tree.RB_Insert(15);
 tree.RB_Insert(16);
 tree.RB_Insert(13);
 tree.RB_Insert(18);
 tree.RB_Insert(17);
 tree.RB_Print();
 // tree.RB_Delete(14);
 // tree.RB_Delete(10);
 // Sleep(1000);
 // tree.RB_Print();
}

int main()
{
 cout << "红黑树RBTree测试程序 !\n";
 Fun_Test();
 getchar();
 return 0;
}

最近想复习一下数据结构和算法,所以就写了一个二叉树的创建和遍历

// test2.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;

struct tree//树结构体
{
 int data;
 tree *left,*right;
};
class Ctree
{

public:
 static int n;
 static int m;
 tree *root;
 Ctree()
 {
 root=NULL;

}
 void CreateTreeNode(int a);//创建树节点;
 int Sum(tree*);
 void PreOrder(tree*);
 void MedialOrder(tree*);
 void BackOrder(tree*);
};
int Ctree::m=0;
int Ctree::n=0;

void Ctree::CreateTreeNode(int data)
{
 tree *newNode=new tree;

 newNode->data=data;
 newNode->right=newNode->left=NULL;
 if(root==NULL)
 root=newNode;
 else
 {
 tree *tail;
 tree *cur=root;

 while(cur!=NULL)
 { tail=cur;

 if(data<cur->data)
 cur=cur->left;
 else
 cur=cur->right;
 }
 if(data<tail->data)
 tail->left=newNode;
 else
 tail->right=newNode;
 }

}

int Ctree::Sum(tree *p)//计算结点数
{
 if(p==NULL)
 return 0;
 else
 return Sum(p->left)+Sum(p->right)+1;
}

void Ctree::PreOrder(tree *p)//先序遍历;
{
 if(p!=NULL)
 {
 cout<<p->data<<endl;
 PreOrder(p->left);
 PreOrder(p->right);
 }
}
void Ctree::MedialOrder(tree*p)//中序遍历
{

if(p!=NULL)
 {
 MedialOrder(p->left);
 cout<<p->data<<endl;
 MedialOrder(p->right);
 }
}

void Ctree::BackOrder(tree *p)//后序遍历
{
 if(p!=NULL)
 {
 BackOrder(p->left);
 BackOrder(p->right);
 cout<<p->data<<endl;
 }
}
int main(int argc, char* argv[])
{
 Ctree *T=new Ctree();

T->CreateTreeNode(10);//根结点
 T->CreateTreeNode(7);
 T->CreateTreeNode(8);
 T->CreateTreeNode(11);
 T->CreateTreeNode(9);
 T->CreateTreeNode(6);

cout<<"结点数:"<<T->Sum(T->root)<<endl;
 cout<<"先序遍历:"<<endl;
 T->PreOrder(T->root);
 cout<<"中序遍历:"<<endl;
 T->MedialOrder(T->root);
 cout<<"后序遍历:"<<endl;
 T->BackOrder(T->root);
 getchar();
 return 0;
}

&nbsp;

输出结果如下: