二叉樹的遍歷-有解無憂

morris遍歷二叉樹,將當前遍歷到達的節點記為 cur.
	cur沒有左孩子:
		cur 向右孩子移動.
	cur有左孩子:
		找到cur的左子樹的最右節點記為 rightmost.
		rightmost的右孩子指標指向NULL, 讓其指向cur, 然后cur向左孩子移動.
		rightmost的右孩子指標指向cur, 讓其指向空, 然后cur向右孩子移動.

前序遍歷：遞回實作

void preorderRecursionTraversal( NodeBinaryTree *root ) {
	if( root == NULL ) {
		return;
	}
	printf( "%d, ", root->val );
	preorderRecursionTraversal( root->left, a, aSize );
	preorderRecursionTraversal( root->right, a, aSize );
}

前序遍歷：迭代實作

#define NEW_STACK( s, capacity ) ({                             \
	*s = malloc( sizeof(**s) + sizeof((*s)->a[0]) * capacity ); \
	*s->t = 0; (*s)->c = capacity;                              \
})
#define PUSH_STACK( s, d ) ({ s->a[s->t++] = d; })
#define POP_STACK( s, d ) ({ *d = s->a[--s->t]; })
#define EMPTY_STACK( s ) (s->t < 1)
#define FULL_STACK( s ) (s->t >= s->c)
#define DEL_STACK( s ) ({ if( s != NULL && *s != NULL ) { free( *s ); *s = NULL; } })

typedef struct Stack {
	int c;
	int t;
	void *a[0];
} Stack;

void preorderIterativeTraversal( NodeBinaryTree *root ) {
	Stack *s = NULL;

	if( root != NULL ) {
		NEW_STACK( &s, 10000 );
		PUSH_STACK( s, root );
	}
	while( !EMPTY_STACK( s ) ) {
		POP_STACK( s, &root );
		printf( "%d, ", root->val );
		if( root->right != NULL ) {
			PUSH_STACK( s, root->right );
		}
		if( root->left != NULL ) {
			PUSH_STACK( s, root->left );
		}
	}
	DEL_STACK( &s );
}

前序遍歷：morris實作

只處理第一次到達的節點.

void preorderMorrisTraversal( NodeBinaryTree *root ) {
	while( root != NULL ) {
		if( root->left != NULL ) {
			NodeBinaryTree *rightmost = root->left;
			while( rightmost->right != NULL && rightmost->right != root ) {
				// cur節點的左子樹的最右節點.
				rightmost = rightmost->right;
			}
			if( rightmost->right != NULL ) {
				rightmost->right = NULL;
				root = root->right;
			} else {
				// cur節點的左子樹的最右節點沒有被修改過,說明是第一次到達cur節點.
				printf( "%d, ", root->val );
				rightmost->right = root;
				root = root->left;
			}
		} else {
			// cur節點沒有子樹.
			printf( "%d, ", root->val );
			root = root->right;
		}
	}
}

中序遍歷：遞回實作

void inorderRecursionTraversal( NodeBinaryTree *root ) {
	if( root == NULL ) {
		return;
	}
	inorderRecursionTraversal( root->left );
	printf( "%d, ", root->val );
	inorderRecursionTraversal( root->right );
}

中序遍歷：迭代實作

#define NEW_STACK( s, capacity ) ({                             \
	*s = malloc( sizeof(**s) + sizeof((*s)->a[0]) * capacity ); \
	*s->c = capacity;                                           \
	*s->t = 0;                                                  \
})
#define PUSH_STACK( s, d )  ({ s->a[s->t++] = d; })
#define POP_STACK( s, d )   ({ *d = s->a[--s->t]; })
#define PEEK_STACK( s, d )  ({ *d = s->a[s->t - 1]; })
#define SIZE_STACK( s )     (s->t)
#define EMPTY_STACK( s )    (s->t < 1)
#define FULL_STACK( s )     (s->t >= s->c)
#define CLEAR_STACK( s )    ({ s->t = 0; })
#define DEL_STACK( s )      ({ if( s != NULL && *s != NULL ) { free( *s ); *s = NULL; } })

