データ構造とアルゴリズムツリーテンプレートクラスの実装(再帰非再帰遍歴)

ツリーノードとツリークラスの定義は次のとおりです.

#include
using namespace std;
const int Maxsize = 100;
template
struct BiNode {
	T data;
	BiNode*rch;
	BiNode*lch;
};
template
class Bitree {
private:
	void Create(BiNode*&R, T data[], int n);
	void Release(BiNode*R);
public:
	BiNode*Root;
	Bitree(T data[]) { Create(Root, data, 1); }
	~Bitree() { Release(Root); }
};

二叉木クラスを再帰的に生成および破棄する

templatevoid Bitree::Create(BiNode*&R, T data[], int i) {
	if (data[i - 1] != 0) {//       ，   
		R = new BiNode;//         
		R->data = data[i - 1];
		R->lch = R->rch = NULL;
		Create(R->lch, data, 2 * i);//    
		Create(R->rch, data, 2 * i + 1);
	}
}
templatevoid Bitree::Release(BiNode*R) {
	if (!R) {
		Release(R->lch);
		Release(R->rch);
		delete R;
	}
}

再帰的に遍歴を行う前序と中序のため,後序遍歴のアルゴリズムは同様に位置を変えるだけでよいが,前序遍歴を例に挙げる.

templatevoid PreOrder(BiNode*&R)
{
	if (R) {
		cout << R->data ;
		PreOrder(R->lch);
		PreOrder(R->rch);
	}
	cout << 0;
}

非再帰的な方式で各種の遍歴方式の前序遍歴を実現する:スタックの先進的な後出の思想で実現する.格納ノードの配列(スタック)を定義し、スタックの上部にルートノードをスタックします.2.それから桟を突き出して、桟を出ると同時に、その左右の子供が桟に入って、先進的な後出の思想のため、まず右の子供を桟に入れます.3.スタックが空でない場合は、2コードを継続する

templatevoid PreOrder(BiNode*R) {
	BiNode*stack[Maxsize];
	int top = -1;
	BiNode*p;
	if (R != NULL)
	{
		stack[++top] = R;
		while (top != -1) {
			p = stack[top--];
			cout << p->data<rch != NULL)stack[++top] = p->rch;
			if (p->lch != NULL)stack[++top] = p->lch;
		}
	}
}

中序遍歴:1.スタックとワークポインタを定義し、ルートノードがスタックに入り、ワークポインタがルートノードを指します.2.スタックが空でない場合、またはワークノードがNULLでない場合にループを開始します.2.1作業ポインタの左の子供、左の子供の左の子供は順番にスタックに入って、左の子供のノードがないまで.2.2ノードにアクセスしてスタックを出し、作業ノードを右の子供ノードに向けます.2.3次のループ:右の子ノードおよび右の子ノードに子ノードがあるかどうかを判断し、右の子ノードが存在しない場合は前のノードに戻る.ループを続けます.

templatevoid InOrder(BiNode*R) {
	BiNode*stack[Maxsize];
	int top = -1;
	BiNode*p=R;
	cout << "    ";
	while (top != -1 || p != NULL) {
		while (p) {
			stack[++top] = p;
			p = p->lch;
		}
		if (top != -1) {
			p = stack[top--];
			cout << p->data<rch;
		}
	}
}