毕业论文二叉树(求高手帮忙,一个数据作业论文：建立一棵二叉树,使用二叉链表存)

1.求高手帮忙,一个数据作业 论文： 建立一棵二叉树,使用二叉链表存

#include"stdio.h"#include"stdlib.h"#define MAXSIZE 30 typedef struct BiThTree { char data; struct BiThTree *lchild,*rchild; }BiTreeNode; int ye; void InitBiTree(BiTreeNode **Bt) { *Bt=(BiTreeNode *)malloc(sizeof(BiTreeNode)); (*Bt)->lchild=(*Bt)->rchild=NULL; } BiTreeNode *CreatBiTree(BiTreeNode **Bt,char *tr) { BiTreeNode *p[MAXSIZE],*q=NULL; int i=0,k; int top=-1; *Bt=NULL; while(tr[i]!='/0') { switch(tr[i]) { case'(': k=1；//对左孩子进行操作 top++; p[top]=q; break; case')': top--; break; case',': k=2; break; default: q=(BiTreeNode *)malloc(sizeof(BiTreeNode)); q->data=tr[i]; q->lchild=q->rchild=NULL; if(*Bt==NULL) *Bt=q; else if(k==1) p[top]->lchild=q; else if(k==2) p[top]->rchild=q; break; } i++; } return *Bt； }//按中序遍历二叉树 递归算法 int InorderBiTree(BiTreeNode *Bt) { BiTreeNode *p=Bt; if(p==NULL) return 0; else { InorderBiTree(p->lchild); printf("%c ",p->data); InorderBiTree(p->rchild); } return 1; } int PreorderBiTree(BiTreeNode *Bt) { BiTreeNode *p=Bt; if(p!=NULL) { printf("%c",p->data); PreorderBiTree(p->lchild); PreorderBiTree(p->rchild); } return 1； }//先序递归遍历 int PostorderBiTree(BiTreeNode *Bt) { BiTreeNode *p=Bt; if(p!=NULL) { PostorderBiTree(p->lchild); PostorderBiTree(p->rchild); printf("%c",p->data); } printf("/n"); return 1； }//后序递归遍历//按中序遍历二叉树 非递归算法 void FeiBiTree(BiTreeNode *Bt) { int top=0; BiTreeNode *s[MAXSIZE]; BiTreeNode *p=Bt; while(top>-1) { if(p!=NULL) { s[top]=p; top++; p=p->lchild; } else { top--; if(top>-1) { p=s[top]; printf("%3c",p->data); p=p->rchild; } } } printf("/n"); } void CengBiTree(BiTreeNode *Bt) { BiTreeNode *p=Bt,*q=NULL; BiTreeNode *s[MAXSIZE]; int front=0,rear=0; printf（"层序遍历结果：/n"）; if(p!=NULL) { front=(front+1)%MAXSIZE; s[front]=p; } while(rear!=front) { rear=(rear+1)%MAXSIZE; printf("%2c",s[rear]->data); p=s[rear]; if(p->lchild) { front=(front+1)%MAXSIZE; s[front]=p->lchild; } if(p->rchild) { front=(front+1)%MAXSIZE; s[front]=p->rchild； } } }//求二叉树的深度 int DepthBiTree(BiTreeNode *Bt) { BiTreeNode *p=Bt; int dep=0,lh=0,rh=0; if(p!=NULL) { lh=DepthBiTree(p->lchild); rh=DepthBiTree(p->rchild); dep=(lh>rh)?(++lh):(++rh); return dep; } else return 0； }//求二叉树的树叶 int YeshuBiTree(BiTreeNode *Bt) { BiTreeNode *p=Bt; if(p==NULL) return 0; else { if((p->lchild==NULL)&&(p->rchild==NULL)) ye++; YeshuBiTree(p->lchild); YeshuBiTree(p->rchild); } return ye; } void main() { BiTreeNode *BTr=NULL; char TR[MAXSIZE]; int ye,gao,n; printf（"建立一个二叉树！/n"）; printf（"请输入二叉树的字符序列串：/n"）; scanf("%s",TR); InitBiTree(&BTr); BTr=CreatBiTree(&BTr,TR); do{ printf（"请选择：/n"）; printf("---------------*********************----------------/n/n"); printf("/t/t中序递归遍历二叉树---1:/n/n"); printf("/t/t中序非递归遍历二叉树---2:/n/n"); printf("/t/t层序遍历二叉树---3:/n/n"); printf("/t/t求树的高度---4:/n/n"); printf("/t/t求树的叶子数---5:/n"); printf("/t/t退出该程序---6/n/n"); printf("---------------*********************---------------/n/n"); scanf("%d",&n); switch(n) { case 1: InorderBiTree(BTr); break; case 2: FeiBiTree(BTr); break; case 3: CengBiTree(BTr); break; case 4: gao=DepthBiTree(BTr); printf("/n该二叉树的高为：%d/n",gao); break; case 5: ye=YeshuBiTree(BTr); printf（"该二叉树的叶数为：%d/n",ye）; break; case 6: exit(0); } }while(n!=6); }。

