二叉樹遍歷的問題

billzhou

二叉樹的后序遍歷   不過不能用遞歸  也不能用棧

anthony1983

引入指向父節(jié)點的指針

billzhou

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

}*BTree,BTree;

給定了一個頭結(jié)點來遍歷

billzhou

原帖由 billzhou 于 2007-10-31 22:12 發(fā)表
Typedef struct
{
   b_Tree    *parent;
   b_Tree    *left;
   b_Tree     *right;

}*BTree,b_Tree;

給定了一個頭結(jié)點來遍歷

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   //根節(jié)點沒有老爸，遍歷完畢                 return;         }         if (p->times == 1) //第一次訪問，看看有沒有左節(jié)點         {             if (p->left != NULL)                 q = p->left;         }         else   //第二次訪問，看看有沒有右節(jié)點         {             if (p->right != NULL)                 q = p->right;         }     } }

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