//二叉樹Morris后序遍歷函式
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void reverse(struct TreeNode *from, struct TreeNode *to)
{
struct TreeNode *x, *y, *z;
if (from==to) return;
x = from;
y = from->right;
from->right = NULL;
while (x!=to){
z = y->right;
y->right = x;
x = y;
y = z;
}
}
void printreverse(struct TreeNode *from, struct TreeNode *to)
{
struct TreeNode *p;
reverse(from, to);
p = to;
while (1){
printf("%d\n", p->val);
if (p==from) break;
p = p->right;
}
reverse(to, from);
}
void postorderTraverse(struct TreeNode *root)
{
struct TreeNode *p = NULL;
struct TreeNode *t1 = malloc(sizeof(struct TreeNode));
t1->left = root;
t1->right = NULL;
struct TreeNode *t = t1;
while (t){
if (t->left){
p = t->left;
while (p->right!=NULL && p->right!=t){
p = p->right;
}
if (p->right==NULL){
p->right = t;
t = t->left;
}
else{
printreverse(t->left, p);
p->right = NULL;
t = t->right;
}
}
else{
t = t->right;
}
}
free(t1);
}
這段代碼我在編譯器上測驗過了，沒有發現錯誤的地方，但是感覺代碼是不是太長了？有什么需要改進的地方嗎？
uj5u.com熱心網友回復：
這是morris后序遍歷必須的步驟，也就是先遍歷到左子樹的最右節點，才開始逆向列印。所以逆向列印步驟省不了，優化的地方有限，關鍵就看逆向列印怎么實作。通常的做法就是先把節點逆轉，列印結束后再把節點逆轉回來。如果非要改進，參考以下代碼吧
struct TreeNode
{
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* reverse(struct TreeNode *node)
{
struct TreeNode* pre = NULL;
struct TreeNode* next = NULL;
while (node != NULL){
next = node->right;
node->right = pre;
pre = node;
node = next;
}
return pre;
}
void printreverse(struct TreeNode *node)
{
struct TreeNode* tail =reverse(node);
struct TreeNode* cur = tail;
while (cur != NULL ){
printf("%d\n", cur->val);
cur =cur->right;
}
reverse(tail);
}
void postorderTraverse(struct TreeNode *root)
{
if (root==NULL) return;
struct TreeNode *p = NULL;
//struct TreeNode *t1 =malloc(sizeof(struct TreeNode)); //沒必要用t1
//t1->left = root;
//t1->right = NULL;
//struct TreeNode *t = t1;
struct TreeNode* t = root; //直接t從root開始就可以
while (t){
p = t->left;
//if (t->left){
if (p->left){
//p = t->left;
while (p->right!=NULL && p->right!=t){
p = p->right;
}
if (p->right==NULL){
p->right = t;
t = t->left;
}
else{
//printreverse(t->left, p);
p->right = NULL; //為了節點逆轉的判斷，先恢復右節點為NULL
printreverse(t->left); //再逆向列印
t = t->right;
}
}
else{
t = t->right;
}
}
//free(t1);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/168193.html
標籤：C語言
上一篇：小白求指教