2.二叉树基本操作设计及实现

# include # include struct BTNode{ int data; struct BTNode * pLchild;//p是指针，L是左，child是孩子 struct BTNode * pRchild；}；//函数声明struct BTNode * CreateBTree(void)；//创建树void PreTraverseBTree(struct BTNode * pT)；//先序遍历void InTraverseBTree(struct BTNode * pT)；//中序遍历void PostTraverseBTree(struct BTNode * pT)；//后续遍历int main(void){ struct BTNode * pT = CreateBTree(); PreTraverseBTree(pT); printf("\n"); InTraverseBTree(pT); printf("\n"); PostTraverseBTree(pT); return 0；}//创建树struct BTNode * CreateBTree(void){ struct BTNode * pA = (struct BTNode * )malloc(sizeof(BTNode)); struct BTNode * pB = (struct BTNode * )malloc(sizeof(BTNode)); struct BTNode * pC = (struct BTNode * )malloc(sizeof(BTNode)); struct BTNode * pD = (struct BTNode * )malloc(sizeof(BTNode)); struct BTNode * pE = (struct BTNode * )malloc(sizeof(BTNode)); pA->data = 'A'; pB->data = 'B'; pC->data = 'C'; pD->data = 'D'; pE->data = 'E';pA->pLchild = pB; pA->pRchild = pC; pB->pLchild = NULL; pB->pRchild = NULL; pC->pLchild = pD; pC->pRchild = NULL; pD->pLchild = NULL; pD->pRchild = pE; pE->pLchild = NULL; pE->pRchild = NULL;return pA；}//先序遍历void PreTraverseBTree(struct BTNode * pT){ //先访问根节点，再先序访问左子树，最后先序访问右子树 if ( pT != NULL) { printf("%c\n",pT->data)；//访问根节点 //pT->pLchild可以代表整个左子树 PreTraverseBTree(pT->pLchild); PreTraverseBTree(pT->pRchild); }return；}//中序遍历void InTraverseBTree(struct BTNode * pT){ if(pT != NULL ) { if (NULL != pT->pLchild) { InTraverseBTree(pT->pLchild); } printf("%c\n",pT->data); if (NULL != pT->pRchild) { InTraverseBTree(pT->pRchild); } } return；}//后续遍历void PostTraverseBTree(struct BTNode * pT){ if(pT != NULL ) { if (NULL != pT->pLchild) { PostTraverseBTree(pT->pLchild); }if (NULL != pT->pRchild) { PostTraverseBTree(pT->pRchild); } printf("%c\n",pT->data); } return;}。

3.二叉树基本操作设计及实现

/*以下程序是百度知道C++爱好者团副团长enochwills应团长21chenxb邀请专门为VC编写的二叉树基本操作实现WINDOWS图形化直观展示程序：实现对二叉树的查询和插入操作；（1）实现二叉树的生成。

（2）实现对二叉树的遍历查询；（3）实现对二叉树叶节点的增加； （4）将整棵树画在屏幕上*/#include #include #include struct BTree { int data; struct BTree * left; struct BTree * right;};//end struct BTreeBTree * CreateLeaf(int number){ BTree * l = new BTree; l->data = number; l->left = 0; l->right = 0; return l;}//end CreateLeafvoid append(BTree ** root, int number){ if (!root) return ; BTree * t = *root; if (!t) { *root = CreateLeaf(number); return ; }//end if while(t) { if(number == t->data ) return ; //ignore duplicated elements. if(number < t->data ) { if(!t->left ) { t->left = CreateLeaf(number); return ; }//end if t = t->left ; }else{ if(!t->right ) { t->right = CreateLeaf(number); return ; }//end if t = t->right ; }//end if }//end while}//end appendvoid PrintLeaf(const BTree * root){ if (!root) return ; if (root->left ) PrintLeaf(root->left ); printf("%d\t", root->data); if (root->right ) PrintLeaf(root->right );}//end printLeafvoid PrintTree (const BTree * root){ printf("[\t"); PrintLeaf(root); printf("]\n");}//end printTreeBTree * global_root = 0;int Offsets[32];int LevelHeight = 50;void GDIShowTree(HDC h, BTree * root, int level, int center){ if (!root || !h) return ; char number[32] = ""; sprintf(number, "%d", root->data ); int x0 = center; int off = Offsets[level + 1]; int x1 = 0; int y0 = level * LevelHeight; int y1 = y0 + LevelHeight; if (root->left ) { x1 = x0 - off; GDIShowTree(h, root->left , level + 1, x1); MoveToEx(h, x0, y0, 0); LineTo(h, x1, y1); }//end if if (root->right) { x1 = x0 + off; GDIShowTree(h, root->right, level + 1, x1); MoveToEx(h, x0, y0, 0); LineTo(h, x1, y1); }//end if TextOut(h, x0, y0, number, strlen(number));}//end GDIShowTreeLRESULT CALLBACK MsgProc( HWND hwnd, // handle to window UINT uMsg, // message identifier WPARAM wParam, // first message parameter LPARAM lParam) // second message parameter{ 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; }//next i GDIShowTree(hDC, global_root, 0, r.right / 2); EndPaint(hwnd,&ps); break; case WM_CLOSE: exit(0); default: return DefWindowProc(hwnd,uMsg,wParam,lParam); }//end case return 0;}//end MsgProcint main(void){ int x = 0; printf("Enter some numbers ended with 0:"); do { scanf("%d", &x); append(&global_root, x); }while(x); PrintTree(global_root); 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_ERROR); 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","Enoch WILLS 2010",WS_OVERLAPPEDWINDOW, 0,0,640,480,0,0,0,0); ShowWindow(hwnd,SW_MAXIMIZE); UpdateWindow(hwnd); MSG msg; while(GetMessage(&msg,NULL,0,0)) { TranslateMessage(&msg); DispatchMessage(&msg); }//end while return 0;}//end main。

