如果child有到parent的ref的话。Let struct treeNode{ int id; treeNode *left; treeNode *right; treeNode *par; }; DFS(treeNode *root){ treeNode *cur=root; while (cur!=NULL){ printf("%d, ", cur->id); if (cur->left!=NULL){ cur=cur->left; } else if (cur->right!=NULL) cur=cur->right; else{ treeNode *par=cur->par; while (par!=NULL){ if (par->left==cur && par->right!=NULL){ cur=par->right; break; } cur=par; par=par->par; } if (par==NULL) cur=NULL; } } } 其实就是depth first, 应该是O(3n)=O(n)吧。