| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1749 人关注过本帖
标题:小妹哭求一题的算法,各为好心的哥哥姐姐救救偶呀。
只看楼主 加入收藏
激情依旧
Rank: 1
等 级:新手上路
威 望:2
帖 子:524
专家分:0
注 册:2005-4-4
收藏
得分:0 
   呵呵。MM他是用递归写的。你不知道明白不。不知道这个论坛谁有本事写出非递归的二叉书遍历来。

生是编程人!!!!死是编程鬼!!!!颠峰人生!!!焚尽编程!!! 爱已严重死机!情必须重新启动!情人已和服务器断开连接!网恋也需要重新拨号!-----激情依旧
2005-05-16 07:19
小馨
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2005-5-14
收藏
得分:0 

哇,好复杂呀,看不懂哈,不过还是谢谢拉。 我那道题用下面这个程序能过么,大概意思好像差不多哟。 #include <stdio.h> #include<malloc.h> #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *left,*right; } BTree;

void creatree(BTree **BT,char *str) { BTree *stack[MaxSize],*p; int top=-1,k,j=0;/*top为栈指针,k指定是左还是右孩子,j为str指针*/ char ch; *BT=NULL; ch=str[j]; while (ch!='\0') { switch(ch) { case '(':top++;stack[top]=p;k=1; /*为左结点*/ break; case ')':top--; break; case ',':k=2; /*为右结点*/ break; default: p=(BTree *)malloc(sizeof(BTree)); p->data=ch;p->left=p->right=NULL; if (*BT==NULL) /*根结点*/ *BT=p; else { switch(k) { case 1:stack[top]->left=p; break; case 2:stack[top]->right=p; } } } j++; ch=str[j]; } } void preorder(BTree *BT) { if (BT!=NULL) { printf("%c",BT->data); preorder(BT->left); preorder(BT->right); } } void inorder(BTree *BT) { if (BT!=NULL) { inorder(BT->left); printf("%c",BT->data); inorder(BT->right); } } void postorder(BTree *B) { if (B!=NULL) { postorder(B->left); postorder(B->right); printf("%c",B->data); } } int BTreeDepth(BTree *B) { int leftdep,rightdep; if (B==NULL) return(0); else { leftdep=BTreeDepth(B->left); rightdep=BTreeDepth(B->right); if (leftdep>rightdep) return(leftdep+1); else return(rightdep+1); } } int leafcount(BTree *B) { if (B==NULL) return(0); else if (B->left==NULL && B->right==NULL) return(1); else return(leafcount(B->left)+leafcount(B->right)); }

main() { BTree *B; char *s="A(B(D,E(H,I)),C(G))"; creatree(&B,s); printf("\n前序遍历:"); preorder(B); printf("\n中序遍历:"); inorder(B); printf("\n后序遍历:"); postorder(B); printf("\nthe deepth is%d\n",BTreeDepth(B)); printf("the leafcount is %d\n",leafcount(B)); }