4.用C语言编写二叉树的建立与遍历

以下是我的数据结构实验的作业：肯定好用，里面还包括了统计树的深度和叶子数！记住每次做完一个遍历还要重新输入你的树哦！ #include "stdio。

h" #include "string。h" #define NULL 0 typedef struct BiTNode{ char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Create(BiTree T){ char ch; ch=getchar(); if(ch=='#') T=NULL; else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf("Error!"); T->data=ch; T->lchild=Create(T->lchild); T->rchild=Create(T->rchild); } return T; } void Preorder(BiTree T){ if(T){ printf("%c",T->data); Preorder(T->lchild); Preorder(T->rchild); } } int Sumleaf(BiTree T){ int sum=0,m,n; if(T){ if((!T->lchild)&&(!T->rchild)) sum++; m=Sumleaf(T->lchild); sum+=m; n=Sumleaf(T->rchild); sum+=n; } return sum; } void zhongxu(BiTree T){ if(T){ zhongxu(T->lchild); printf("%c",T->data); zhongxu(T->rchild); } } void houxu(BiTree T){ if(T){ houxu(T->lchild); houxu(T->rchild); printf("%c",T->data); } } int Depth(BiTree T){ int dep=0,depl,depr; if(!T) dep=0; else{ depl=Depth(T->lchild); depr=Depth(T->rchild); dep=1+(depl>depr?depl:depr); } return dep; } main(){ BiTree T; int sum,dep; T=Create(T); Preorder(T); printf("\n"); zhongxu(T); printf("\n"); houxu(T); printf("\n"); sum=Sumleaf(T); printf("%d",sum); dep=Depth(T); printf("\n%d",dep)； } 在Turbo C的环境下，先按Ctrl+F9运行程序，此时就是建立二叉树的过程，例如输入序列ABC##DE#G##F###（其中的“#”表示空，并且输入过程中不要加回车，因为回车也有对应的ASCII码，是要算字符的，但是输入完之后可以按回车退出），然后再按ALT+F5显示用户界面，这时候就能够看到结果了。

另外你必须会手动建立一棵二叉树，保证你输入的序列能构成一棵二叉树，否则你怎么输入，按最后按多少回车程序也不会结束！ 下面是我举的例子的二叉树的图形表示（画的不好，别见笑），如果可能，把你想建立的二叉树也发上来。

5.

建立头指针 h，和指向当前节点的指针 p = h;

按 先序 或 中序 遍历该2叉树.

当碰到叶子节点 c 时：

p->rchild = c;

p = c;

遍历结束，返回h

*****************************

struct Node{

DateType date;

struct Node *lchild,*rchild

}*h,*p;

main()

{

*h = (Node *)malloc(sizeof(Node));

*p = h;

Node *tree;

/*取得2叉树*/

/*遍历*/

PreOderTraverse(tree);

p = h->rchild;

free(h);

/*输出p*/

}

PreOrderTraverse(Node node)

{

if(node == null) return;

if(node->lchild == null && node->rchild == null)

{p->rchild = node;

p = node;

return;

}

PreOrderTraverse(node->lchild)

PreOrderTraverse(node->rchild)

}

6.二叉树的遍历操作实现二.实验内容与要求1.建立二叉树二 爱问知

// S_lbecs。

