bstview.h

数据结构中的二叉搜索树

// BSTView.h : CBSTView 类的接口
//


#pragma once
#include "insertdlg.h"
#include "searchdlg.h"
#include "malloc.h"
#define NOWSIZE 30

typedef struct Node
{
	CPoint point;
	int px;  
	int Islchild;
	                //只是辅助可视化编程；
	int data;       //结点的数值；
	int h;          //树的结点中加入h，表示结点所在的层次；
	Node *lch,*rch;
}Node;

class stack         //栈类
{
private:
	Node *base;
	//Node *top;
	int size;
	int fulsize;

public:
	stack()        //栈的初始化；
	{
		base=new Node[NOWSIZE];  //开辟空间；
		//top=base;
		size=0;                  //记录栈的数据个数；
		fulsize=NOWSIZE;
	}

	~stack()
	{
	}

	Node* PopStack()
	{
		Node *a;
		if(!size) 
			AfxMessageBox("栈空");
		else 
		{
			//top--;
			//a=top;
			size--;
			a=base+size;
			return a;
		}
	}

	void PushStack(Node* a)
	{ 
		if (size>=NOWSIZE-1)
		{
			base=(Node *) realloc(base,(fulsize+5) *sizeof(Node));
			fulsize+=5;		
		}
		else 
		{
			base[size]=*a;
			size++;
			//top=a;
			//top++;
		}
	}  

	int IsEmpty()
	{
		if(!size)
			return 1;
		else 
			return 0;
	}
};                  //栈类结束；

class CBSTView : public CView
{
protected: // 仅从序列化创建
	CBSTView();
	DECLARE_DYNCREATE(CBSTView)

// 属性
public:
	CBSTDoc* GetDocument() const;

// 操作
public:

// 重写
	public:
	virtual void OnDraw(CDC* pDC);  // 重写以绘制该视图
virtual BOOL PreCreateWindow(CREATESTRUCT& cs);
protected:

// 实现
public:
	virtual ~CBSTView();
#ifdef _DEBUG
	virtual void AssertValid() const;
	virtual void Dump(CDumpContext& dc) const;
#endif

protected:

// 生成的消息映射函数
protected:
	DECLARE_MESSAGE_MAP()
public:
	afx_msg void OnInsert();
	afx_msg void OnSearch();
	InsertDlg Dlg1;
	SearchDlg Dlg2;
	int first;
	long* m_data;
	int m_R;
	int m_Len;
	int m_x;
	int m_y;
	afx_msg void OnSize(UINT nType, int cx, int cy);
 /************************************************************/
//二叉树的主要部分的定义；
	int h;     //树的深度；
	int leaf;  //树的叶子结点个数；
	Node *T;
	Node *last;
	int Search(Node* & q, long data, int IsHelp=0);
	void PreTraverse(Node *p,int IsHelp=0,int i=0); 
	void InTraverse(Node *p,int IsHelp=0);    //实现中序遍历，在原来功能上加上协助求叶子结点功能,黓认功能为原始功能；
	void AfterTraverse(Node *p);  //实现后序遍历,，在原来功能上加上协助交换子树的功能,黓认功能为原始功能；；
	void UnInTraverse();            //实现非递归中序遍历；
	void Getleaf();
/************************************************************/
	void Draw(Node *p,int IsHelp=0);
	afx_msg void OnPre();
	afx_msg void OnLevel();
	afx_msg void OnAfter();
	afx_msg void OnMid();
	afx_msg void OnFei();
	afx_msg void OnExchange();
};

#ifndef _DEBUG  // BSTView.cpp 的调试版本
inline CBSTDoc* CBSTView::GetDocument() const
   { return reinterpret_cast<CBSTDoc*>(m_pDocument); }
#endif