2005-05-16 09:47
axa
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2005-5-16
收藏
得分:0 
以下是引用tary在2005-5-15 22:35:46的发言: typedef struct BitTNode{ datatype data; struct BiTNode *lchild;*rchild; } BiTNode,*BiTree; void CreateBinTree(BinTree *T) {/*以加入结点的先序序列输入,构造二叉链表*/ char *ch; scanf("\n%c",&ch); if(ch=='0') *T=NULL; else { *T=(BinTNode *)malloc(sizeof(BinTNode)); (*T)->data=ch; CreatBinTree(&(*T)->lchild); CreatBinTree(&(*T)->rchild); } } void InOrderOut(BinTree T) {/*中序遍历输出二叉树T的结点值*/ if(T) {InOrderOut(T->lchild); printf("%3c",T->data); InOrderOut(T->rchild); } void PreOrderOut(BiTree T) {/*先序遍历输出二叉树T的结点值*/ printf("%3c",T->data); PreOrderOut(T->lchild); PreOrderOut(T->rchild); } void PostOrderOut(BiTree T) { /*后序遍历输出二叉树T的结点值*/ PostOrderOut(T->lchild); PostOrderOut(T->rchild); printf("%3c",T->data); } int Countleaf(BiTree T) { /*开始时,T为根结点所在链结点的指针,返回值为T的叶子数*/ if(T==NULL) return(0); if(T->lchild==NULL&&T->rchild==NULL) retur(1); printf(Countleaf(T->rchild)+Counleaf(T->rchild)); } main() {BtTree bt; CreateBinTree(&bt); InOrderOut(bt); PostOrderOut(bt); PreOrderOut(bt); Countleaf(bt);} 唉, 懒了, 不想写了, 就这些吧, 其它的你加吧..
这个程序有三个错误啊,可以请求版主修改一下,调试好后再贴上来吗?太谢谢了!
2005-05-16 14:18
axa
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2005-5-16
收藏
得分:0 

我把程序改成下面的,想实现建立二叉树,遍历和输出,大家帮我看看哪里错了,怎么会老是有两个错误啊,应该怎样改呢,大家指教一下,谢谢了!

typedef struct BitTNode{ datatype data; struct BiTNode *lchild;*rchild; } BiTNode,*BiTree;

void CreateBinTree(BinTree *T) { char *ch; scanf("\n%c",&ch); if(ch=='0') *T=NULL; else { *T=(BinTNode *)malloc(sizeof(BinTNode)); (*T)->data=ch; CreatBinTree(&(*T)->lchild); CreatBinTree(&(*T)->rchild); } }

void InOrderOut(BinTree T) { if(T) {InOrderOut(T->lchild); printf("%3c",T->data); InOrderOut(T->rchild); } void PreOrderOut(BiTree T) { printf("%3c",T->data); PreOrderOut(T->lchild); PreOrderOut(T->rchild); } void PostOrderOut(BiTree T) { PostOrderOut(T->lchild); PostOrderOut(T->rchild); printf("%3c",T->data); }

main() {BtTree bt; CreateBinTree(&bt); InOrderOut(bt); PostOrderOut(bt); PreOrderOut(bt); }

2005-05-16 14:25
ぁ小甜瓜ぁ
Rank: 1
等 级:新手上路
帖 子:8
专家分:0
注 册:2005-5-20
收藏
得分:0 
你以后不被赶出教室了吧!有那么多大哥帮助你。
其实我数据结构学的不是很好,以后共同交流,学习。
2005-05-22 19:39
tary
Rank: 1
等 级:新手上路
帖 子:780
专家分:0
注 册:2004-10-5
收藏
得分:0 

#define NULL 0; typedef char elemtype; typedef struct bitnode { char data; struct bitnode *lchild,*rchild; }bitnode,*bitree;

void creatree(bitree *s) { char xt; bitree t; scanf("%c",&xt); if(xt==' ') *s=NULL else { t=(bitnode*)malloc(sizeof(bitnode)); if (!t) printf("\n eroe \n"); t->data=xt; *s=t; creatree(&((*s)->lchild)); creatree(&((*s)->rchild)); } return; } void xian(bitree s) { if(s) { printf("%c->",s->data); xian(s->lchild); xian(s->rchild); } return; }

void zhong(bitree s) { if(s) { zhong(s->lchild); printf("%c->",s->data); zhong(s->rchild); } return; } void hou(bitree s) { if(s) { hou(s->lchild); hou(s->rchild); printf("%c->",s->data); } return; }

void main() { bitree s; clrscr(); printf("\n creatree \n"); creatree(&s); printf("\n xina xi:\n"); xian(s); printf("\b\n"); printf("\n zhong xi:\n"); zhong(s); printf("\b\n"); printf("\n hou xi:\n"); hou(s); printf("\b\n"); clrscr(); getch(); return; } 这个可以运行了..


┌→¨ ≮我可以学会对你很冷落≯¨←┐ │  <却学不╓══╦══╖会将爱> │ │¨←┐ ╭╩╮哭‖哭╭╩╮ ┌→¨│ └──┘收 ╲╱ ◇‖◇ ╲╱回└──┘
2005-06-01 22:23
涛声依旧
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2005-3-5
收藏
得分:0 

呵呵,小妹妹不要着急哈,大哥才看到哈,大哥帮你哈,绝对没什么问题哦~~~~!!! /* 二叉树前根周游的递归算法*/

#include<stdlib.h> #include<stdio.h> int count=0; /*全局变量*/ typedef char DataType;

struct BinTreeNode; /* 二叉树中结点 */ typedef struct BinTreeNode *PBinTreeNode; /* 结点的指针类型 */

struct BinTreeNode { DataType info; /* 数据域 */ PBinTreeNode llink; /* 指向左子女 */ PBinTreeNode rlink; /* 指向右子女 */ };

typedef struct BinTreeNode *BinTree; typedef BinTree *PBinTree; typedef PBinTreeNode BNode;

void visit(BNode p) { printf("%c ",p->info); }

PBinTreeNode root_btree(PBinTree t) { return *t; }

PBinTreeNode leftChild_btree (PBinTreeNode p) { return p->llink; }

PBinTreeNode rightChild_btree (PBinTreeNode p) { return p->rlink; } /*以下算法利用完全二叉树的性质来建立二叉树的链表结构。 参照完全二叉树的顺序对各结点进行编号。 算法中,各结点按编号从小到大的次序逐个输入两个信息:编号j及其数据域值x。 另外设立一个指针数组,把j结点的地址存放在该数组的第j个分量中。 如果j=1,则是根结点,否则j结点的父结点就是f=j/2, 于是,父子结点间就可链接起来。 */ PBinTreeNode createRest_BTree() { PBinTreeNode t,p,temp[40]; int i,j,n,f; DataType x; printf("输入欲创建的二叉树的结点个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("\n请输入二叉树结点在完全二叉树情况下结点的编号及数值:\n"); scanf("%d,%c",&j,&x); p=(PBinTreeNode)malloc(sizeof(BinTreeNode)); p->info=x; p->llink=NULL; p->rlink=NULL; temp[j]=p; if(j==1) t=p; else { f=j/2; if(j%2==0) temp[f]->llink=p; else temp[f]->rlink=p; } } return t; }

PBinTree create_BTree( void ) { /*创建完整的二叉树 */ PBinTree pbtree = (PBinTree)malloc(sizeof(BinTree)); if (pbtree != NULL) *pbtree = createRest_BTree( ); /*递归创建从根开始的二叉树 */ return pbtree; }

void preOrder( BNode p) { if (p==NULL) return; visit(p); preOrder(leftChild_btree(p)); preOrder(rightChild_btree(p)); }

void inOrder(BNode p) { if (p==NULL) return; preOrder(leftChild_btree(p)); visit(p); preOrder(rightChild_btree(p)); }

void postOrder( BNode p) { if (p==NULL) return; preOrder(leftChild_btree(p)); preOrder(rightChild_btree(p)); visit(p); }

int num_of_leaves( BinTree t) { /*计算二叉树叶结点个数*/ if (t == NULL) return 0; /*空树返回0*/ if ( t->llink == NULL && t->rlink == NULL) return 1; /*根结点是树叶返回1*/ return num_of_leaves (t->llink) + num_of_leaves (t->rlink); /*返回左子树的叶结点数+右子树的叶结点数*/ }

void countleaf( BinTree bt, int *count) { if( bt!=NULL) { if(( bt->llink==NULL) &&( bt->rlink==NULL)) { (*count)++; return; } countleaf(bt->llink,count); countleaf(bt->rlink,count); } } void Count_preOrder(BNode root) //采用先序遍历的递归算法 { if ( root!=NULL ) //非空二叉树条件,等效于 if(root) { if( !root->llink && !root->rlink) //是叶子结点则统计并打印 { count++; printf("%c\n",root->info); } //sum是全局变量 Count_preOrder(root->llink); //递归遍历左子树,直到叶子处; Count_preOrder(root->rlink); } //递归遍历右子树,直到叶子处; }

int num_of_nodes( BinTree t) { /*计算二叉树的结点个数*/ if (t == NULL) return 0; /*空树返回 0*/ return 1 + num_of_nodes( t->llink ) + num_of_nodes( t->rlink ); /*返回1+左子树的结点树+右子树的结点树*/ }

int main() { PBinTree tree = create_BTree(); printf("前根序列是:\n"); preOrder(*tree); printf("\n中根序列是:\n"); inOrder(*tree); printf("\n后根序列是:\n"); postOrder(*tree); putchar('\n'); count=num_of_leaves(*tree); printf("叶子结点数是:%d\n",count); count=num_of_nodes(*tree); printf("结点数是:%d\n",count); return 0; } 上面的程序我编译过绝对没什么问题哈~~!~~~以后多支持哥哥就是了哈~~!!

2005-06-05 21:44
涛声依旧
Rank: 1
等 级:新手上路
帖 子:38
专家分:0
注 册:2005-3-5
收藏
得分:0 
有机会多看看书这些其实都是书上的,只要把他们拿到一起就可以了哈!!有机会加哥哥哈,252675232
2005-06-05 21:48
tary
Rank: 1
等 级:新手上路
帖 子:780
专家分:0
注 册:2004-10-5
收藏
得分:0 

┌→¨ ≮我可以学会对你很冷落≯¨←┐ │  <却学不╓══╦══╖会将爱> │ │¨←┐ ╭╩╮哭‖哭╭╩╮ ┌→¨│ └──┘收 ╲╱ ◇‖◇ ╲╱回└──┘
2005-06-08 19:19
seeker
Rank: 1
等 级:新手上路
帖 子:172
专家分:0
注 册:2005-6-5
收藏
得分:0 
<P>我给出我的作业,你自己看看,不明白我也没法!


/*====ch_6_head.h====*/

#include&lt;stdio.h&gt;
#include &lt;string.h&gt;
#include&lt;malloc.h&gt;
#include&lt;conio.h&gt;
#include&lt;process.h&gt;
/***********************/
typedef int DataType;
typedef struct BiTNode
{/*树的数据结构*/
 DataType        data;
 struct BiTNode  *LChild;
 struct BiTNode  *RChild;
}BiTNode,*BiTree;
typedef BiTree QElemType; //设队列元素为二叉树的指针类型
typedef struct QNode
{
 QElemType Data;
 struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
 QueuePtr front,rear;//队头,队尾指针
}LinkQueue;
/*******************************/</P><P>BiTree Initiate()
{/*初始化为空树*/
 BiTree root=0;
 return root;
}
/**************************************/
BiTree Creat(DataType data)
 /*创建节点*/
{BiTree Temp;
  Temp=(BiTree)malloc(sizeof(BiTNode));
  //BiTree Temp=new BiTNode;
  Temp-&gt;data=data;
  Temp-&gt;LChild=0;
  Temp-&gt;RChild=0;
  return Temp;
}
/****************************************/
void  CreateBiTree(BiTree &amp;root,DataType data)
/* 降序二叉数装入数据,左子树&lt;右子树*/
{
  BiTree p=Creat(data);
  if(!root)
  {
   root=p;
  }
  else if(p-&gt;data&lt;root-&gt;data)
  {
   CreateBiTree(root-&gt;LChild,p-&gt;data);
  }
  else
  {
  CreateBiTree(root-&gt;RChild,p-&gt;data);
  } /*相等的 将装数据到右孩子 */
}
/************************************/
 void PrintTree1(BiTree root)
 /*递归前序遍历*/
{
  if(!root)  return ;
  printf("%d==&gt;",root-&gt;data);
  PrintTree1(root-&gt;LChild);
  PrintTree1(root-&gt;RChild);
  return ;
}
/************************************/
 void PrintTree2(BiTNode *root)
 /*递归中序遍历---&gt; 显示从小到大*/
{
      if(!root)  return ;
      PrintTree2(root-&gt;LChild);
   printf("%d==&gt;",root-&gt;data);
      //cout&lt;&lt;root-&gt;data&lt;&lt;" :";
      PrintTree2(root-&gt;RChild);
      return ;
}
/***********************************/
  void PrintTree3(BiTNode *root)
 /*递归后序遍历*/
{
   if(!root)  return ;
      PrintTree3(root-&gt;LChild);
      PrintTree3(root-&gt;RChild);
   printf("%d==&gt;",root-&gt;data);
   //cout&lt;&lt;root-&gt;data&lt;&lt;" :";
      return ;
}
/*******************************/
void  FreeTree(BiTree root)
{
       if(!root) return;
       FreeTree(root-&gt;LChild);
       FreeTree(root-&gt;RChild);
       free(root);//跟节点要最后删!
}

/*==============================*/


/*计算二叉树中叶子节点的数目*/
#include "ch_6_head.h"</P><P>int Leaves(BiTNode *T)//求二叉树中叶子结点的数目
{
 if(!T) return 0; //空树没有叶子
 else if(!T-&gt;LChild&amp;&amp;!T-&gt;RChild) return 1; //叶子结点
 else return (Leaves(T-&gt;LChild)+Leaves(T-&gt;RChild));
 //左子树的叶子数加上右子树的叶子数
}//Leaves
void main()
{  
  int a;//作输入变量
  int i=0;
  BiTNode *Root=Initiate();
  printf("            /**** 6.42 计算二叉树中叶子节点的数目 ****/\n");
  printf("输入二叉树的节点值(整数)\n输入 -1 退出创建:\n");
  scanf("%d",&amp;a);
  while(a!=-1)
  {      
   CreateBiTree(Root,a);
   scanf("%d",&amp;a);                        
  }
  i=Leaves(Root);
  printf("叶子结点数为:%d\n",i);
 /* printf("前序遍历为:\n");
  PrintTree1(Root);//输出所创建的树
  printf("OK!!\n中序遍历为:\n");
  PrintTree2(Root);
  printf("OK!!\n后序遍历为:\n");
  PrintTree3(Root);
  printf("OK!!\n");*/
  FreeTree(Root);//销毁树 防止内存泄漏
  getch();
}
/*==============END================*/
</P>

[此贴子已经被作者于2016-4-6 17:03编辑过]


我相信总有一片天空属于我!http://myseeker. E-Mail:lwqcny@
2005-06-08 20:29
快速回复:小妹哭求一题的算法,各为好心的哥哥姐姐救救偶呀。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025696 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved