日本军舰命名:C++二叉树的课程设计

《数据结构》实验三——二叉树排序算法
*试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。*/
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 <malloc.h>
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 8
struct 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 <malloc.h>
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 <malloc.h>
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 <malloc.h>
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 <malloc.h>
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 <malloc.h>
#include <stdio.h>
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");

}

你需要的是公式方法还是代码,对于二叉树不是很难啊,对于遍历中就是一个增加的

你告诉我油箱，代码直接发给你