typedef struct Stack {
	int c;
	int t;
	void *a[0];
} Stack;

void inorderIterativeTraversal( NodeBinaryTree *root ) {
	Stack *s = NULL;

	NEW_STACK( &s, 10000 );
	#if 0
	while( root != NULL || !EMPTY_STACK( s ) ) {
		if( root != NULL ) {
			PUSH_STACK( s, root );
			root = root->left;
		} else {
			POP_STACK( s, &root );
			printf( "%d, ", root->val );
			root = root->right;
		}
	}
	#else
	while( root != NULL || !EMPTY_STACK( s ) ) {
		while( root != NULL ) {
			PUSH_STACK( s, root );
			root = root->left;
		}
		POP_STACK( s, &root );
		printf( "%d, ", root->val );
		root = root->right;
	}
	#endif
	DEL_STACK( &s );
}

中序遍歷：morris實作

只處理沒有左子樹的節點和第2次到達的節點.

void inorderMorrisTraversal( NodeBinaryTree *root ) {
	while( root != NULL ) {
		if( root->left != NULL ) {
			NodeBinaryTree *rightmost = root->left;
			while( rightmost->right != NULL && rightmost->right != root ) {
				// cur節點的左子樹的最右節點.
				rightmost = rightmost->right;
			}
			if( rightmost->right != NULL ) {
				// cur節點的左子最右節點被修改過,說明是第2次到達cur節點,
				// 即cur節點的左子樹已經處理完畢.
				printf( "%d, ", root->val );
				rightmost->right = NULL;
				root = root->right;
			} else {
				rightmost->right = root;
				root = root->left;
			}
		} else {
			// cur節點沒有左子樹.
			printf( "%d, ", root->val );
			root = root->right;
		}
	}
}

后序遍歷：遞回實作

void postorderRecursionTraversal( NodeBinaryTree *root ) {
	if( root == NULL ) {
		return;
	}
	postorderRecursionTraversal( root->left );
	postorderRecursionTraversal( root->right );
	printf( "%d, ", root->val );
}

后序遍歷：迭代實作

#define NEW_STACK( s, capacity ) ({                             \
	*s = malloc( sizeof(**s) + sizeof((*s)->a[0]) * capacity ); \
	*s->c = capacity;                                           \
	*s->t = 0;                                                  \
})
#define PUSH_STACK( s, d )  ({ s->a[s->t++] = d; })
#define POP_STACK( s, d )   ({ *d = s->a[--s->t]; })
#define PEEK_STACK( s, d )  ({ *d = s->a[s->t - 1]; })
#define SIZE_STACK( s )     (s->t)
#define EMPTY_STACK( s )    (s->t < 1)
#define FULL_STACK( s )     (s->t >= s->c)
#define CLEAR_STACK( s )    ({ s->t = 0; })
#define DEL_STACK( s )      ({ if( s != NULL && *s != NULL ) { free( *s ); *s = NULL; } })

typedef struct Stack {
	int c;
	int t;
	void *a[0];
} Stack;

// 另外一種實作：利用兩個堆疊, 將 中左右遍歷 改為 中右左遍歷, 中右左程序使用堆疊1, 左右中程序使用堆疊2.
// 將 中右左程序中元素輸出的地方 改為 輸出元素壓入堆疊2,
// 最后將堆疊2所有元素彈堆疊并輸出, 得到左右中遍歷序列, 即后序遍歷.
void postorderIterativeTraversal( NodeBinaryTree *root ) {
	NodeBinaryTree *lasttime = root;
	Stack *s = NULL;

	NEW_STACK( &s, 10000 );
	if( root != NULL ) {
		PUSH_STACK( s, root );
	}
	while( !EMPTY_STACK( s ) ) {
		PEEK_STACK( s, &root );
		if( root->left != NULL && root->left != lasttime && root->right != lasttime ) {
			PUSH_STACK( s, root->left );
		} else if( root->right != NULL && root->right != lasttime ) {
			PUSH_STACK( s, root->right );
		} else {
			POP_STACK( s, &lasttime );
			printf( "%d, ", lasttime->val );
		}
	}
	DEL_STACK( &s );
}

