找回密码
 注册
12下一页
返回列表 发新帖
查看: 2884|回复: 17

二叉树的中序遍历

[复制链接]
moonsky
发表于 2003-5-26 12:59:09 | 显示全部楼层 |阅读模式
[code:1]-----------------------------------------------------------------------

/* ======================================== */
/*    二叉树的中序遍历                      */
/* ======================================== */
#include <stdlib.h>

struct tree                       /* 树的结构宣告       */
{
   int data;                      /* 节点数据           */
   struct tree *left;             /* 指向左子树的指标   */
   struct tree *right;            /* 指向右子树的指标   */
};
typedef struct tree treenode;     /* 树的结构新型态     */
typedef treenode *btree;          /* 宣告树节点指标型态 */

/* ---------------------------------------- */
/*  插入二叉树的节点                        */
/* ---------------------------------------- */
btree insertnode(btree root,int value)
{

   btree newnode;                 /* 树根指标           */
   btree current;                 /* 目前树节点指标     */
   btree back;                    /* 父节点指标         */

   /* 建立新节点记忆体 */
   newnode = ( btree ) malloc(sizeof(treenode));
   newnode->data = value;         /* 建立节点内容       */
   newnode->left = NULL;          /* 设定指标初值       */
   newnode->right = NULL;         /* 设定指标初值       */
   if ( root == NULL )            /* 是否是根节点       */
   {
      return newnode;             /* 传回新节点位置     */
   }
   else
   {
      current = root;             /* 保留目前树指标     */
      while ( current != NULL )
      {
         back = current;          /* 保留父节点指标     */
         if ( current->data > value )    /* 比较节点值  */
            current = current->left;     /* 左子树      */
         else
            current = current->right;    /* 右子树      */
      }
      if ( back->data > value )   /* 接起父子的链结     */
         back->left = newnode;    /* 左子树             */
      else
         back->right = newnode;   /* 右子树             */
   }
   return root;                   /* 传回树根指标       */
}

/* ---------------------------------------- */
/*  建立二叉树                              */
/* ---------------------------------------- */
btree createbtree(int *data,int len)
{
   btree root = NULL;             /* 树根指标           */
   int i;

   for ( i = 0; i < len; i++ )    /* 用回路建立树状结构 */
      root = insertnode(root,data[i]);
   return root;
}

