二叉树课程设计毕业论文

好的，我来做吧，免费的。。。嘿嘿》》》》

//调式完毕，你copy后把不必要的注释可以去掉，交作业吧，记得采纳，这程序大部分是你自己的功劳#include#include<>using namespace std;typedef int KeyType;#define MaxElement 1024 //因二叉树结构，实际输入元素不能过多，否则递归调用时可能出异常typedef struct tree//声明树的结构{ struct tree *left; //存放左子树的指针 struct tree *right; //存放又子树的指针 KeyType key; //存放节点的内容} BSTNode, * BSTree; //声明二叉树的链表int insertBST(BSTree &pRoot,KeyType key) // 在二叉排序树中插入结点 参数:改为根结点的引用 key值 Ok了{//若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回 BSTree f,p=pRoot; //p的初值指向根结点 while(p) //查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲 { if(p->key==key) //树中已有key，无须插入 return 0; f=p; //f保存当前查找的结点，即f是p的双亲 p=(keykey)?p->left:p->right; } p=(BSTree)malloc(sizeof(BSTNode)); //生成新结点 p->key=key; p->left=p->right=NULL; if(pRoot==NULL) //原树为空，新插入的结点为新的根 pRoot=p; else if(keykey) f->left=p; else f->right=p; return 1;}BSTree createBST(int *iArr)//建立二叉树{//这个不方便重复使用,大改一下了, 参数中有则直接用参数中的，没有则键盘输入 BSTree t=NULL; //根结点 KeyType key; int i=0; if(!*iArr) { cin>>key; while(key!=-1 && ++i>key; } } for(i=1;i<=*iArr;i++) //由数组形式 生成 二叉树状集合形式 { insertBST(t,iArr[i]); } return t;}void inorder_btree(BSTree root)// 中序遍历打印二叉排序树 OK{ BSTree p=root; if(p!=NULL){ inorder_btree(p->left ); cout<<" "<key<<" "; inorder_btree(p->right ); }}BSTree searchBST(BSTree t,KeyType key)//元素判定 注意 Ok{ //这里稍改，返回结点指针或空 比较合适 //if(key==t->key)return t->key; //如果不是它的元素，你这会先访问了一个空指针的结点 //if(t==NULL)return 0; 上下这两行顺序放错了先这行再上面一行还可以 且0也可能是元素之一 //综合起来就是这个返回类型定得不合适，改为返回指针，未找到时返回空指针 找到时返回所在位置 if(!t || key==t->key) return t; //<<< 先判是不是空指针，非空了再判是不是相等了 if(keykey) return searchBST(t->left,key); else return searchBST(t->right,key);}int deleteBST(BSTree &pRoot,KeyType key)//删除 本函数暂未测试{ BSTree p,tmp,parent=NULL; p=pRoot; while(p) { if(p->key==key) break; parent=p; p=(keykey)?p->left:p->right; } if(!p) return 0; tmp=p; if(!p->right&&!p->left) /*p的左右子树都为空*/ { if(!parent) //要删根，须修改根指针 pRoot=NULL; else if(p==parent->right) parent->right=NULL; else parent->left=NULL; free(p); } else if(!p->right) //p的右子树为空，则重接p的左子树 { p=p->left; if(!parent) //要删根，须修改根指针 pRoot=p; else if(tmp==parent->left) parent->left=p; else parent->right=p; free(tmp); } else if(!p->left) //的左子树为空，则重接p的左子树 { p=p->right; if(!parent) //要删根，须修改根指针 pRoot=p; else if(tmp==parent->left) parent->left=p; else parent->right=p; free(tmp); } else if(p->right&&p->left) //p有左子树和右子树，用p的后继覆盖p然后删去后继 { //另有方法：用p的前驱覆盖p然后删去前驱||合并p的左右子树 parent=p; //由于用覆盖法删根，则不必特殊考虑删根 p=p->right; while(p->left) { parent=p; p=p->left; } tmp->key=p->key; if(p==parent->left) parent->left=NULL; else parent->right=NULL; free(p); } return 1;}void inorder_btree2Arr(BSTree root,int *Arr)//中序遍历 输出到数组中 数组第0个元素放个数(初始必需为0){ BSTree p=root; if(p!=NULL){ inorder_btree2Arr(p->left, Arr); (*Arr)++; //<<<数组首个地址进来之前一定要置为0!!!! 我约定的，不许赖啊 否则程序死掉不怨我 Arr[*Arr] = p->key; //Arr[*Arr]等价于Arr[Arr[0]] inorder_btree2Arr(p->right, Arr); }}void inorder_btreeCount(BSTree root,int &n)//统计个数 n 初始必需为0 否则数得不对{ BSTree p=root; if(p!=NULL){ inorder_btreeCount(p->left, n); n++; inorder_btreeCount(p->right, n); }}int beyong(BSTree m,BSTree n) //子集判定{ //if(m->key==n->left)//这是什么算法啊，我看不懂呀 汗 是语法错误!! 只得改写了 //return m->key; //else // return 0; int i,Array[MaxElement]={0};//不懂怎么一个一个的来访问树结点，只好使个懒人的方法，转成数组，再遍历数组啦 inorder_btree2Arr(n,Array);//返回的数组第一元素为长度，之后是数据 for(i=1;i<=*Array;i++) if(!searchBST(m,Array[i])) return 0;//有元素找不着就不是子集了 return 1;//都能找着，就是子集}void combineTree(BSTree A,BSTree B,BSTree &C) //A+B=C 并集{ int i,Array[MaxElement]={0}; inorder_btree2Arr(A,Array); C = createBST(Array); //A 先复制到 C Array[0]=0; inorder_btree2Arr(B,Array); for(i=1; i<=*Array; i++) insertBST(C,Array[i]);//B的每个元素试着插入C,重复元素自动忽略}void joinTree(BSTree A,BSTree B,BSTree &C) //A*B=C 交集{ int i,Array[MaxElement]={0},Array1[MaxElement]={0}; inorder_btree2Arr(B,Array); for(i=1;i<=*Array;i++) if(searchBST(A,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}//求相交的所有元素 if(Array1[0]) C = createBST(Array1); //结果不空时 再组一个集合 else C=NULL;}void differencedTree(BSTree A,BSTree B,BSTree &C) //A-B=C 差集{ int i,Array[MaxElement]={0},Array1[MaxElement]={0}; inorder_btree2Arr(A,Array);//列出A中所有元素 for(i=1;i<=*Array;i++) if(!searchBST(B,Array[i])){Array1[0]++; Array1[Array1[0]] = Array[i];}//求出不属于B的所有元素 if(Array1[0]) C = createBST(Array1); //结果不空时 再组一个集合 else C=NULL;}int main(){ int i,e; int iArray[MaxElement]={0};//数组形式的整数集合 做输入输出缓冲,输入时先在这暂存 BSTree root1,root2,root3,root4,root5; cout<<"请输入你所要创建的集合LA，以-1结束：\n"; //<<<怎么看着不伦不类呀，这换行，有C风格的\n iArray[0]=0; root1=createBST(iArray); cout<<"\n\n中序遍历二叉树："<

