Programming 版 (精华区)
发信人: SwordLea (飞刀李), 信区: Programming
标 题: [合集]非递归后序遍历一棵二叉树方法
发信站: 哈工大紫丁香 (2003年12月23日12:03:16 星期二), 站内信件
────────────────────────────────────────
artist (手艺人) 于 2003年12月05日17:48:51 星期五 说道:
谢谢。
────────────────────────────────────────
Scorpion (.......................................) 于 2003年12月05日18:08:19 星期五 说道:
用stack
push的时候加一个标记
【 在 artist (手艺人) 的大作中提到: 】
谢谢。
────────────────────────────────────────
artist (手艺人) 于 2003年12月05日19:39:28 星期五 说道:
二叉树结点定义如下
struct bitree
{
int data;
struct bitree *left;
struct bitree *right;
};
怎么加标记，能否具体点？
谢谢。
【 在 Scorpion (.......................................) 的大作中提到: 】
: 用stack
: push的时候加一个标记
: 【 在 artist (手艺人) 的大作中提到: 】
: 谢谢。
────────────────────────────────────────
iamxiaohan (潇寒·System Programmer ^_^) 于 2003年12月05日22:24:56 星期五 说道:
【 在 artist (手艺人) 的大作中提到: 】
谢谢。
────────────────────────────────────────
iamxiaohan (潇寒·System Programmer ^_^) 于 2003年12月05日22:25:06 星期五 说道:
纯C论坛上有
【 在 artist (手艺人) 的大作中提到: 】
: 谢谢。
────────────────────────────────────────
hotman (风) 于 Sun Dec 7 19:31:33 2003 说道:
有一段时间没有看数据结构了:-)，看到这道题比较有意思，好像原来也写过。现在写
了一下，初步验证是通过了，不过你看看是不是有错。
struct binary_tree_s {
void *data;
struct binary_tree_s *left_son;
struct binary_tree_s *right_son;
struct binary_tree_s *link; //多定义一个域，生成树时复制为0，这
样是否适合你的空间要求
};
void output_data(void *data) {}
void post_order(struct binary_tree_s *binary_tree)
{
struct binary_tree_s *p, *q;
if (binary_tree) {
p = binary_tree;
while (1) {
if (p->left_son) {
if (!p->left_son->link) { //以此来判断左子树是否被访问过
p->left_son->link = p;
p = p->left_son;
continue;
}
}
if (p->right_son) {
if (!p->right_son->link) { //以此来判断右子树是否被访问过
p->right_son->link = p;
p = p->right_son;
continue;
}
}
output_data(p->data); //输出节点信息
if (p == binary_tree) { //判断是否已经到达根节点
break;
}
q = p;
p = p->link;
q->link = (struct binary_tree_s *)~0L; //将其复制为无效值
}
}
}
【 在 artist 的大作中提到: 】
: 谢谢。
--
╭≈☆水青☆≈╮
╰┄┄┄┄┄┄╯
长河落日 大漠孤烟
※ 来源:．哈工大紫丁香 bbs.hit.edu.cn [FROM: 219.133.122.170]
────────────────────────────────────────
hotman (风) 于 Sun Dec 7 22:54:59 2003 说道:
突然想起来，那个只能进行一次后序查询，需要加入几行代码就可以实现任意次后序查
询了。请斑竹删了那个不健全的算法:-)谢谢
struct binary_tree_s {
void *data;
struct binary_tree_s *link;
struct binary_tree_s *left_son;
struct binary_tree_s *right_son;
};
void output_data(void *data) {printf("data = %p\n", data);}
void post_order(struct binary_tree_s *binary_tree)
{
struct binary_tree_s *p, *q;
if (binary_tree) {
p = binary_tree;
while (1) {
if (p->left_son) {
if (!p->left_son->link) {
p->left_son->link = p;
p = p->left_son;
continue;
}
}
if (p->right_son) {
if (!p->right_son->link) {
p->right_son->link = p;
p = p->right_son;
continue;
}
}
output_data(p->data);
if (p->left_son) {
p->left_son->link = 0;
}
if (p->right_son) {
p->right_son->link = 0;
}
if (p == binary_tree) {
break;
}
q = p;
p = p->link;
q->link = (struct binary_tree_s *)~0L;
}
}
}
【 在 hotman 的大作中提到: 】
:
: 有一段时间没有看数据结构了:-)，看到这道题比较有意思，好像原来也写过。�..
: 了一下，初步验证是通过了，不过你看看是不是有错。
:
: struct binary_tree_s {
: void *data;
: struct binary_tree_s *left_son;
: struct binary_tree_s *right_son;
: struct binary_tree_s *link; //多定义一个域，生成树时复制为..
: 样是否适合你的空间要求
: };
:
: void output_data(void *data) {}
:
: void post_order(struct binary_tree_s *binary_tree)
: {
: struct binary_tree_s *p, *q;
:
: if (binary_tree) {
: p = binary_tree;
: (以下引言省略...)
────────────────────────────────────────
artist (手艺人) 于 2003年12月08日08:18:34 星期一 说道:
精益求精，是美德。
需要原来的算法作对比，才能显示出改进之处。
所以暂时不删了，呵呵。
【 在 hotman (风) 的大作中提到: 】
: 突然想起来，那个只能进行一次后序查询，需要加入几行代码就可以实现任意次后序查
: 询了。请斑竹删了那个不健全的算法:-)谢谢
: struct binary_tree_s {
: void *data;
:
: struct binary_tree_s *link;
: struct binary_tree_s *left_son;
: struct binary_tree_s *right_son;
: };
:
: void output_data(void *data) {printf("data = %p\n", data);}
────────────────────────────────────────
artist (手艺人) 于 2003年12月08日08:42:12 星期一 说道:
与Lerry合作，发现以下算法用于二叉树非递归后序遍历。实际验证有效。其
理论正确性还有待证明。
:D
typedef struct bitree /*二叉树结点定义*/
{
int data;
struct bitree *left;
struct bitree *right;
}BiTreeNode,*BiTree;
void PostOrder(BiTree bt) /*??后序非递归遍历二叉树*/
{
BiTree p;
Stack s1,s2; /*定义两个空栈*/
p=bt;
if(!bt) return;
while(p)
{
Push(s2,p); /*指针p压入栈s2*/
if(p->left)
Push(s1,p->left); /*指针p->left压入栈s1*/
p=p->right;
if(!p) p=Pop(s1); /*s1退栈*/
}
while(p=Pop(s2))
printf("%d\t",p->data);
}
【 在 artist (手艺人) 的大作中提到: 】
: 谢谢。
────────────────────────────────────────
hotman (风) 于 Mon Dec 8 22:01:22 2003 说道:
昨天晚上又把先根、中根的顺序遍历的非递规算法也写了一下并进行了初步的验证。
同时也验证了一下非递规的这三个算法时间开销是相应递规算法的1/2的样子。
struct binary_tree_s {
void *data;
struct binary_tree_s *link;
struct binary_tree_s *left_son;
struct binary_tree_s *right_son;
};
void output_data(void *data) {printf("node = %p \n", data);}
1，先根
void prev_order(struct binary_tree_s *binary_tree)
{
struct binary_tree_s *p, *q;
if (binary_tree) {
p = binary_tree;
output_data(p->data);
while(1) {
if (p->left_son) {
if (!p->left_son->link) {
p->left_son->link = p;
p = p->left_son;
output_data(p->data);
continue;
}
}
if (p->right_son) {
if (!p->right_son->link) {
p->right_son->link = p;
p = p->right_son;
output_data(p->data);
continue;
}
}
if (p->left_son) {
p->left_son->link = 0;
}
if (p->right_son) {
p->right_son->link = 0;
}
if (p == binary_tree) {
break;
}
q = p;
p = p->link;
q->link = (struct binary_tree_s *)~0L;
}
}
}
2，中根
void midl_order(struct binary_tree_s *binary_tree)
{
struct binary_tree_s *p, *q;
if (binary_tree) {
p = binary_tree;
while(1) {
if (p->left_son) {
if (!p->left_son->link) {
p->left_son->link = p;
p = p->left_son;
continue;
}
}
if (!p->right_son || !p->right_son->link) {
output_data(p->data);
}
if (p->right_son) {
if (!p->right_son->link) {
p->right_son->link = p;
p = p->right_son;
continue;
}
}
if (p->left_son) {
p->left_son->link = 0;
}
if (p->right_son) {
p->right_son->link = 0;
}
if (p == binary_tree) {
break;
}
q = p;
p = p->link;
q->link = (struct binary_tree_s *)~0L;
}
}
}
【 在 artist 的大作中提到: 】
: 与Lerry合作，发现以下算法用于二叉树非递归后序遍历。实际验证有效。其
: 理论正确性还有待证明。
: :D
: typedef struct bitree /*二叉树结点定义*/
: {
: int data;
: struct bitree *left;
: struct bitree *right;
: }BiTreeNode,*BiTree;
: void PostOrder(BiTree bt) /*??后序非递归遍历二叉树*/
: {
: BiTree p;
: Stack s1,s2; /*定义两个空栈*/
: p=bt;
: if(!bt) return;
: while(p)
: {
: Push(s2,p); /*指针p压入栈s2*/
: if(p->left)
: Push(s1,p->left); /*指针p->left压入栈s1*/
: (以下引言省略...)
────────────────────────────────────────
artist (手艺人) 于 2003年12月09日16:46:52 星期二 说道:
请教：：：怎末验证这三个算法的的时间开销?
谢谢。:D
【 在 hotman (风) 的大作中提到: 】
: 昨天晚上又把先根、中根的顺序遍历的非递规算法也写了一下并进行了初步的验证。
: 同时也验证了一下非递规的这三个算法时间开销是相应递规算法的1/2的样子。
: struct binary_tree_s {
: void *data;
: struct binary_tree_s *link;
: struct binary_tree_s *left_son;
: struct binary_tree_s *right_son;
: };
:
: void output_data(void *data) {printf("node = %p \n", data);}
:
────────────────────────────────────────
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：208.100毫秒