二叉树的建立，遍历及显示-数据结构.doc

二叉树的建立，遍历及显示 需求和规格说明 需求： 1.按先序顺序建立一棵二叉树； 2. 用递归方式遍历一棵二叉树（先序，中序，后序），输出遍历序列； 3.按非递归方式，实现对这棵二叉树的遍历。 规格说明： 按先序顺序依次输入二叉树节点的值，用‘#’表示空树； 简化程序书写，使程序清晰； 实现二叉树的可视化显示。 2.设计 2.1 设计思想 先画好需要创建的二叉树，以字符串形式表示出来； 设计MFC的对话框，有一个输入的示例编辑框，几个输出的示例编辑框，添加树控件及其相应的按钮，点击以实现内容的传入与显示； 3.自定义类：tree；为其在C_treeDlg类中声明对象，实现对象对类中成员函数的调用，对二叉树的建立，递归遍历的实现全部封装在tree类中； 4,为实现非递归遍历，用到栈结构，则这里有自定义了链栈结构，套用了原来编写的对栈的相应的处理函数； 5.注意把相应的头文件添加到C_treeDlg.cpp中 2.2设计表示 树的结构 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; class tree : public CWnd { DECLARE_DYNAMIC(tree) public: tree(); virtual ~tree(); int CreateBiTree(BiTree T,CString str,int i);//先序建立二叉树 bool PrintElement(char e,CString Str); //字符串连接函数 int PreOrderTraverse(BiTree T,CString Str); //递归先序遍历 int BehOrderTraverse(BiTree T,CString Str); //递归后序遍历 int MidOrderTraverse(BiTree T,CString Str); //递归中序遍历 int InOrderTraverse(BiTree T,CString Str);//中序非递归遍历二叉树 int Compare(CString); protected: DECLARE_MESSAGE_MAP() }; 栈的结构 typedef struct { BiTree *base; BiTree *top; int stacksize; }Stack; void InitStack(Stack S)//建立一个栈 int GetTop(Stack S,BiTree e)//得到栈顶元素，若栈不为空，则返回1；否则返回0； int Push(Stack S,BiTree e)//压栈} int Pop(Stack S,BiTree e)//出栈 int StackEmpty(Stack S) int DestoyStack(Stack S) 2.3实现注释 1. int CreateBiTree(BiTree T,CString str,int i);//先序建立二叉树 将字符串传递进来，用i标记字符串的偏移量，用来依次读取字符串中的字符，以先序顺序建立一棵二叉树，首先判断第一个字符是否为‘#’，为空着返回树为空，若不为空，则将当前字符存到刚申请的树节点的数据域中，成功建树则返回1； 2.int compare（CString str） //用于判断字符串是否合法；根据完全二叉树的性质，如果合法则‘#’的个数比非‘#’的个数多1.正确则返回1，否则返回0； printElement（char e，CStringstr） //实现字符型数据向字符串型的转换，并连接到字符串strr中； int PreOrderTraverse(BiTree T,CString Str); //递归先序方式建树，调用printElement函数，将T-data中字符连接到字符串中，就是先序遍历对根节点的访问方式，之后依次访问根子树的左孩子和右孩子； int InOrderTraverse(BiTree T,CString Str); //中序非递归遍历二叉树，先建栈S，根指针入栈，判断栈是否为空，不为空则判断栈顶元素是否为空不为空则继续把该指针的左子树入栈，否则为空指针结束内层循环，判断栈当前是否为空，不为空则继续弹出栈顶元素，调用printElement函数，将p-data连接到当前字符串中，再把当前指针指向节点的右子树入栈；非递归遍历结束后，销毁栈。 对树控件的操作函数： TVINSERTSTRUCT tvI