二叉树遍历的问题

billzhou

二叉树的后序遍历   不过不能用递归  也不能用栈

anthony1983

引入指向父节点的指针

billzhou

Typedef struct
{
   b_Tree    *parent;
   b_Tree    *left;
   b_Tree     *right;

}*BTree,BTree;

给定了一个头结点来遍历

billzhou

原帖由 billzhou 于 2007-10-31 22:12 发表
Typedef struct
{
   b_Tree    *parent;
   b_Tree    *left;
   b_Tree     *right;

}*BTree,b_Tree;

给定了一个头结点来遍历

Typedef struct
{
   b_Tree    *parent;
   b_Tree    *left;
   b_Tree     *right;

}*BTree,b_Tree;

anthony1983

自己验证一下看对不对，粗略测了一下。基本思想就是这样的，需要做访问标记，加入父指针是为了方便回退。

void postorder_bbtree(bbtree_node *btn) {     bbtree_node *p;     bbtree_node *q = btn;     for (;;)     {         p = q;         p->times++;         if (p->times == 3) //第三次访问，可以打印了         {                          print_bbtreeNode(p);             p->times = 0;  //用完了归零，方便下次遍历哈             if ((q = p->father) != NULL)                 continue;             else   //根节点没有老爸，遍历完毕                 return;         }         if (p->times == 1) //第一次访问，看看有没有左节点         {             if (p->left != NULL)                 q = p->left;         }         else   //第二次访问，看看有没有右节点         {             if (p->right != NULL)                 q = p->right;         }     } }

[ 本帖最后由 anthony1983 于 2007-11-1 08:58 编辑 ]