《数据结构》实验三——二叉树排序算法*试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。*/Exchange(pBiNode BiTree){ pBiNode p; if(BiTree) { p = BiTree->lChild; BiTree->lChild = BiTree->rChild; BiTree->rChild = p; Exchange(BiTree->lChild); Exchange(BiTree->rChild); }}/*这个算法要求同学必须掌握*/《数据结构》实验三——动态查找*1.试按表(10,8,9,12,20,5,6,15,19,25)中元素的排列次序，将所有元素插入一棵初始为空的二叉排序树中，使之仍是一棵二叉排序树，请设计算法2.在已构建的二叉排序树中插入元素40，使之依然为二叉排序树*/#include <>typedef struct node{ int data; struct node * lChild,*rChild;}node,*BTNode;BTNode Create(BTNode BiTree){ int n; BTNode p,q; scanf("%d",&n); for(;n != 0;) { p = (BTNode)malloc(sizeof(struct node)); p->data = n; p->lChild = NULL; p->rChild = NULL; if(!BiTree) BiTree = p; else { q = BiTree; while(q->data != n) { if(q->data > n) if(q->lChild != NULL) q = q->lChild; else q->lChild = p; else if(q->rChild != NULL) q = q->rChild; else q->rChild = p; } } scanf("%d",&n); } return BiTree;}InOrderTraverse(BTNode BiTree){ if(BiTree) { InOrderTraverse(BiTree->lChild); printf("%4d",BiTree->data); InOrderTraverse(BiTree->rChild); }}Insert(BTNode BiTree,int n){ BTNode p,q = BiTree; while(q->data != n) { if(q->data > n) if(q->lChild != NULL) q = q->lChild; else { p = (BTNode)malloc(sizeof(struct node)); p->data = n; p->lChild = p->rChild = NULL; q->lChild = p; } else if(q->rChild != NULL) q = q->rChild; else { p = (BTNode)malloc(sizeof(struct node)); p->data = n; p->lChild = p->rChild = NULL; q->rChild = p; } }}main(){ BTNode BTRoot; BTRoot = NULL; BTRoot = Create(BTRoot); printf("\n Sorted numbers are:\n"); InOrderTraverse(BTRoot); Insert(BTRoot,40); printf("\nAfter instert numbers are:\n"); InOrderTraverse(BTRoot); printf("\n");}*将序列（13,15,22,8,34,19,21）插入到一个初始时是空的哈希表中，哈希函数采用hash(x)=1+(x MOD 7)。使用线性探测法解决冲突*/#define N 8struct number{ int data; int flag; /*冲突与否标志*/}hx[N] = {0};Create_hxTable(struct number a[]){ int i,j,n; for(i = 1;i < 8;i++) { scanf("%d",&n); j= 1 + n % 7; while(a[j].flag) j = (j + 1) % N; a[j].data = n; a[j].flag = 1; }}main(){ int i; Create_hxTable(hx); for(i = 0;i < N;i++) { if(hx[i].flag) printf("%3d",hx[i].data); else printf(" * "); } printf("\n");}Joseph算法实现#include <>typedef struct s{ int no,password; struct s *next;}*node;node create_cycle(int n){ node head,end,p; int i; head = NULL; end = NULL; printf("Please input %d passwords(password > 0)\n",n); for(i = 1;i <= n;i++) { p = (node)malloc(sizeof(struct s)); scanf("%d",&p->password); p->no = i; if(!head) { head = p; end = p; } else { end->next = p; end = p; } } end->next = head; head = end; return head;}void out_link(node head,int n,int m){ int i,j,k = m; node p = head,q; for(i = 1;i < n;i++) { for(j = 1;j < k;j++) p = p->next; q = p->next; k = q->password; p->next = q->next; printf("%3d",q->no); free(q); } printf("%3d",p->no); free(p);}void main(){ node head; int n,m; printf("Please input numbers of people and init_password\n"); scanf("%d%d",&n,&m); head = create_cycle(n); printf("Out link sequence is:\n"); out_link(head,n,m); printf("\n");}串操作：判断子串int find(char *c1,char *c2){ int flag = -1,i,j; for(i = 0;*(c1 + i);i++) { j = 0; if(*(c1 + i) == *(c2 + j)) { flag = i; for(;*(c1 + i) && *(c2 + j) && *(c1 + i) == *(c2 + j);i++,j++) ; /*空循环，继续判断是否匹配*/ if(*(c2 + j) == '\0') /*找到匹配的串*/ break; else flag = -1; } } return flag;}void main(){ char c1[30],c2[30]; int f; scanf("%s%s",c1,c2); f = find(c1,c2); if(f == -1) printf("No\n"); else printf("Yes! Position is %d\n",f + 1);}/*找二叉树的叶节点及统计叶节点个数*/int ShowLeaves(pBiNode BiTree){ static int i = 0; if(BiTree) { ShowLeaves(BiTree->lChild); ShowLeaves(BiTree->rChild); if((BiTree->lChild==NULL)&&(BiTree->rChild==NULL)) { printf("%c",BiTree->data); i++; } } return i;}/*求二叉树的深度*/int Depth(pBiNode BiTree){ int dep1,dep2; if(BiTree==NULL)return 0; else { dep1=Depth(BiTree->lChild); dep2=Depth(BiTree->rChild); return dep1>dep2? dep1+1: dep2+1; }}二叉树的创建和遍历(递归)#include <>typedef struct BiNode{ char data; struct BiNode *lChild,*rChild;}BiNode,*pTree;CreateTree(pTree *BTRoot){ char ch; scanf("%c",&ch); if(ch == '#') (*BTRoot) = NULL; else { (*BTRoot) = (pTree)malloc(sizeof(BiNode)); (*BTRoot)->data = ch; CreateTree(&((*BTRoot)->lChild)); CreateTree(&((*BTRoot)->rChild)); }}PreOrderTraverse(pTree pRoot){ if(pRoot) { printf("%c ",pRoot->data); PreOrderTraverse(pRoot->lChild); PreOrderTraverse(pRoot->rChild); }}InOrderTraverse(pTree pRoot){ if(pRoot) { InOrderTraverse(pRoot->lChild); printf("%c ",pRoot->data); InOrderTraverse(pRoot->rChild); }}PostOrderTraverse(pTree pRoot){ if(pRoot) { PostOrderTraverse(pRoot->lChild); PostOrderTraverse(pRoot->rChild); printf("%c ",pRoot->data); }}main(){ pTree root = NULL; CreateTree(&root); printf("\n\nPreOrder is :\n"); PreOrderTraverse(root); printf("\n\nInOrder is :\n"); InOrderTraverse(root); printf("\n\nPostOrder is :\n"); PostOrderTraverse(root); printf("\n");}循环链表的建立及两循环链表的链接 #include <>typedef struct s{ int num; struct s *next;}*ls;ls creat(){ ls head,p,end; int i; static int n = 501; head = (ls)malloc(sizeof(struct s)); head->next = NULL; end = head; for(i = 1;i <= 10;i++) { p = (ls)malloc(sizeof(struct s)); p->num = n++; end->next = p; end = p; } p->next = head; return head;}ls link_two(ls h1,ls h2){ ls end1,end2,p; for(p = h1->next;p->next != h1;p = p->next) end1 = p; for(p = h2->next;p->next != h2;p = p->next) end2 = p; end1->next = h2->next; end2->next = h1; free(h2); return h1;}main(){ ls head1,head2,head,p; head1 = creat(); head2 = creat(); head = link_two(head1,head2); for(p = head->next;p != head;p = p->next) printf("%5d",p->num);}与课堂上讲的稍修改了下，把n改为了静态变量static int n = 501;creat()函数不带参数 单链表的建立、节点查找、插入、删除等操作实现 #include <>typedef struct s{ int num; struct s *next;}*ls;ls creat(){ ls head,p,end; int i,n = 501; head = (ls)malloc(sizeof(struct s)); head->next = NULL; end = head; for(i = 1;i <= 10;i++) { p = (ls)malloc(sizeof(struct s)); p->num = n++; end->next = p; end = p; } p->next = NULL; return head;}ls find_front(ls head,ls e){ ls p; p = head->next; for(;p->next && p->next->num != e->num;p = p->next) if(p->next->num == e->num) return p; else return NULL;}void insert_front(ls head,ls e,ls f){ ls p; p = find_front(head,e); f->next = p->next; p->next = f;}main(){ ls head,p,e,f; head = creat(); for(p = head->next;p;p = p->next) printf("%5d",p->num); printf("\n"); e = (ls)malloc(sizeof(struct s)); f = (ls)malloc(sizeof(struct s)); scanf("%d%d",&e->num,&f->num); e->next = NULL; f->next = NULL; /*p = find_front(head,e);*/ insert_front(head,e,f); printf("Inerted!\n"); for(p = head->next;p;p = p->next) printf("%5d",p->num);} 节点删除void delete(ls head,ls e){ ls p,q; p = find_front(head,e); q = p->next; p->next = p->next->next; free(q);}堆栈操作（检验符号匹配实例）#include <>#include <>typedef struct stack{ char c; struct stack *next;}*node;node push(node top,node new) /*入栈*/{ if(top == NULL) top = new; else { new->next = top; top = new; } return top;}node pop(node top) /*出栈*/{ node p; if(!top) { printf("NULL stack\n"); return NULL; } else { p = top; top = top->next; free(p); return top; }}char top_data(node top) /*取栈顶数据*/{ char ch = 0; if(!top) return 0; else ch = top->c; return ch;}void main(){ char ch; node top = NULL,p; for(;(ch = getchar()) != '\n';) /*输入表达式*/ { if(ch == '(' ||ch == '[' ||ch == '{') { p = (node)malloc(sizeof(struct stack)); p->c = ch; p->next = NULL; top =push(top,p); } else if(ch == ')') { if(top_data(top) != '(') { printf("No\n"); exit(); } else top = pop(top); } else if(ch == ']') { if(top_data(top) != '[') { printf("No\n"); exit(); } else top = pop(top); } else if(ch == '}') { if(top_data(top) != '{') { printf("No\n"); exit(); } else top = pop(top); } } if(top) printf("No\n"); else printf("Yes\n");}