cpp ： 定义控制台应用程序的入口点。//链表二叉树的定义和操作#include "stdafx。

h"#include "stdio。h"#include "malloc。

h"#include "string。h"#include "stdlib。

h"#define Max 20 //最大节点个数typedef struct node{ char data; struct node *lchild,*rchild； //左边孩子的指针 和 右边孩子的指针}BinTNode;typedef BinTNode *BinTree； //定义二叉树的指针int NodeNum,leaf; //NodeNum是结点数 leaf是叶子数//基于先序遍历算法创建二叉树//要求输入先序序列，其中加入虚结点“#”以示空指针的位置BinTree CreatBinTree(void){ BinTree T; char ch; scanf("%c",&ch); if(ch=='#') //读入# 返回空指针 return(NULL); else{ T=(BinTNode *)malloc(sizeof(BinTNode)）； //生成结点 T->data=ch; T->lchild=CreatBinTree（)； //构造左子树 T->rchild=CreatBinTree（)； //构造右子树 return(T); }}//DLR 先序遍历//访问根节点 先序遍历左子树 先序遍历右子树void Preorde(BinTree T){ if(T){ printf("%c",T->data)； //访问结点 D Preorde(T->lchild)； //先序遍历左子树 L Preorde(T->rchild)； //先序遍历右子树 R }}//LDR 中序遍历void Inorder(BinTree T){ if(T){ Inorder(T->lchild)； //中序遍历左子树 L printf("%c",T->data)； //访问结点 D Inorder(T->rchild)； //中序遍历右子树 R }}//LRD 后序遍历void Postorder(BinTree T){ if(T){ Postorder(T->lchild)； //后序遍历左子树 L Postorder(T->rchild)； //后序遍历右子树 R printf("%c",T->data)； //访问结点 D }}//采用后序遍历求二叉树的深度、结点数及叶子数的递归算法int TreeDepth(BinTree T){ int hl,hr,max; if(T){ hl=TreeDepth(T->lchild)； //求左深度 hr=TreeDepth(T->rchild)； //求右深度 max=hl>hr?hl:hr； //取最大深度 NodeNum=NodeNum 1； //求结点数 if(hl==0&&hr==0) //若左右深度都为0 则为叶子 leaf=leaf 1; return(max 1); }else{ return(0)； }}//利用“先进先出”（FIFO）队列，按层次遍历二叉树void Levelorder(BinTree T){ int front=0,rear=1; BinTNode *cq[Max],*p； //定义结点的指针数组cq cq[1]=T； //根入队 while(front!=rear){ front=(front 1)%NodeNum; p=cq[front]； //出队 printf("%c",p->data)； //输出结点的值 if(p->lchild!=NULL){ rear=(rear 1)%NodeNum; cq[rear]=p->lchild； //左子树入队 } if(p->rchild!=NULL){ rear=(rear 1)%NodeNum; cq[rear]=p->rchild； //右子树入队 } }}int _tmain(int argc, _TCHAR* argv[]){ BinTree root; int i,depth； //最大深度 printf（" 创建二叉树；输入完全二叉树先序序列："）； //用#代表虚结点 如ABD###CE##F## root=CreatBinTree（)； //创建二叉树 返回根结点 printf（" 创建成功！ "）； do{ //从菜单中选择遍历方式，输入序号。 printf(" ********** select ************ "); printf(" 1： 先序遍历 ")； printf(" 2： 中序遍历 ")； printf(" 3： 后序遍历 ")； printf(" 4： 求树的深度及叶子数 ")； printf(" 5： 按层次遍历 ")； //按层次遍历之前，先选择4，求出该树的结点数。

printf(" 0： 退出 ")； printf（" ******************************* 请选择："）； scanf("%d",&i)； //输入菜单选项 0-5 switch(i){ case 1: //1： 先序遍历 Preorde printf（"先序遍历的结果是"）； Preorde(root); // printf(" "); break; case 2: //2： 中序遍历 Inorder printf（"中序遍历的结果是"）； Inorder(root); // printf(" "); break; case 3: //3： 后序遍历 Postorder printf（"后序遍历的结果是"）； Postorder(root); // printf(" "); break; case 4: //4： 求树的深度及叶子数 TreeDepth depth=TreeDepth(root); // printf（"数的深度=%d 结点数=%d",depth,NodeNum）; printf（" 叶子数=%d",leaf）; printf(" "); break; case 5: //5： 按层次遍历 Preorde printf（"按层次遍历的结果是"）； Levelorder(root); // printf(" "); break; default: printf（"输入错误 "）； break; } }while(i!=0); return 0；}是vs做的 有些地方需要改下 是C语言做的。

转载请注明出处众文网 » 毕业论文二叉树(求高手帮忙,一个数据作业论文：建立一棵二叉树,使用二叉链表存)