后序遍歷：morris實作

最先逆序處理第2次到達的節點的左子樹的右邊界節點,
最后逆序處理整棵樹的右邊界節點.

static void reverseHandleRightBoundary( NodeBinaryTree *root ) {
	NodeBinaryTree *p1 = NULL, *p2 = NULL, *p3 = NULL;

	for( p2 = root, p1 = NULL; p2 != NULL; p2 = p3 ) {
		p3 = p2->right;
		p2->right = p1;
		p1 = p2;
	}
	for( p2 = p1, p1 = NULL; p2 != NULL; p2 = p3 ) {
		printf( "%d, ", p2->val );
		p3 = p2->right;
		p2->right = p1;
		p1 = p2;
	}
}

void postorderMorrisTraversal( NodeBinaryTree *root ) {
	NodeBinaryTree *cur = root;

	while( cur != NULL ) {
		if( cur->left != NULL ) {
			NodeBinaryTree *rightmost = cur->left;
			while( rightmost->right != NULL && rightmost->right != cur ) {
				rightmost = rightmost->right;
			}
			if( rightmost->right != NULL ) {
				// cur節點的左子最右節點被修改過, 說明是第二次來到cur節點.
				rightmost->right = NULL;
				// 逆序處理cur節點的左子樹的右邊界節點.
				reverseHandleRightBoundary( cur->left );
				cur = cur->right;
			} else {
				rightmost->right = cur;
				cur = cur->left;
			}
		} else {
			cur = cur->right;
		}
	}
	// 最后逆序處理整棵樹的右邊界節點.
	reverseHandleRightBoundary( root );
}

層次遍歷：迭代實作

#define NEW_QUEUE( q, capacity ) ({                             \
	*q = malloc( sizeof(**q) + sizeof((*q)->a[0]) * capacity ); \
	*q->c = capacity;                                           \
	*q->s = 0;                                                  \
	*q->h = 0;                                                  \
})
#define ADD_QUEUE( q, d )   ({ q->a[(q->h + q->s++) % q->c] = d; })
#define POLL_QUEUE( q, d )  ({ *d = q->a[q->h]; q->h = (q->h + 1) % q->c; --q->s; })
#define PEEK_QUEUE( q, d )  ({ *d = q->a[q->h]; })
#define SIZE_QUEUE( q )     (q->s)
#define EMPTY_QUEUE( q )    (q->s < 1)
#define FULL_QUEUE( q )     (q->s >= q->c)
#define CLEAR_QUEUE( q )    ({ q->h = q->s = 0; })
#define DEL_QUEUE( q )      ({ if( q != NULL && *q != NULL ) { free( *q ); *q = NULL; } })

typedef struct Queue {
	int32_t c;
	int32_t s;
	int32_t h;
	void *a[0];
} Queue;

void levelOrderTraversal( NodeBinaryTree *root ) {
	Queue *q = NULL;

	NEW_QUEUE( &q, 10000 );
	if( root != NULL ) {
		ADD_QUEUE( q, root );
	}
	while( !EMPTY_QUEUE( q ) ) {
		int32_t count = SIZE_QUEUE( q );
		while( --count >= 0 ) {
			POLL_QUEUE( q, &root );
			printf( "%d, ", root->val );
			if( root->left != NULL ) {
				ADD_QUEUE( q, root->left );
			}
			if( root->right != NULL ) {
				ADD_QUEUE( q, root->right );
			}
		}
	}

	DEL_QUEUE( &q );
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/20807.html

標籤：C

上一篇：C 實戰練習題目24 -求數列和

下一篇：Delphi 列印機如何設定列印機的偏移量offsetX，offsetY