/*以下是用c++ 实现的二叉排序树的源代码*/#include<>typedef struct TreeNode{int key;struct TreeNode *left;struct TreeNode *right;}treeNode;class BiSortTree{public: BiSortTree(void);void desplayTree(void);//显示这个树void insertTree(int key);//在树中插入一个值 deleteTree(int key);//在树中删除一个值 treeNode* searchTree(int key);//在树中查找一个值 ~BiSortTree();private:treeNode* buildTree(treeNode* head,int number);//建立一个树treeNode* search(treeNode* head ,int key);//查找treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p);//查找出p的父亲节点的指针treeNode* BiSortTree::searchMinRight(treeNode* head);//找到右子树中最小的节点void showTree(treeNode* head);//显示 void destroyTree(treeNode* head);//删除treeNode *Head;};/**************以下是建立一个二叉排序树****************/BiSortTree::BiSortTree(){ cout<<"建立一棵二叉排序树,请输入你要建树的所有数(以-1 作为结束标志!): "<>number; while(number!=-1) { Head=buildTree(Head,number); cin>>number; }}treeNode* BiSortTree::buildTree(treeNode* head,int number){treeNode *p; p=new treeNode; p->key=number;p->left =p->right=NULL;if(head==NULL){return p;}else{ if(p->key key)head->left=buildTree(head->left,number); else head->right=buildTree(head->right,number); return head;}}/*****************以下是在一棵二叉排序树插入一个数***********************************/void BiSortTree::insertTree(int key){Head=buildTree(Head,key);}/*****************以下是在一个二叉排序树查找一个数是否存在*************************/treeNode* BiSortTree::searchTree(int key){return search(Head,key);}treeNode* BiSortTree::search(treeNode* head ,int key){ if(head==NULL)return NULL;if(head->key==key)return head;else{if(keykey )return search( head->left,key); elsereturn search(head->right,key);}}/************以下是在一个二叉排序树删除一个给定的值*********************************/BiSortTree::deleteTree(int key){treeNode *p;p=NULL; p=search(Head,key);if(p==NULL){cout<<"Don't find the key";} if(p==Head){Head=NULL;}else{treeNode* parent;parent=searchParent(Head,p);if(p->left==NULL&&p->right==NULL)//叶子节点{ if(parent->left==p){parent->left=NULL;} else{parent->right=NULL;}} else//非叶子节点{ if(p->right==NULL)//该节点没有右孩子 { if(parent->left==p) { parent->left=p->left ; } else { parent->right=p->left; } } else//该点有左右孩子 { treeNode * rightMinSon,* secondParent;//secondParent为右子树中的最小节点的父亲 rightMinSon=searchMinRight(p->right); secondParent=searchParent(p->right ,rightMinSon); secondParent->left=rightMinSon->right;if(p->right==rightMinSon)//右子树中的最小节点的父亲为p { p->right=rightMinSon->right ; } p->key=rightMinSon->key ;}}}}treeNode* BiSortTree::searchParent(treeNode* head,treeNode* p){if(head->left==p||head->right==p||head==p||head==NULL)return head; else{if(p->keykey)return searchParent(head->left ,p);elsereturn searchParent(head->right ,p);}}treeNode* BiSortTree::searchMinRight(treeNode* head)//找到右子树中最小的节点{if(head->left ==NULL||head==NULL){return head;}else{return searchMinRight(head->left);}}/*****************以下是显示一个二叉排序树****************************************/void BiSortTree::desplayTree(void){showTree(Head);cout<left ) ; cout<key<<' ' ;showTree(Head->right) ;}}/*****************以下是删除一棵整二叉排序树************************************/BiSortTree::~BiSortTree(){cout<<"已经消除了一棵树!!!!"<left );destroyTree(head->right );delete head;}}/*********************/void print(){ cout<>choiceNumber; switch(choiceNumber) { case 1: ();break; case 2: cout<<"请插入一个数: "<>number; (number); (); break; case 3: cout<<"请插入你要找数: "<>number; if((number)==NULL) { cout<<"没有发现"<>number; (number); (); break; default: break; } cout<<"你是否要继续(Y/N)?"<>flag; if(flag=='N'||flag=='n')break;}}