/* ---------------------------------------- */
/*  二叉树中序遍历                          */
/* ---------------------------------------- */
void inorder(btree ptr)
{
   if ( ptr != NULL )             /* 终止条件           */
   {
      inorder(ptr->left);         /* 左子树             */
      printf("[%2d]\n",ptr->data);  /* 列印节点内容     */
      inorder(ptr->right);        /* 右子树             */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立二叉树且用中序遍历列印出来. */
/* ---------------------------------------- */
void main()
{
   btree root = NULL;             /* 树根指标           */

   /* 二叉树节点数据 */
   int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   root = createbtree(data,9);    /* 建立二叉树         */
   printf("树的节点内容 \n");
   inorder(root);                 /* 中序遍历二叉树     */
}


/* ======================================== */
/*    二叉树的前序遍历                      */
/* ======================================== */
#include <stdlib.h>

struct tree                       /* 树的结构宣告       */
{
   int data;                      /* 节点数据           */
   struct tree *left;             /* 指向左子树的指标   */
   struct tree *right;            /* 指向右子树的指标   */
};
typedef struct tree treenode;     /* 树的结构新型态     */
typedef treenode *btree;          /* 宣告树节点指标型态 */

/* ---------------------------------------- */
/*  插入二叉树的节点                        */
/* ---------------------------------------- */
btree insertnode(btree root,int value)
{

   btree newnode;                 /* 树根指标           */
   btree current;                 /* 目前树节点指标     */
   btree back;                    /* 父节点指标         */

   /* 建立新节点记忆体 */
   newnode = ( btree ) malloc(sizeof(treenode));
   newnode->data = value;         /* 建立节点内容       */
   newnode->left = NULL;          /* 设定指标初值       */
   newnode->right = NULL;         /* 设定指标初值       */
   if ( root == NULL )            /* 是否是根节点       */
   {
      return newnode;             /* 传回新节点位置     */
   }
   else
   {
      current = root;             /* 保留目前树指标     */
      while ( current != NULL )
      {
         back = current;          /* 保留父节点指标     */
         if ( current->data > value ) /* 比较节点值     */
            current = current->left;  /* 左子树         */
         else
            current = current->right; /* 右子树         */
      }
      if ( back->data > value )   /* 接起父子的链结     */
         back->left = newnode;    /* 左子树             */
      else
         back->right = newnode;   /* 右子树             */
   }
   return root;                   /* 传回树根指标       */
}

/* ---------------------------------------- */
/*  建立二叉树                              */
/* ---------------------------------------- */
btree createbtree(int *data,int len)
{
   btree root = NULL;             /* 树根指标           */
   int i;

   for ( i = 0; i < len; i++ )    /* 用回路建立树状结构 */
      root = insertnode(root,data[i]);
   return root;
}

/* ---------------------------------------- */
/*  二叉树前序遍历                          */
/* ---------------------------------------- */
void preorder(btree ptr)
{
   if ( ptr != NULL )             /* 终止条件           */
   {
      printf("[%2d]\n",ptr->data);  /* 列印节点内容     */
      preorder(ptr->left);        /* 左子树             */
      preorder(ptr->right);       /* 右子树             */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立二叉树且用前序遍历列印出来. */
/* ---------------------------------------- */
void main()
{
   btree root = NULL;             /* 树根指标           */

   /* 二叉树节点数据 */
   int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   root = createbtree(data,9);    /* 建立二叉树         */
   printf("树的节点内容 \n");
   preorder(root);                /* 前序遍历二叉树     */
}



/* ======================================== */
/*    二叉树的后序遍历                      */
/* ======================================== */
#include <stdlib.h>

struct tree                       /* 树的结构宣告       */
{
   int data;                      /* 节点数据           */
   struct tree *left;             /* 指向左子树的指标   */
   struct tree *right;            /* 指向右子树的指标   */
};
typedef struct tree treenode;     /* 树的结构新型态     */
typedef treenode *btree;          /* 宣告树节点指标型态 */

/* ---------------------------------------- */
/*  插入二叉树的节点                        */
/* ---------------------------------------- */
btree insertnode(btree root,int value)
{

   btree newnode;                 /* 树根指标           */
   btree current;                 /* 目前树节点指标     */
   btree back;                    /* 父节点指标         */

   /* 建立新节点记忆体 */
   newnode = ( btree ) malloc(sizeof(treenode));
   newnode->data = value;         /* 建立节点内容       */
   newnode->left = NULL;          /* 设定指标初值       */
   newnode->right = NULL;         /* 设定指标初值       */
   if ( root == NULL )            /* 是否是根节点       */
   {
      return newnode;             /* 传回新节点位置     */
   }
   else
   {
      current = root;             /* 保留目前树指标     */
      while ( current != NULL )
      {
         back = current;          /* 保留父节点指标     */
         if ( current->data > value )    /* 比较节点值  */
            current = current->left;     /* 左子树      */
         else
            current = current->right;    /* 右子树      */
      }
      if ( back->data > value )   /* 接起父子的链结     */
         back->left = newnode;    /* 左子树             */
      else
         back->right = newnode;   /* 右子树             */
   }
   return root;                   /* 传回树根指标       */
}

/* ---------------------------------------- */
/*  建立二叉树                              */
/* ---------------------------------------- */
btree createbtree(int *data,int len)
{
   btree root = NULL;             /* 树根指标           */
   int i;

   for ( i = 0; i < len; i++ )    /* 用回路建立树状结构 */
      root = insertnode(root,data[i]);
   return root;
}

/* ---------------------------------------- */
/*  二叉树后序遍历                          */
/* ---------------------------------------- */
void postorder(btree ptr)
{
   if ( ptr != NULL )             /* 终止条件           */
   {
      postorder(ptr->left);       /* 左子树             */
      postorder(ptr->right);      /* 右子树             */
      printf("[%2d]\n",ptr->data);  /* 列印节点内容     */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立二叉树且用后序遍历列印出来. */
/* ---------------------------------------- */
void main()
{
   btree root = NULL;             /* 树根指标           */

   /* 二叉树节点数据 */
   int data[9] = { 5, 6, 4, 8, 2, 3, 7, 1, 9 };
   root = createbtree(data,9);    /* 建立二叉树         */
   printf("树的节点内容 \n");
   postorder(root);               /* 后序遍历二叉树     */
}

转自：山海网络[/code:1]
回复

使用道具 举报

ShiChao
发表于 2003-5-26 14:03:43 | 显示全部楼层
头一次看到C语言的
回复

使用道具 举报

flyaway
发表于 2003-5-26 18:20:23 | 显示全部楼层
自打学的时候，就不知道再哪能用得到？能不能给个具体点的例子？
回复

使用道具 举报

sjinny
发表于 2003-5-26 22:05:27 | 显示全部楼层
我现在更需要图的遍历方法，用OOP，而且要是能遍历任意结构的图的万能算法！！
我没想到什么方法！！
回复

使用道具 举报

sailer
发表于 2003-5-28 09:49:02 | 显示全部楼层
http://ourbbs.8800.org/viewtopic.php?t=2094&sid=b4dfff36d4be4a75df12f7afa2ce01a1

这是完全由我自己写的二叉树的操作
回复

使用道具 举报

ShiChao
发表于 2003-5-29 11:21:47 | 显示全部楼层
[quote:eeb219adb9="sjinny"]我现在更需要图的遍历方法，用OOP，而且要是能遍历任意结构的图的万能算法！！
我没想到什么方法！！ [/quote]

把遍历过的标记出来，避免死循环
然后就是地跪调用了
回复

使用道具 举报

moonsky
 楼主| 发表于 2003-5-30 09:20:23 | 显示全部楼层
To sailer:
把你的程序也贴过来吧，大家对比参考一下了。
回复

使用道具 举报

atfa
发表于 2003-5-30 11:13:56 | 显示全部楼层
[code:1]
数据结构之二叉排序树（前/中/后序的递归、非递归）

发表于: 星期三 四月 09, 2003 21:55    发表主题: 数据结构之二叉排序树（前/中/后序的递归、非递归）        
一本参考书看到有比较完整的二叉排序树的程序，把它拿来放在linux下运行，出现Ｎ多错误，只能想办法改。改过的程序目前还不能运行，提示“段错误”。
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct bnode * Position;
typedef struct bnode {
　　　　ElementType data;
　　　　Position left, right;
} btree;

void preorder(Position temp)
{
　　　　printf("&&& In preorder, b = %x, b->left = %x, b->right = %x\n", temp, temp->left, temp->right);
　　　　if (temp != NULL) {
　　　　　　　　printf("&&& b->data = %d\n", temp->data);
　　　　　　　　preorder(temp->left);
　　　　　　　　preorder(temp->right);
　　　　}
}


void insert(Position b, Position s)
{
　　　　printf("### In insert() start, s->data = %d, s = %x, s->left = %x, s->right = %x\n", s->data, s, s->left, s->right);
　　　　if (b == NULL) {
　　　　　　　　b = s;
　　　　} else if (s->data == b->data) {
　　　　} else if (s->data < b->data) {
　　　　　　　　insert(b->left, s);
　　　　} else if (s->data > b->data) {
　　　　　　　　insert(b->right, s);
　　　　}
　　　　printf("### In insert() stop, b->data =%d, b = %x, b->left = %x, b->right = %x\n", b->data, b, b->left, b->right);
}

void create(Position b)
{
　　　　int x;
　　　　Position s;

　　　　do {
　　　　　　　?canf("%d", &x);
　　　　　　　　s = (btree *)malloc(sizeof(btree));
　　　　　　　　s->data = x;
　　　　　　　　s->left = (btree *)malloc(sizeof(btree));
　　　　　　　　s->right = (btree *)malloc(sizeof(btree));
　　　　　　　　printf("@@@ In create(), x = %d, s->data = %d, s = %x, s->left = %x, s->right = %x\n", x, s->data, s, s->left, s->right);
　　　　　　　　insert(b, s);
　　　　　　　　printf("@@@ In create(), after insert(), b = %x\n", b);
　　　　　　　　//preorder(b);
　　　　} while (x != -1);
}


int main(void)
{
　　　　Position tree, TREE;
　　　　int x;

　　　　scanf("%d", &x);
　　　　tree = (btree *)malloc(sizeof(btree));
　　　　TREE= tree;
　　　　tree->left = tree->right = NULL;
　　　　create(tree);
　　　　printf("+++ In main(), before preorder(), tree = %x\n", tree);
　　　　preorder(TREE);

　　　　return 0;
}

程序运行结果如下：
1
2
@@@ In create(), x = 2, s->data = 2, s = 8049978, s->left = 8049988, s->right = 8049998
### In insert() start, s->data = 2, s = 8049978, s->left = 8049988, s->right = 8049998
### In insert() start, s->data = 2, s = 8049978, s->left = 8049988, s->right = 8049998
### In insert() stop, b->data =2, b = 8049978, b->left = 8049988, b->right = 8049998
### In insert() stop, b->data =0, b = 8049968, b->left = 0, b->right = 0
@@@ In create(), after insert(), b = 8049968
3
@@@ In create(), x = 3, s->data = 3, s = 80499a8, s->left = 80499b8, s->right = 80499c8
### In insert() start, s->data = 3, s = 80499a8, s->left = 80499b8, s->right = 80499c8
### In insert() start, s->data = 3, s = 80499a8, s->left = 80499b8, s->right = 80499c8
### In insert() stop, b->data =3, b = 80499a8, b->left = 80499b8, b->right = 80499c8
### In insert() stop, b->data =0, b = 8049968, b->left = 0, b->right = 0
@@@ In create(), after insert(), b = 8049968
-1
@@@ In create(), x = -1, s->data = -1, s = 80499d8, s->left = 80499e8, s->right = 80499f8
### In insert() start, s->data = -1, s = 80499d8, s->left = 80499e8, s->right = 80499f8
### In insert() start, s->data = -1, s = 80499d8, s->left = 80499e8, s->right = 80499f8
### In insert() stop, b->data =-1, b = 80499d8, b->left = 80499e8, b->right = 80499f8
### In insert() stop, b->data =0, b = 8049968, b->left = 0, b->right = 0
@@@ In create(), after insert(), b = 8049968
+++ In main(), before preorder(), tree = 8049968
&&& In preorder, b = 8049968, b->left = 0, b->right = 0
&&& b->data = 0
Segmentation fault





程序做了修改，前面“段错误”的原因是函数访问结点的左、右孩子，而这些孩子为空结点，这也是指针使用的错误。
现在输出的二叉树还是有问题。
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct bnode * Position;
typedef struct bnode {
　　　　ElementType data;
　　　　Position left, right;
} btree;

void preorder(Position temp)
{
　　　　if (temp != NULL) {
　　　　　　　　if (temp->left != NULL) {
　　　　　　　　　　　　preorder(temp->left);
　　　　　　　　}
　　　　　　　　if (temp->right != NULL) {
　　　　　　　　　　　　preorder(temp->right);
　　　　　　　　}
　　　　}
}

void insert(Position b, Position s)
{
　　　　if (b == NULL) {
　　　　　　　　b = s;
　　　　} else if (s->data == b->data) {
　　　　} else if (s->data < b->data) {
　　　　　　　　if (b->left != NULL) {
　　　　　　　　　　　　insert(b->left, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->left = s;
　　　　　　　　}
　　　　} else if (s->data > b->data) {
　　　　　　　　if (b->right != NULL) {
　　　　　　　　　　　　insert(b->right, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->right = s;
　　　　　　　　}
　　　　}
}

void create(Position b)
{
　　　　int x;
　　　　Position s;

　　　　do {
　　　　　　　　scanf("%d", &x);
　　　　　　　　s = (btree *)malloc(sizeof(btree));
　　　　　　　　s->data = x;
　　　　　　　　s->left = (btree *)malloc(sizeof(btree));
　　　　　　　　s->right = (btree *)malloc(sizeof(btree));
　　　　　　　　insert(b, s);
　　　　} while (x != -1);
}

int main(void)
{
　　　　Position tree;
　　　　int x;

　　　　scanf("%d", &x);
　　　　tree = (btree *)malloc(sizeof(btree));
　　　　tree->data = x;
　　　　tree->left = (btree *)malloc(sizeof(btree));
　　　　tree->right = (btree *)malloc(sizeof(btree));
　　　　create(tree);
　　　　preorder(tree);

　　　　return 0;
}

输出结果：
linux:~/f0203/arithmetic/tree # ./sortbt
1
2
3
4
-1
&&& b->data = 1, b = 8049758, b->left = 8049768, b->right = 8049778
&&& b->data = 0, b = 8049768, b->left = 8049818, b->right = 0
&&& b->data = -1, b = 8049818, b->left = 8049828, b->right = 8049838
&&& b->data = 0, b = 8049828, b->left = 0, b->right = 0
&&& b->data = 0, b = 8049838, b->left = 0, b->right = 0
&&& b->data = 0, b = 8049778, b->left = 0, b->right = 8049788
&&& b->data = 2, b = 8049788, b->left = 8049798, b->right = 80497a8
&&& b->data = 0, b = 8049798, b->left = 0, b->right = 0
&&& b->data = 0, b = 80497a8, b->left = 0, b->right = 80497b8
&&& b->data = 3, b = 80497b8, b->left = 80497c8, b->right = 80497d8
&&& b->data = 0, b = 80497c8, b->left = 0, b->right = 0
&&& b->data = 0, b = 80497d8, b->left = 0, b->right = 80497e8
&&& b->data = 4, b = 80497e8, b->left = 80497f8, b->right = 8049808
&&& b->data = 0, b = 80497f8, b->left = 0, b->right = 0
&&& b->data = 0, b = 8049808, b->left = 0, b->right = 0

_________________
笨

（我QQ在线状态）

最后进行编辑的是 sailer on 星期六 四月 12, 2003 22:58, 总计第 4 次编辑
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期三 四月 09, 2003 22:07    发表主题:        
发现上面问题所在，又做了修改。输出的二叉树比上面的有进步，但还不完全正确，还是存在多余的树叶。
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct bnode * Position;
typedef struct bnode {
　　　　ElementType data;
　　　　Position left, right;
} btree;

void preorder(Position temp)
{
　　　　if (temp != NULL) {
　　　　　　　　printf("&&& b->data = %d, b = %x, b->left = %x, b->right = %x\n", temp->data, temp, temp->left, temp->right);
　　　　　　　　if (temp->left != NULL) {
　　　　　　　　　　　　preorder(temp->left);
　　　　　　　　}
　　　　　　　　if (temp->right != NULL) {
　　　　　　　　　　　　preorder(temp->right);
　　　　　　　　}
　　　　}
}

void insert(Position b, Position s)
{
　　　　if (b == NULL) {
　　　　　　　　b = s;
　　　　} else if (s->data == b->data) {
　　　　} else if (s->data < b->data) {
　　　　　　　　if (b->left->left != NULL) {
　　　　　　　　　　　　insert(b->left, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->left = s;
　　　　　　　　}
　　　　} else if (s->data > b->data) {
　　　　　　　　if (b->right->left != NULL) {
　　　　　　　　　　　　insert(b->right, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->right = s;
　　　　　　　　}
　　　　}
}

void create(Position b)
{
　　　　int x;
　　　　Position s;

　　　　do {
　　　　　　　　scanf("%d", &x);
　　　　　　　　s = (btree *)malloc(sizeof(btree));
　　　　　　　　s->data = x;
　　　　　　　　s->left = (btree *)malloc(sizeof(btree));
　　　　　　　　s->left->left = s->left->right = NULL;
　　　　　　　　s->right = (btree *)malloc(sizeof(btree));
　　　　　　　　s->right->left = s->right->right = NULL;
　　　　　　　　insert(b, s);
　　　　} while (x != -1);
}

int main(void)
{
　　　　Position tree;
　　　　int x;

　　　　scanf("%d", &x);
　　　　tree = (btree *)malloc(sizeof(btree));
　　　　tree->data = x;
　　　　tree->left = (btree *)malloc(sizeof(btree));
　　　　tree->left->left = tree->left->right = NULL;
　　　　tree->right = (btree *)malloc(sizeof(btree));;
　　　　tree->right->left = tree->right->right = NULL;
　　　　create(tree);
　　　　preorder(tree);

　　　　return 0;
}

程序输出：
linux:~/f0203/arithmetic/tree # ./sortbt
1
2
3
4
-1
&&& b->data = 1, b = 80497d8, b->left = 8049898, b->right = 8049808
&&& b->data = -1, b = 8049898, b->left = 80498a8, b->right = 80498b8
&&& b->data = 0, b = 80498a8, b->left = 0, b->right = 0
&&& b->data = 0, b = 80498b8, b->left = 0, b->right = 0
&&& b->data = 2, b = 8049808, b->left = 8049818, b->right = 8049838
&&& b->data = 0, b = 8049818, b->left = 0, b->right = 0
&&& b->data = 3, b = 8049838, b->left = 8049848, b->right = 8049868
&&& b->data = 0, b = 8049848, b->left = 0, b->right = 0
&&& b->data = 4, b = 8049868, b->left = 8049878, b->right = 8049888
&&& b->data = 0, b = 8049878, b->left = 0, b->right = 0
&&& b->data = 0, b = 8049888, b->left = 0, b->right = 0
_________________
笨

（我QQ在线状态）

最后进行编辑的是 sailer on 星期三 四月 09, 2003 22:26, 总计第 1 次编辑
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期三 四月 09, 2003 22:18    发表主题:        
我kao,程序终于改好（/me 吃菠罗ing）。输出的二叉树正确了，前面两个贴子里为结点的左、右孩子分配内存空间的做法是错误的，只要在第一个贴子里程序的基础上在insert()函数里增加一个左、右孩子是否为空的判断就可以了。明天争取把插入和删除的函数写出来。
#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;

typedef struct bnode * Position;
typedef struct bnode {
　　　　ElementType data;
　　　　Position left, right;
} btree;

void preorder(Position temp)
{
　　　　if (temp != NULL) {
　　　　　　　　printf("&&& b->data = %d, b = %x, b->left = %x, b->right = %x\n", temp->data, temp, temp->left, temp->right);
　　　　　　　　if (temp->left != NULL) {
　　　　　　　　　　　　preorder(temp->left);
　　　　　　　　}
　　　　　　　　if (temp->right != NULL) {
　　　　　　　　　　　　preorder(temp->right);
　　　　　　　　}
　　　　}
}


void insert(Position b, Position s)
{
　　　　if (b == NULL) {
　　　　　　　　b = s;
　　　　} else if (s->data == b->data) {
　　　　} else if (s->data < b->data) {
　　　　　　　　if (b->left != NULL) {
　　　　　　　　　　　　insert(b->left, s);　/*把小于结点b的结点s插入到b的左子树*/
　　　　　　　　} else {
　　　　　　　　　　　　b->left = s;
　　　　　　　　}
　　　　} else if (s->data > b->data) {
　　　　　　　　if (b->right != NULL) {
　　　　　　　　　　　　insert(b->right, s);　/*把大于结点b的结点s插入到b的右子树*/
　　　　　　　　} else {
　　　　　　　　　　　　b->right = s;
　　　　　　　　}
　　　　}
}

void create(Position b)
{
　　　　int x;
　　　　Position s;

　　　　do {
　　　　　　　　scanf("%d", &x);
　　　　　　　　s = (btree *)malloc(sizeof(btree));
　　　　　　　　s->data = x;
　　　　　　　　insert(b, s);
　　　　} while (x != -1);
}


int main(void)
{
　　　　Position tree;
　　　　int x;

　　　　scanf("%d", &x);
　　　　tree = (btree *)malloc(sizeof(btree));
　　　　tree->data = x;　　/*在main()里输入第一个元素的值，目的是给tree初始化，也就是使tree指针在被create()函数调用前，明确的指向某个内存地址（因为未初始化的指针被函数调用会产生不可预料的后果）。这里还可以增加以一个判断，当输入“-1”时程序退出运行。 */
　　　　create(tree);
　　　　preorder(tree);

　　　　return 0;
}

程序手工输入：
linux:~/f0203/arithmetic/tree # ./sortbt
1
2
3
4
-1
程序输出：
&&& b->data = 1, b = 8049718, b->left = 8049758, b->right = 8049728
&&& b->data = -1, b = 8049758, b->left = 0, b->right = 0
&&& b->data = 2, b = 8049728, b->left = 0, b->right = 8049738
&&& b->data = 3, b = 8049738, b->left = 0, b->right = 8049748
&&& b->data = 4, b = 8049748, b->left = 0, b->right = 0

_________________
笨

（我QQ在线状态）
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期四 四月 10, 2003 15:40    发表主题:        
上面程序里的前序遍历使用递归过程，刚才增加了非递归过程的前序遍历，函数名是PreorderNoRecursion(BTreePos tree)（程序中粗体部分）。以书上第144页算法4.3为参考，本来想得很简单，把这段程序抄一下，再略改动就可以了，结果运行、调试的时候才发现这段程序有N多的细节都没考虑到，结果在这个函数里不是“段错误”就是进入死循环。为了使这个函数能正常运行，在程序里增加了堆栈的代码，在树的结点里增加了指向父结点的parent指针。
另书上这段代码里“Push(NULL, S)”这行代码在C语言下是完完全全的指针使用错误的。我也没看出来这行代码起什么作用。

#include <stdio.h>
#include <stdlib.h>

#define new(type) (type *)malloc(sizeof(type));

typedef int Element;

typedef struct bnode *BTreePos;
typedef struct bnode {
　　　　Element data;
　　　　BTreePos parent, left, right;
} btree;

typedef struct cell *StackPos;
typedef struct cell {
　　　　Element data;
　　　　BTreePos parent, left, right;
　　　　StackPos next;
} Cell;
typedef struct stack {
　　　　StackPos top;
} Stack;

enum StackError { None, StackIsEmpty, StackUnderflow, StackOverflow };
enum StackError SErr;


void CreateStack(Stack * S)
{
　　　　S->top = new(Cell);
　　　　S->top->parent = NULL;
　　　　SErr = None;
}

void Push(BTreePos p, Stack * S)
{
　　　　StackPos q;

　　　　q = new(Cell);
　　　　q->data = p->data;
　　　　q->left = p->left;
　　　　q->right = p->right;
　　　　q->parent = p->parent;
　　　　q->next = S->top;
　　　　S->top = q;
}

void Pop(BTreePos p, Stack * S)
{
　　　　StackPos q, s;

　　　　if (S->top == NULL) {
　　　　　　　　SErr = StackUnderflow;
　　　　} else {
　　　　　　　　s = S->top;
　　　　　　　　p->data = s->data;
　　　　　　　　p->left = s->left;
　　　　　　　　p->right = s->right;
　　　　　　　　p->parent = s->parent;
　　　　　　　　q = S->top;
　　　　　　　　S->top = s->next;
　　　　　　　　free(q);
　　　　}
}

void Preorder(BTreePos tree)　/*归递前序*/
{
　　　　if (tree != NULL) {
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 tree->data, tree, tree->left, tree->right);
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　Preorder(tree->left);
　　　　　　　　}
　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　Preorder(tree->right);
　　　　　　　　}
　　　　}
}

void PreorderNoRecursion(BTreePos tree)　/*非归递前序*/
{
　　　　Stack *temp;

　　　　CreateStack(temp);
　　　　while (tree) {
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 tree->data, tree, tree->left, tree->right);
　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　Push(tree->right, temp);
　　　　　　　　}
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　tree = tree->left;
　　　　　　　　} else if (temp->top->parent != NULL) {
　　　　　　　　　　　　Pop(tree, temp);
　　　　　　　　　　　　tree->parent->right = tree;
　　　　　　　　} else {
　　　　　　　　　　　　break;
　　　　　　　　}
　　　　}
}

void Insert(BTreePos b, BTreePos s)
{
　　　　if (b == NULL) {
　　　　　　　　b = s;
　　　　} else if (s->data == b->data) {
　　　　} else if (s->data < b->data) {
　　　　　　　　if (b->left != NULL) {
　　　　　　　　　　　　Insert(b->left, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->left = s;
　　　　　　　　　　　　s->parent = b;
　　　　　　　　}
　　　　} else if (s->data > b->data) {
　　　　　　　　if (b->right != NULL) {
　　　　　　　　　　　　Insert(b->right, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->right = s;
　　　　　　　　　　　　s->parent = b;
　　　　　　　　}
　　　　}
}

void CreateBTree(BTreePos b)
{
　　　　int x;
　　　　BTreePos s;

　　　　do {
　　　　　　　　scanf("%d", &x);
　　　　　　　　s = (btree *) malloc(sizeof(btree));
　　　　　　　　s->parent = s->left = s->right = NULL;
　　　　　　　　s->data = x;
　　　　　　　　Insert(b, s);
　　　　} while (x != -1);
}

int main(void)
{
　　　　BTreePos tree;
　　　　int x;

　　　　scanf("%d", &x);
　　　　tree = (btree *) malloc(sizeof(btree));
　　　　tree->parent = tree->left = tree->right = NULL;
　　　　printf("In main(), tree->left = %x, tree->right = %x\n", tree->left, tree->right);
　　　　tree->data = x;
　　　　CreateBTree(tree);

　　　　printf("Use Preorder with recursion :\n");
　　　　Preorder(tree);

　　　　printf("Use Preorder with no recursion :\n");
　　　　PreorderNoRecursion(tree);
　　　　return 0;
}

手工输入：
1
2
3
4
-1
程序输出：
Use Preorder with recursion :
&&& tree->data = 1, tree = 80499e8, tree->left = 8049a48, tree->right = 8049a00
&&& tree->data = -1, tree = 8049a48, tree->left = 0, tree->right = 0
&&& tree->data = 2, tree = 8049a00, tree->left = 0, tree->right = 8049a18
&&& tree->data = 3, tree = 8049a18, tree->left = 0, tree->right = 8049a30
&&& tree->data = 4, tree = 8049a30, tree->left = 0, tree->right = 0
Use Preorder with no recursion :
&&& tree->data = 1, tree = 80499e8, tree->left = 8049a48, tree->right = 8049a00
&&& tree->data = -1, tree = 8049a48, tree->left = 0, tree->right = 0
&&& tree->data = 2, tree = 8049a48, tree->left = 0, tree->right = 8049a18
&&& tree->data = 3, tree = 8049a48, tree->left = 0, tree->right = 8049a30
&&& tree->data = 4, tree = 8049a48, tree->left = 0, tree->right = 0


十一点半了，睡觉。
_________________
笨

（我QQ在线状态）
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期五 四月 11, 2003 15:00    发表主题:        
中序遍历的递归函数已经完成：

void InorderRecursion(BTreePos irtree)
{
　　　　if (irtree != NULL) {
　　　　　　　　if (irtree->left != NULL) {
　　　　　　　　　　　　InorderRecursion(irtree->left);
　　　　　　　　}
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 irtree->data, irtree, irtree->left, irtree->right);
　　　　　　　　if (irtree->right != NULL) {
　　　　　　　　　　　　InorderRecursion(irtree->right);
　　　　　　　　}
　　　　}
}

Add the line in main():
　　　　printf("Use Inorder with recursion :\n");
　　　　InorderRecursion(tree);

The result:
30
45
40
65
60
70
50
100
150
140
160
-1
Use Inorder with recursion :
&&& tree->data = -1, tree = 8049dd0, tree->left = 0, tree->right = 0
&&& tree->data = 30, tree = 8049cc8, tree->left = 8049dd0, tree->right = 8049ce0
&&& tree->data = 40, tree = 8049cf8, tree->left = 0, tree->right = 0
&&& tree->data = 45, tree = 8049ce0, tree->left = 8049cf8, tree->right = 8049d10
&&& tree->data = 50, tree = 8049d58, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 8049d28, tree->left = 8049d58, tree->right = 0
&&& tree->data = 65, tree = 8049d10, tree->left = 8049d28, tree->right = 8049d40
&&& tree->data = 70, tree = 8049d40, tree->left = 0, tree->right = 8049d70
&&& tree->data = 100, tree = 8049d70, tree->left = 0, tree->right = 8049d88
&&& tree->data = 140, tree = 8049da0, tree->left = 0, tree->right = 0
&&& tree->data = 150, tree = 8049d88, tree->left = 8049da0, tree->right = 8049db8
&&& tree->data = 160, tree = 8049db8, tree->left = 0, tree->right = 0

中序的非递归函数还有错误，好像写得太复杂了：
void InorderNoRecursion(BTreePos tree)
{
　　　　BTreePos topnode;
　　　　Stack temp;

　　　　topnode = tree;
　　　　CreateStack(&temp);
　　　　while (tree) {
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　Push(tree, &temp);
　　　　　　　　　　　　tree = tree->left;
　　　　　　　　} else {
　　　　　　　　　　　　printf
　　　　　　　　　　　　　　("1. &&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　　　　　 tree->data, tree, tree->left, tree->right);
　　　　　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else if (temp.top != NULL) {
　　　　　　　　　　　　　　　　Pop(tree, &temp);
　　　　　　　　　　　　　　　　if (tree != topnode) {
　　　　　　　　　　　　　　　　　　　　tree->parent->left = tree;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　printf("2. &&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n", tree->data, tree, tree->left, tree->right);
　　　　　　　　　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　} else if (tree->right != NULL) {
　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}
用上面输入的1、2、3、4、-1，输出没有错误。如果输入比较复杂的话，输出就不对了。



我kao，花了三个多小时终于把中序的非递归写好了。
在堆栈的结果里增加了一个BTreePos addr指针，在Push()里把它指向被压入的结点的地址。这样被Pop()的结点仍然能够放在原来的内存位置上。
last变量是最后弹出的结点的数值，printed变量是最后显示的结果的数值，它用于判断结点是否被显示过，如果打印过，则不再做第二次显示（如果没有这个判断，中序递归函数的输出中“60”结点被显示两次）。

void InorderNoRecursion(BTreePos tree)
{
　　　　BTreePos topnode;
　　　　Stack temp;
　　　　int last = -1, printed = -1;

　　　　topnode = tree; 　/*根结点赋给topnode指针，后面做判断用*/
　　　　CreateStack(&temp);
　　　　while (tree) {
　　　　　　　　if (tree->left != NULL && tree->data != last) {　/*当前结点的左子树不空，且不是最近Pop()出来的结点 */
　　　　　　　　　　　　Push(tree, &temp);
　　　　　　　　　　　　tree = tree->left; 　/*当前结点指向左子树*/
　　　　　　　　} else {
　　　　　　　　　　　　if (printed != tree->data) {　/*如果当前结点没有显示过*/
　　　　　　　　　　　　　　　　printf("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n", tree->data, tree, tree->left, tree->right);
　　　　　　　　　　　　}
　　　　　　　　　　　　if (tree->right != NULL) {　/*当前结点的右子树不空*/
　　　　　　　　　　　　　　　　tree = tree->right; 　/*当前结点指向右子树*/
　　　　　　　　　　　　　　　　continue; 　/*继续下一次while循环*/
　　　　　　　　　　　　} else if (temp.top != NULL) {　/*栈顶不空，即栈内还有结点*/
　　　　　　　　　　　　　　　　Pop(tree->parent, &temp); 　/*当前结点的父结点指向被Pop()出来的结点*/
　　　　　　　　　　　　　　　　tree = tree->parent; 　/*当前结点指向父结点*/
　　　　　　　　　　　　　　　　last = tree->data; 　/*把Pop()出来结点的数值赋给last变量*/
　　　　　　　　　　　　　　　　if (tree != topnode) {　/*当前结点不是根结点*/
　　　　　　　　　　　　　　　　　　　　tree->parent->left = tree; 　/*把当前结点的父结点的左子树指向当前结点，使Pop()以后的结点之间保持原有的连接*/
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　printf("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n", tree->data, tree, tree->left, tree->right);
　　　　　　　　　　　　　　　　printed = tree->data; 　/*把刚显示过的结点的数值赋给printed变量*/
　　　　　　　　　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}

另CreateBTree()函数做了修改，输入“-1”就退出，即“-1”本身不再被插入到树中，它只做为输入结点的结束（这样做也方便了InorderNoRecursion()和其他函数中给last和printed变量赋初值）。
void CreateBTree(BTreePos b)
{
　　　　int x;
　　　　BTreePos s;

　　　　do {
　　　　　　　　scanf("%d", &x);
　　　　　　　　if (x == -1) {
　　　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　s = (btree *) malloc(sizeof(btree));
　　　　　　　　s->parent = s->left = s->right = NULL;
　　　　　　　　s->data = x;
　　　　　　　　Insert(b, s);
　　　　} while (x != -1);
}
_________________
笨

（我QQ在线状态）

最后进行编辑的是 sailer on 星期六 四月 12, 2003 15:00, 总计第 2 次编辑
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期六 四月 12, 2003 14:40    发表主题:        
后序遍历的递归过程：
三个遍历过的递归过程的程序都很简单，只是显示结点的printf语句位置不同。

void PostorderRecursion(BTreePos tree)
{
　　　　if (tree != NULL) {
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　PostorderRecursion(tree->left);
　　　　　　　　}
　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　PostorderRecursion(tree->right);
　　　　　　　　}
　　　　　　　　printf("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n", tree->data, tree, tree->left, tree->right);
　　　　}
}


函数结果：
30
45
40
65
60
70
50
100
150
140
160
-1
Use postorder with recursion :
&&& tree->data = 40, tree = 8049bd0, tree->left = 0, tree->right = 0
&&& tree->data = 50, tree = 8049c30, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 8049c00, tree->left = 8049c30, tree->right = 0
&&& tree->data = 140, tree = 8049c78, tree->left = 0, tree->right = 0
&&& tree->data = 160, tree = 8049c90, tree->left = 0, tree->right = 0
&&& tree->data = 150, tree = 8049c60, tree->left = 8049c78, tree->right = 8049c90
&&& tree->data = 100, tree = 8049c48, tree->left = 0, tree->right = 8049c60
&&& tree->data = 70, tree = 8049c18, tree->left = 0, tree->right = 8049c48
&&& tree->data = 65, tree = 8049be8, tree->left = 8049c00, tree->right = 8049c18
&&& tree->data = 45, tree = 8049bb8, tree->left = 8049bd0, tree->right = 8049be8
&&& tree->data = 30, tree = 8049ba0, tree->left = 0, tree->right = 8049bb8


后序遍历的非递归过程：
写程序以前，花了半个小时想算法，并用文字表达出来：
从根开始：
左子树不为空且没显示过？
是：进栈，下左子树。
否：
　　1..右子树不为空且右子树没显示过？
　　是，当前结点进栈，进入右子树，继续。
　　否，显示，如果当前结点不是根结点。
　　　　是，弹出并指向父结点，继续。
　　　　否，退出循环。


用一棵树模拟下来没什么问题，接下来写程序。
用文字描述算法很简单，但是写起来不容易，为了判断左子是否显示过，不得不使用了一个单链线性表来存储已经显示过的左子树结点，程序变得更复杂了。

void PostorderNoRecursion(BTreePos tree)
{
　　　　BTreePos topnode;
　　　　Stack temp;
　　　　Line templine;
　　　　int rightprinted = -1;

　　　　topnode = tree;
　　　　CreateStack(&temp);
　　　　CreateLine(&templine);

　　　　while (tree) {
　　　　　　　　if (tree->left != NULL && !FindInLine(tree->left->data, &templine)) {
　　　　　　　　　　　　Push(tree, &temp);
　　　　　　　　　　　　tree = tree->left;
　　　　　　　　} else {
　　　　　　　　　　　　if ((tree->right != NULL) && (tree->right->data != rightprinted)) {
　　　　　　　　　　　　　　　　Push(tree, &temp);
　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　printf("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n", tree->data, tree, tree->left, tree->right);
　　　　　　　　　　　　　　　　if (tree == tree->parent->left) {
　　　　　　　　　　　　　　　　　　　　InsertToLine(tree->data, &templine);
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　if (tree == tree->parent->right) {
　　　　　　　　　　　　　　　　　　　　rightprinted = tree->data;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　if (tree != topnode) {
　　　　　　　　　　　　　　　　　　　　Pop(tree->parent, &temp);
　　　　　　　　　　　　　　　　　　　　tree = tree->parent;
　　　　　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}

程序运行结果：
30
45
40
65
60
70
50
100
150
140
160
-1
Use Postorder with no recursion :
&&& tree->data = 40, tree = 8049bd8, tree->left = 0, tree->right = 0
&&& tree->data = 50, tree = 8049c38, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 8049c08, tree->left = 8049c38, tree->right = 0
&&& tree->data = 140, tree = 8049c80, tree->left = 0, tree->right = 0
&&& tree->data = 160, tree = 8049c98, tree->left = 0, tree->right = 0
&&& tree->data = 150, tree = 8049c68, tree->left = 8049c80, tree->right = 8049c98
&&& tree->data = 100, tree = 8049c50, tree->left = 0, tree->right = 8049c68
&&& tree->data = 70, tree = 8049c20, tree->left = 0, tree->right = 8049c50
&&& tree->data = 65, tree = 8049bf0, tree->left = 8049c08, tree->right = 8049c20
&&& tree->data = 45, tree = 8049bc0, tree->left = 8049bd8, tree->right = 8049bf0
&&& tree->data = 30, tree = 8049ba8, tree->left = 0, tree->right = 8049bc0

_________________
笨

（我QQ在线状态）
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期一 四月 14, 2003 15:38    发表主题:        
在程序中分别调试前、中、序都是正确的，但是没料到把六个函数放在一起，输出就不正确了。
The whole program:

#include <stdio.h>
#include <stdlib.h>

#define new(type) (type *)malloc(sizeof(type));

typedef int Element;

typedef struct bnode *BTreePos;
typedef struct bnode {
　　　　Element data;
　　　　BTreePos parent, left, right;
} btree;

typedef struct cell *StackPos;
typedef struct cell {
　　　　Element data;
　　　　BTreePos parent, left, right, addr;
　　　　StackPos next;
} Cell;
typedef struct stack {
　　　　StackPos top;
} Stack;

typedef struct lefttree *LTPos;
typedef struct lefttree {
　　　　Element data;
　　　　LTPos next;
} LeftTree;
typedef struct line {
　　　　LTPos head;
} Line;

enum StackError { None, StackIsEmpty, StackUnderflow, StackOverflow };
enum StackError SErr;


void CreateStack(Stack * S)
{
　　　　S->top = NULL;
　　　　//S->top->parent = NULL;
　　　　SErr = None;
}

void Push(BTreePos p, Stack * S)
{
　　　　StackPos q;

　　　　q = new(Cell);
　　　　q->data = p->data;
　　　　q->left = p->left;
　　　　q->right = p->right;
　　　　q->parent = p->parent;
　　　　q->addr = p;
　　　　q->next = S->top;
　　　　S->top = q;
}

void Pop(BTreePos p, Stack * S)
{
　　　　StackPos q, s;

　　　　if (S->top == NULL) {
　　　　　　　　SErr = StackUnderflow;
　　　　} else {
　　　　　　　　s = S->top;
　　　　　　　　p->data = s->data;
　　　　　　　　p->left = s->left;
　　　　　　　　p->right = s->right;
　　　　　　　　p->parent = s->parent;
　　　　　　　　p = s->addr;
　　　　　　　　q = S->top;
　　　　　　　　S->top = s->next;
　　　　　　　　free(q);
　　　　}
}

void CreateLine(Line * L)
{
　　　　L->head = NULL;
}

void InsertToLine(Element e, Line * L)
{
　　　　LTPos p, q;

　　　　if (L->head == NULL) {
　　　　　　　　L->head = new(LeftTree);
　　　　　　　　L->head->data = e;
　　　　　　　　L->head->next = NULL;
　　　　} else {
　　　　　　　　p = new(LeftTree);
　　　　　　　　p->data = e;
　　　　　　　　p->next = NULL;
　　　　　　　　q = L->head;
　　　　　　　　while (q->next != NULL) {
　　　　　　　　　　　　q = q->next;
　　　　　　　　}
　　　　　　　　q->next = p;
　　　　}
}

int FindInLine(Element e, Line *L)
{
　　　　LTPos p;
　　　　int found = 0;

　　　　p = L->head;
　　　　while (p != NULL) {
　　　　　　　　if (p->data == e) {
　　　　　　　　　　　　found = 1;
　　　　　　　　　　　　break;
　　　　　　　　} else {
　　　　　　　　　　　　p = p->next;
　　　　　　　　}
　　　　}
　　　　return (found);
}

void ListLine(Line *L)
{
　　　　LTPos p;

　　　　p = L->head;
　　　　while (p != NULL) {
　　　　　　　　printf("data = %d\n", p->data);
　　　　　　　　p = p->next;
　　　　}
}

void PreorderRecursion(BTreePos tree)
{
　　　　if (tree != NULL) {
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 tree->data, tree, tree->left, tree->right);
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　PreorderRecursion(tree->left);
　　　　　　　　}
　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　PreorderRecursion(tree->right);
　　　　　　　　}
　　　　}
}

void PreorderNoRecursion(BTreePos tree)
{
　　　　Stack temp1;

　　　　CreateStack(&temp1);
　　　　while (tree) {
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 tree->data, tree, tree->left, tree->right);
　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　Push(tree->right, &temp1);
　　　　　　　　}
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　tree = tree->left;
　　　　　　　　} else if (temp1.top != NULL) {
　　　　　　　　　　　　　　　　Pop(tree, &temp1);
　　　　　　　　} else {
　　　　　　　　　　　　break;
　　　　　　　　}
　　　　}
}

void InorderRecursion(BTreePos tree)
{
　　　　if (tree != NULL) {
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　InorderRecursion(tree->left);
　　　　　　　　}
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 tree->data, tree, tree->left, tree->right);
　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　InorderRecursion(tree->right);
　　　　　　　　}
　　　　}
}

void InorderNoRecursion(BTreePos tree)
{
　　　　BTreePos topnode;
　　　　Stack temp2;
　　　　int last = -1, printed = -1;

　　　　topnode = tree;
　　　　CreateStack(&temp2);
　　　　while (tree) {
　　　　　　　　if (tree->left != NULL && tree->data != last) {
　　　　　　　　　　　　Push(tree, &temp2);
　　　　　　　　　　　　tree = tree->left;
　　　　　　　　} else {
　　　　　　　　　　　　if (printed != tree->data) {
　　　　　　　　　　　　　　　　printf
　　　　　　　　　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　　　　　　　　　 tree->data, tree, tree->left,
　　　　　　　　　　　　　　　　　　 tree->right);
　　　　　　　　　　　　}
　　　　　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else if (temp2.top != NULL) {
　　　　　　　　　　　　　　　　Pop(tree->parent, &temp2);
　　　　　　　　　　　　　　　　tree = tree->parent;
　　　　　　　　　　　　　　　　last = tree->data;
　　　　　　　　　　　　　　　　if (tree != topnode) {
　　　　　　　　　　　　　　　　　　　　tree->parent->left = tree;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　printf
　　　　　　　　　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　　　　　　　　　 tree->data, tree, tree->left,
　　　　　　　　　　　　　　　　　　 tree->right);
　　　　　　　　　　　　　　　　printed = tree->data;
　　　　　　　　　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}

void PostorderRecursion(BTreePos tree)
{
　　　　if (tree != NULL) {
　　　　　　　　if (tree->left != NULL) {
　　　　　　　　　　　　PostorderRecursion(tree->left);
　　　　　　　　}
　　　　　　　　if (tree->right != NULL) {
　　　　　　　　　　　　PostorderRecursion(tree->right);
　　　　　　　　}
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 tree->data, tree, tree->left, tree->right);
　　　　}
}

void PostorderNoRecursion(BTreePos tree)
{
　　　　BTreePos topnode;
　　　　Stack temp3;
　　　　Line templine;
　　　　int rightprinted = -1;

　　　　topnode = tree;
　　　　CreateStack(&temp3);
　　　　CreateLine(&templine);

　　　　while (tree) {
　　　　　　　　if (tree->left != NULL && !FindInLine(tree->left->data, &templine)) {
　　　　　　　　　　　　Push(tree, &temp3);
　　　　　　　　　　　　tree = tree->left;
　　　　　　　　} else {
　　　　　　　　　　　　if ((tree->right != NULL) && (tree->right->data != rightprinted)) {
　　　　　　　　　　　　　　　　Push(tree, &temp3);
　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　printf("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n", tree->data, tree, tree->left, tree->right);
　　　　　　　　　　　　　　　　if (tree == tree->parent->left) {
　　　　　　　　　　　　　　　　　　　　InsertToLine(tree->data, &templine);
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　if (tree == tree->parent->right) {
　　　　　　　　　　　　　　　　　　　　rightprinted = tree->data;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　if (tree != topnode) {
　　　　　　　　　　　　　　　　　　　　Pop(tree->parent, &temp3);
　　　　　　　　　　　　　　　　　　　　tree = tree->parent;
　　　　　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}

void Insert(BTreePos b, BTreePos s)
{
　　　　if (b == NULL) {
　　　　　　　　b = s;
　　　　} else if (s->data == b->data) {
　　　　} else if (s->data < b->data) {
　　　　　　　　if (b->left != NULL) {
　　　　　　　　　　　　Insert(b->left, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->left = s;
　　　　　　　　　　　　s->parent = b;
　　　　　　　　}
　　　　} else if (s->data > b->data) {
　　　　　　　　if (b->right != NULL) {
　　　　　　　　　　　　Insert(b->right, s);
　　　　　　　　} else {
　　　　　　　　　　　　b->right = s;
　　　　　　　　　　　　s->parent = b;
　　　　　　　　}
　　　　}
}

void CreateBTree(BTreePos b)
{
　　　　int x;
　　　　BTreePos s;

　　　　do {
　　　　　　　　scanf("%d", &x);
　　　　　　　　if (x == -1) {
　　　　　　　　　　　　break;
　　　　　　　　}
　　　　　　　　s = (btree *) malloc(sizeof(btree));
　　　　　　　　s->parent = s->left = s->right = NULL;
　　　　　　　　s->data = x;
　　　　　　　　Insert(b, s);
　　　　} while (x != -1);
}


int main(void)
{
　　　　BTreePos tree;
　　　　int x;

　　　　scanf("%d", &x);
　　　　tree = (btree *) malloc(sizeof(btree));
　　　　tree->parent = tree;
　　　　tree->left = tree->right = NULL;
　　　　tree->data = x;
　　　　CreateBTree(tree);

　　　　printf("Use Preorder with recursion :\n");
　　　　PreorderRecursion(tree);
　　　　printf("Use Preorder with no recursion :\n");
　　　　PreorderNoRecursion(tree);
　　　　printf("Use Preorder with recursion :\n");
　　　　PreorderRecursion(tree);

　　　　printf("Use Inorder with recursion :\n");
　　　　InorderRecursion(tree);
　　　　printf("Use Inorder with no recursion :\n");
　　　　InorderNoRecursion(tree);

　　　　printf("Use Postorder with recursion :\n");
　　　　PostorderRecursion(tree);
　　　　printf("Use Postorder with no recursion :\n");
　　　　PostorderNoRecursion(tree);

　　　　return 0;
}


在做完前序非递归遍历以后，又做了一次前序递归遍历，发现结果不正确（粗体部分），少了好几个结点，把二叉树画出来，发现少的正好是第一个压入堆栈的结点以前的所有结点。
我在调试三个非递归函数的时候就注意到，每次Pop()操作的时候可能会把前一个结点覆盖掉，造成结点的丢失。我已经注意避免这个问题，但还是碰到了。
The result:
Use Preorder with recursion :
&&& tree->data = 30, tree = 8049f68, tree->left = 0, tree->right = 8049f80
&&& tree->data = 40, tree = 8049f80, tree->left = 0, tree->right = 8049f98
&&& tree->data = 45, tree = 8049f98, tree->left = 0, tree->right = 8049fb0
&&& tree->data = 65, tree = 8049fb0, tree->left = 8049fc8, tree->right = 8049fe0
&&& tree->data = 60, tree = 8049fc8, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 50, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 100, tree = 8049fe0, tree->left = 0, tree->right = 804a010
&&& tree->data = 140, tree = 804a010, tree->left = 0, tree->right = 804a028
&&& tree->data = 160, tree = 804a028, tree->left = 0, tree->right = 0
Use Preorder with no recursion :
&&& tree->data = 30, tree = 8049f68, tree->left = 0, tree->right = 8049f80
&&& tree->data = 40, tree = 8049f68, tree->left = 0, tree->right = 8049f98
&&& tree->data = 45, tree = 8049f68, tree->left = 0, tree->right = 8049fb0
&&& tree->data = 65, tree = 8049f68, tree->left = 8049fc8, tree->right = 8049fe0
&&& tree->data = 60, tree = 8049fc8, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 50, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 100, tree = 8049ff8, tree->left = 0, tree->right = 804a010
&&& tree->data = 140, tree = 8049ff8, tree->left = 0, tree->right = 804a028
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0

Use Preorder with recursion :
&&& tree->data = 65, tree = 8049f68, tree->left = 8049fc8, tree->right = 8049fe0
&&& tree->data = 60, tree = 8049fc8, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 100, tree = 8049fe0, tree->left = 0, tree->right = 804a010
&&& tree->data = 140, tree = 804a010, tree->left = 0, tree->right = 804a028
&&& tree->data = 160, tree = 804a028, tree->left = 0, tree->right = 0

Use Inorder with recursion :
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 8049fc8, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 65, tree = 8049f68, tree->left = 8049fc8, tree->right = 8049fe0
&&& tree->data = 100, tree = 8049fe0, tree->left = 0, tree->right = 804a010
&&& tree->data = 140, tree = 804a010, tree->left = 0, tree->right = 804a028
&&& tree->data = 160, tree = 804a028, tree->left = 0, tree->right = 0
Use Inorder with no recursion :
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 65, tree = 8049fb0, tree->left = 8049fc8, tree->right = 8049fe0
&&& tree->data = 100, tree = 8049fe0, tree->left = 0, tree->right = 804a010
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
Use Postorder with recursion :
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 8049fc8, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 100, tree = 8049fe0, tree->left = 0, tree->right = 804a010
&&& tree->data = 65, tree = 8049f68, tree->left = 8049fc8, tree->right = 8049fe0
Use Postorder with no recursion :
&&& tree->data = 160, tree = 8049ff8, tree->left = 0, tree->right = 0
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 100, tree = 8049fb0, tree->left = 0, tree->right = 804a010
&&& tree->data = 100, tree = 8049fe0, tree->left = 0, tree->right = 804a010
&&& tree->data = 65, tree = 8049fb0, tree->left = 8049fc8, tree->right = 8049fe0
&&& tree->data = 45, tree = 8049f98, tree->left = 8049fb0, tree->right = 8049fb0
&&& tree->data = 40, tree = 8049f80, tree->left = 0, tree->right = 8049f98
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 60, tree = 804a010, tree->left = 8049ff8, tree->right = 0
&&& tree->data = 100, tree = 8049fb0, tree->left = 0, tree->right = 804a010
&&& tree->data = 100, tree = 8049fe0, tree->left = 0, tree->right = 804a010
&&& tree->data = 65, tree = 8049fb0, tree->left = 8049fc8, tree->right = 8049fe0
&&& tree->data = 45, tree = 8049f98, tree->left = 8049fb0, tree->right = 8049fb0
&&& tree->data = 40, tree = 8049f80, tree->left = 0, tree->right = 8049f98


程序还需要再改，三个非递归函数的与Pop()操作相关的部分是关键。
_________________
笨

（我QQ在线状态）
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期一 四月 14, 2003 23:14    发表主题:        
晚上回家在上面贴子的基础上把PreorderNoRecursion()改好了，主要是Pop()相关代码做了修正，增加了一语句（粗体），在Pop()以前先给结点定位。

void PreorderNoRecursion(BTreePos tree)
{
　　　　Stack temp1;
　　　　BTreePos temptree;

　　　　CreateStack(&temp1);
　　　　temptree = tree;
　　　　while (temptree) {
　　　　　　　　printf
　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　 temptree->data, temptree, temptree->left, temptree->right);
　　　　　　　　if (temptree->right != NULL) {
　　　　　　　　　　　　Push(temptree->right, &temp1);
　　　　　　　　}
　　　　　　　　if (temptree->left != NULL) {
　　　　　　　　　　　　temptree = temptree->left;
　　　　　　　　} else if (temp1.top != NULL) {
　　　　　　　　　　　　temptree = temp1.top->addr;
　　　　　　　　　　　　Pop(temptree, &temp1);
　　　　　　　　} else {
　　　　　　　　　　　　break;
　　　　　　　　}
　　　　}
}

程序输出结果：
Use Preorder with recursion :
&&& tree->data = 30, tree = 8049ea0, tree->left = 0, tree->right = 8049eb8
&&& tree->data = 45, tree = 8049eb8, tree->left = 0, tree->right = 8049ed0
&&& tree->data = 65, tree = 8049ed0, tree->left = 8049ee8, tree->right = 8049f18
&&& tree->data = 60, tree = 8049ee8, tree->left = 8049f00, tree->right = 0
&&& tree->data = 50, tree = 8049f00, tree->left = 0, tree->right = 0
&&& tree->data = 100, tree = 8049f18, tree->left = 0, tree->right = 8049f30
&&& tree->data = 140, tree = 8049f30, tree->left = 0, tree->right = 8049f48
&&& tree->data = 160, tree = 8049f48, tree->left = 0, tree->right = 0
Use Preorder with no recursion :
&&& tree->data = 30, tree = 8049ea0, tree->left = 0, tree->right = 8049eb8
&&& tree->data = 45, tree = 8049eb8, tree->left = 0, tree->right = 8049ed0
&&& tree->data = 65, tree = 8049ed0, tree->left = 8049ee8, tree->right = 8049f18
&&& tree->data = 60, tree = 8049ee8, tree->left = 8049f00, tree->right = 0
&&& tree->data = 50, tree = 8049f00, tree->left = 0, tree->right = 0
&&& tree->data = 100, tree = 8049f18, tree->left = 0, tree->right = 8049f30
&&& tree->data = 140, tree = 8049f30, tree->left = 0, tree->right = 8049f48
&&& tree->data = 160, tree = 8049f48, tree->left = 0, tree->right = 0
Use Preorder with recursion :
&&& tree->data = 30, tree = 8049ea0, tree->left = 0, tree->right = 8049eb8
&&& tree->data = 45, tree = 8049eb8, tree->left = 0, tree->right = 8049ed0
&&& tree->data = 65, tree = 8049ed0, tree->left = 8049ee8, tree->right = 8049f18
&&& tree->data = 60, tree = 8049ee8, tree->left = 8049f00, tree->right = 0
&&& tree->data = 50, tree = 8049f00, tree->left = 0, tree->right = 0
&&& tree->data = 100, tree = 8049f18, tree->left = 0, tree->right = 8049f30
&&& tree->data = 140, tree = 8049f30, tree->left = 0, tree->right = 8049f48
&&& tree->data = 160, tree = 8049f48, tree->left = 0, tree->right = 0

我kao,又十一点半了，洗澡睡觉。中、后序非递归的函数明天再检查。
_________________
笨

（我QQ在线状态）
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期二 四月 15, 2003 10:12    发表主题:        
刚把中序非递归函数改好，也是修改Pop()相关的操作语句。
void InorderNoRecursion(BTreePos tree)
{
　　　　BTreePos topnode, temptree;
　　　　Stack temp2;
　　　　int last = -1, printed = -1;

　　　　topnode = tree;
　　　　temptree = tree;
　　　　CreateStack(&temp2);
　　　　while (temptree) {
　　　　　　　　if (temptree->left != NULL && temptree->data != last) {
　　　　　　　　　　　　Push(temptree, &temp2);
　　　　　　　　　　　　temptree = temptree->left;
　　　　　　　　} else {
　　　　　　　　　　　　if (printed != temptree->data) {
　　　　　　　　　　　　　　　　printf
　　　　　　　　　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　　　　　　　　　 temptree->data, temptree, temptree->left, temptree->right);
　　　　　　　　　　　　}
　　　　　　　　　　　　if (temptree->right != NULL) {
　　　　　　　　　　　　　　　　temptree = temptree->right;
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else if (temp2.top != NULL) {
　　　　　　　　　　　　　　　　temptree = temp2.top->addr;
　　　　　　　　　　　　　　　　Pop(temptree->parent, &temp2);
　　　　　　　　　　　　　　　　last = temptree->data;
　　　　　　　　　　　　　　　　if (temptree != topnode) {
　　　　　　　　　　　　　　　　　　　　temptree->parent->left = temptree;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　printf
　　　　　　　　　　　　　　　　　　("&&& tree->data = %d, tree = %x, tree->left = %x, tree->right = %x\n",
　　　　　　　　　　　　　　　　　　 temptree->data, temptree, temptree->left, temptree->right);
　　　　　　　　　　　　　　　　printed = temptree->data;
　　　　　　　　　　　　　　　　if (temptree->right != NULL) {
　　　　　　　　　　　　　　　　　　　　temptree = temptree->right;
　　　　　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　　　　　}
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}
_________________
笨

（我QQ在线状态）

最后进行编辑的是 sailer on 星期二 四月 15, 2003 13:23, 总计第 1 次编辑
返回页首        
                
sailer
站长


加入于: 2002-08-21
文章: 1179
位置: 上海
       
发表于: 星期二 四月 15, 2003 13:12    发表主题:        
后序的非递归，增加了判断是否是根结点的判断，修改以前每次执行到根结点的时候因为没有parent结点而出错（段错误）。
void PostorderNoRecursion(BTreePos tree)
{
　　　　BTreePos topnode;
　　　　Stack temp3;
　　　　Line templine;
　　　　int rightprinted = -1;

　　　　topnode = tree;
　　　　CreateStack(&temp3);
　　　　CreateLine(&templine);

　　　　while (tree) {
　　　　　　　　if (tree->left != NULL && !FindInLine(tree->left->data, &templine)) {
　　　　　　　　　　　　Push(tree, &temp3);
　　　　　　　　　　　　tree = tree->left;
　　　　　　　　} else {
　　　　　　　　　　　　if ((tree->right != NULL) && (tree->right->data != rightprinted)) {
　　　　　　　　　　　　　　　　Push(tree, &temp3);
　　　　　　　　　　　　　　　　tree = tree->right;
　　　　　　　　　　　　　　　　continue;
　　　　　　　　　　　　} else {
　　　　　　　　　　　　　　　　printf("&&am
回复

使用道具 举报

moonsky
 楼主| 发表于 2003-5-30 22:14:19 | 显示全部楼层
口弓虽！
回复

使用道具 举报

rhyno
发表于 2003-5-31 14:30:51 | 显示全部楼层
To flyaway :

二元樹可以用在搜尋和排序，分別可以提供 O(lgN) 和 O(NlgN) 的時間複雜度。比基本的泡泡排序或線性搜尋要來得好。

To Sjinny :

Graph traversing 的演算法最基本的就是 DFS 和 BFS，隨便找一本 DATA structuring 的書都有。若有需要做進一步的處理時，例如 topological sort ，尋找 articulation point, 找出 component 等，可以利用 DFS 再加上 dtime (discovery time) 和 ftime( finish time) ，詳細的步驟請參考 cormen 等三位教授的書。

若對 algorithm 有興趣，還可以參考 manber 的書，雖薄，但是內容豐富。
回复

使用道具 举报

发表于 2003-5-31 18:24:18 | 显示全部楼层
楼主：我是大菜鸟，可不可以给个用C来实现链表的程序呢？我现在搞得头都大完了。
回复

使用道具 举报

flyaway
发表于 2003-6-1 14:52:09 | 显示全部楼层
To rhyno:

多谢回复。但是你的回答还未能解我疑窦，我是想知道，二叉树这种数据结构，如何应用于现实问题中。例如：目前我正在编写一个播放器的播放列表，它有两个数据对象，专辑和曲目。我使用了二维链表来完成数据的组织和操作。但是，程序写完之后还有很多缺点（主要的问题就是排序），因此我想到了能不能通过其他的数据结构来帮我实现上述需求。
还希望公社的朋友能给我些提示和经验。
回复

使用道具 举报

rhyno
发表于 2003-6-2 12:17:10 | 显示全部楼层
To flyaway :

使用 linked list 的好處是增刪容易，但是在查詢和排序時就只能使用線性方法。如果想要加
快排序的速度，那傳統的作法視你的資料特性而定。如果是固定的，那可以使用 quick sort
或者是 hash 的作法。如果是變動的，那 binary tree 或是 heap tree 都是還不差的作法。

或者是你也可以考慮 radix sort 一類的作法，只要你覺得空間上的犧牲是值得的話。

就一般情況下來講，因為對曲目的編輯操作基本的增刪查詢排序都是免不了的，或許你可以考慮一下 binary tree 和 heap tree。其中 heap tree 如果配合像 STL 中 vector 一類的 container 來實作時，實際上的效果還不錯。

個人淺見，若有謬誤尚祈不吝指正。
回复

使用道具 举报

flyaway
发表于 2003-6-16 09:54:57 | 显示全部楼层
To rhyno:

最近比较忙，现在才看见这张帖子，对不起。
多谢指教！hash , binary tree, heap tree这些都快还给老师了，呵呵，需要再看看书。不过大学时候的书是pascal版的，而且写得比较晦涩，没有应用实例。能不能推荐本比较好的数据结构书，最好是有些应用实例的。
多谢多谢！
回复

使用道具 举报

rhyno
发表于 2003-6-16 22:05:25 | 显示全部楼层
[quote:dfd7ce3d8a="flyaway"]To rhyno:

最近比较忙，现在才看见这张帖子，对不起。
多谢指教！hash , binary tree, heap tree这些都快还给老师了，呵呵，需要再看看书。不过大学时候的书是pascal版的，而且写得比较晦涩，没有应用实例。能不能推荐本比较好的数据结构书，最好是有些应用实例的。
多谢多谢！[/quote]

沒有關係，剛巧前一陣子在看歐洲近古史，我也是今天才上來 ...

如果你的大學用書也是 Horowitz 出的話，那他的書有很多語言的版本，
一魚數吃，你可以都參考一下。不過，我覺得書裡面的範例寫得很醜，學
習價值不高。

如果要用 hash ，還可以考慮用 STL 中的 map，如果是 tree 的操作，
就要自己花腦筋了。

Heap tree 的虛擬碼，我覺得 cormen 書中的範例不錯，而且很嚴謹，
可以考慮拿來實作看看。 ^^

關於演算法的部份我所知的也就是這幾本書，希望能夠有一點幫助。
回复

使用道具 举报

下一页 »
12下一页
返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

GMT+8, 2025-2-8 05:43 , Processed in 0.032772 second(s), 15 queries .

© 2001-2025 Discuz! Team. Powered by Discuz! X3.5.

快速回复 返回顶部 返回列表