附录:
//*********************************************************************** // 头文件 //*********************************************************************** #include <iostream>
#include <cstring>
#include <iomanip>
using namespace std;
#include <windows.h>
//*********************************************************************** // 全局数据 //*********************************************************************** #define MAX_CHARS 50
struct Node
{
char data;
Node* lchild;
Node* rchild;
};
typedef Node* PNode;
char *pre_order=new char[MAX_CHARS];
char *in_order=new char[MAX_CHARS];
PNode root = NULL;
int Offsets[32];
int LevelHeight = 50;
//************************************************************************ // 函数声明 //************************************************************************ inline int get_left_len(int rootpos,int in_begin,int in_end);
void create(PNode * pnode,int pre_begin,int pre_end,int in_begin,int in_end);
void preOrder(PNode pnode);
void inOrder(PNode pnode);
void postOrder(PNode pnode);
void printMenu();
void dealChoice();
void createBinaryTree();
void outPut();
void delSubTree();
void del(PNode &pnode,char ch);
void addNewNode();
void add(PNode &pnode,char ch);
LRESULT CALLBACK MsgProc(HWND hwnd,UINT uMsg,WPARAM wParam,LPARAM lParam); void GDIShowTree(HDC h, PNode root, int level, int center);
void ShowUseWindow();
//************************************************************************
// 主函数
//************************************************************************
int main()
{
printMenu();
dealChoice();
return 0;
}
inline int get_left_len(int rootpos,int in_begin,int in_end)
{
for(int i = in_begin; i <= in_end; i++)
{
} if(in_order[i] == pre_order[rootpos]) { } return i-in_begin;
return -1;
}
//************************************************************************
// （先序+中序）建立二叉树 //************************************************************************
void create(PNode * pnode,int pre_begin,int pre_end,int in_begin,int in_end)
{
*pnode = new Node;
PNode temp = *pnode;
temp->data = pre_order[pre_begin];
temp->lchild = NULL;
temp->rchild = NULL;
if(pre_begin == pre_end)
{
}
int left_len = get_left_len(pre_begin,in_begin,in_end);
if(left_len > 0)
{
}
if(left_len < (in_end - in_begin))
{
create(&temp->rchild,pre_begin+left_len+1,pre_end, create(&temp->lchild,pre_begin+1,pre_begin+left_len, in_begin,in_begin+left_len-1); return;
}
} in_begin+left_len+1,in_end);
//************************************************************************ // 二叉树的遍历 //************************************************************************ void preOrder(PNode pnode)
{
if(pnode == NULL)
{
}
cout<<pnode->data;
preOrder(pnode->lchild);
preOrder(pnode->rchild);
}
void inOrder(PNode pnode)
{
if(pnode == NULL)
{
}
inOrder(pnode->lchild);
cout<<pnode->data;
inOrder(pnode->rchild);
}
void postOrder(PNode pnode)
{ return; return;
if(pnode == NULL)
{
}
postOrder(pnode->lchild);
postOrder(pnode->rchild);
cout<<pnode->data;
}
//************************************************************************ // 显示菜单 //************************************************************************ void printMenu()
{
cout<<setw(50)<<setfill('*')<<left<<"*"<<endl;
cout<<setw(40)<<setfill(' ')<<" 0 退出系统"<<endl;
cout<<setw(40)<<setfill(' ')<<" 1 根据先序+中序序列创建二叉树"<<endl; cout<<setw(40)<<setfill(' ')<<" 2 显示二叉树遍历序列"<<endl;
cout<<setw(40)<<setfill(' ')<<" 3 显示二叉树"<<endl;
cout<<setw(40)<<setfill(' ')<<" 4 删除二叉树的子树"<<endl;
cout<<setw(40)<<setfill(' ')<<" 5为二叉树添加结点"<<endl;
cout<<setw(50)<<setfill('*')<<left<<"*"<<endl;
cout<<"请输入你的选择：";
}
//************************************************************************ // 处理选择 //************************************************************************ void dealChoice()
{
char choice;
cin>>choice; return;
switch(choice)
{
case '0':exit(0);break;
case '1':createBinaryTree();break;
case '2':outPut();break;
case '3':ShowUseWindow();break;
case '4':delSubTree();break;
case '5':addNewNode();break;
default:cout<<"选择有误！"<<endl;break;
}
system("cls");
printMenu();
dealChoice();
}
//************************************************************************ // 建立二叉树 //************************************************************************ void createBinaryTree()
{
cout<<"请输入先序序列："<<endl;
cin>>pre_order;
cout<<"请输入中序序列："<<endl;
cin>>in_order;
create(&root,0,strlen(pre_order)-1,0,strlen(in_order)-1);
cout<<"树已成功建立！"<<endl;
system("pause");
}
//************************************************************************ // 输出遍历序列 //************************************************************************
void outPut()
{
cout<<"先序序列: ";
preOrder(root);
cout<<endl;
cout<<"中序序列: ";
inOrder(root);
cout<<endl;
cout<<"后序序列: ";
postOrder(root);
cout<<endl;
system("pause");
}
//************************************************************************ // 删除子树 //************************************************************************ void delSubTree()
{
cout<<"请输入要删除的子树父结点:";
char ch=0;
cin>>ch;
del(root,ch);
}
void del(PNode &pnode,char ch)
{
if(pnode == NULL)
{
}
del(pnode->lchild,ch); return;
if (pnode->data==ch)
{
}
del(pnode->rchild,ch);
}
//************************************************************************ // 显示树
//************************************************************************ void GDIShowTree(HDC h, PNode root, int level, int center)
{
if (!root || !h) return ;
char number[32] = ""; sprintf(number, "%c", root->data );
int x0 = center;
int x1 = 0;
int y0 = level * LevelHeight;
int y1 = y0 + LevelHeight;
int off = Offsets[level + 1];
if (root->lchild ) {
x1 = x0 - off; GDIShowTree(h, root->lchild , level + 1, x1); MoveToEx(h, x0, y0, 0); LineTo(h, x1, y1); pnode=NULL; cout<<"删除成功！"<<endl; return;
}//end if
if (root->rchild) {
x1 = x0 + off; GDIShowTree(h, root->rchild, level + 1, x1); MoveToEx(h, x0, y0, 0);
LineTo(h, x1, y1);
}//end if
TextOut(h, x0, y0, number, strlen(number));
}//end GDIShowTree
LRESULT CALLBACK MsgProc(
{
HDC hDC = 0; int i = 0; RECT r = {0, 0, 0, 0}; int width = 0;
PAINTSTRUCT ps;
switch(uMsg){
case WM_PAINT:
hDC=BeginPaint(hwnd,&ps); GetClientRect(hwnd, &r); width = r.right ; for(i = 0; i < 32; i++) { width /= 2; Offsets[i] = width; HWND hwnd, // handle to window UINT uMsg, // message identifier WPARAM wParam, // first message parameter LPARAM lParam) // second message parameter }//next i GDIShowTree(hDC, root, 0, r.right / 2); EndPaint(hwnd,&ps); break;
case WM_CLOSE:
//exit(0); cout<<"操作回到控制台界面！"<<endl;printMenu(); dealChoice();exit(0); break; default:
return DefWindowProc(hwnd,uMsg,wParam,lParam);
}//end case
return 0;
}//end MsgProc
void ShowUseWindow()
{
WNDCLASS wc;
wc.cbClsExtra=0;
wc.cbWndExtra=0;
wc.hbrBackground=(HBRUSH)GetStockObject(WHITE_BRUSH);
wc.hCursor=LoadCursor(NULL,IDC_CROSS);
wc.hIcon=LoadIcon(NULL,IDI_WINLOGO);
wc.hInstance=0;
wc.lpfnWndProc=MsgProc;
wc.lpszClassName="Binary Tree Demo";
wc.lpszMenuName=NULL;
wc.style=CS_HREDRAW | CS_VREDRAW;
RegisterClass(&wc);
HWND hwnd;
hwnd=CreateWindow("Binary Tree Demo","二叉树直观显示界面",WS_OVERLAPPEDWINDOW,
ShowWindow(hwnd,SW_NORMAL);
UpdateWindow(hwnd);
MSG msg;
while(GetMessage(&msg,NULL,0,0))
{
TranslateMessage(&msg); 0,0,640,480,0,0,0,0);
}
} DispatchMessage(&msg);
//************************************************************************ // 增加新结点 //************************************************************************ void addNewNode()
{
char ch;
cout<<"请输入叶子结点："<<endl;
cin>>ch;
add(root,ch);
}
void add(PNode &pnode,char ch)
{
if(pnode == NULL)
{
}
add(pnode->lchild,ch);
if (pnode->data==ch)
{
if(pnode->lchild==NULL&&pnode->rchild==NULL) { char nd; cout<<"请输入添加元素："<<endl; cin>>nd; PNode temp = new Node; return;
temp->lchild=temp->rchild=NULL; temp->data=nd; cout<<"请输入 6：加在右边 7：加在左边"<<endl; int choice; cin>>choice; if (choice==6) { } if (choice==7) { } else { } cout<<"添加成功！"<<endl; cout<<"你的输入有错！"<<endl; pnode->lchild=temp; pnode->rchild=temp; return ;
}
add(pnode->rchild,ch);
}
} else { } return; cout<<"这不是叶子结点！"<<endl;
二叉树的应用一实验目的1使学生熟练掌握二叉树的逻辑结构和存储结构2熟练掌握二叉树的各种遍历算法3熟悉二叉树的应用二实验内容本次实验…
内蒙古科技大学本科生课程设计说明书题目数据结构课程设计二叉树的遍历和应用学生姓名学号专业班级指导教师20xx年5月29日内蒙古科技…
广西工学院计算机学院数据结构课程实验报告书实验六二叉树的基本操作及其应用学生姓名学号班级指导老师专业计算机学院软件学院提交日期20…
数据结构实验报告实验题目树和二叉树的应用实验内容重言式判别实验目的掌握树和二叉树的概念及工作原理运用其原理及概念完成上述实验题中的…
实验报告课程名称数据结构上机实验实验项目二叉树的应用实验仪器PC机系别专业班级学号学生姓名实验日期成绩指导教师实验三二叉树的应用1…
实验报告实验课程数据结构实验项目实验九二叉树遍历的应用实验地点指导教师班级学生姓名金轶洲学号09020xx03教师评分日期浙江传媒…
实验报告课程名称数据结构上机实验实验项目二叉树的应用实验仪器PC机系别专业班级学号学生姓名实验日期成绩指导教师实验三二叉树的应用1…
includequotstdiohquotincludequotstdlibhquotincludequotstringhquotincludequo…
内蒙古科技大学本科生课程设计说明书题目数据结构课程设计二叉树的遍历和应用学生姓名学号专业班级指导教师20xx年5月29日内蒙古科技…
二叉树的应用一实验目的1使学生熟练掌握二叉树的逻辑结构和存储结构2熟练掌握二叉树的各种遍历算法3熟悉二叉树的应用二实验内容本次实验…