C/C++ツリーの遍歴再帰と非再帰の実現

よく言えば、すべての再帰はスタックで実現することができます.肝心なのは再帰とスタックの基本原理を理解することである.

ここでは最も典型的な中順遍歴を例にとると、他の実装は

に類似する.

c++STLのstack

を直接呼び出す.

木の知識点は大量の再帰知識を用いており、よく理解していない場合は典型的な二叉木の例を探して、アルゴリズム

を試してみることをお勧めします.
データ構造:

typedef char ElemType;

typedef struct BiTNode {
	ElemType data;
	struct BiTNode *lchild, *rchild;
} Node, *Tree;

中間パスの再帰的な実装:

void InOrderTraverse(Tree T, void (*Visit)(ElemType e)) {
	if(T) {
		InOrderTraverse(T->lchild,Visit);
		Visit(T->data);
		InOrderTraverse(T->rchild,Visit);
	}	
}

非再帰的なインプリメンテーション:

void InOrderTraverse2(Tree T, void (*Visit)(ElemType e)) {
	stack<Node*> S;
	Tree p;
	p = T;
	S.push(p);
	while (p->lchild != NULL) {
		p = p->lchild;
		S.push(p);
	}
		while (!S.empty()) {
			p = S.top();
			Visit(p->data);
			S.pop();
			if (p->rchild != NULL) {
				p=p->rchild;
				S.push(p);
				while (p->lchild != NULL) {
					p = p->lchild;
					S.push(p);
				}			
			}
		}
}