杨辉三角数据结构

#include <vector>
#include <iostream>

using namespace std;

struct BaseNode
{
	int value;
	int depth;
	struct BaseNode* lparent;
	struct BaseNode* rparent;
	struct BaseNode* lchild;
	struct BaseNode* rchild;
};

void genPascalTri(BaseNode* & node,int n)
{
	std::vector<BaseNode*> cur;
	std::vector<BaseNode*> las;
	las.push_back(node);
	for(int i=1;i<n;++i){
		for(int j=0;j<=i;++j){
			BaseNode* cnode = new BaseNode();
			cur.push_back(cnode);
			cur[j]->depth = i+1;

			if(j==0){
				cur[j]->value = las[0]->value;
				cur[j]->lparent = NULL;
				cur[j]->rparent = las[0];
				las[0]->lchild = cur[j];
			}
			else if (j==i){
				cur[j]->value = las[i-1]->value;
				cur[j]->rparent = NULL;
				cur[j]->lparent = las[i-1];
				las[i-1]->rchild = cur[j];
			}
			else{
				cur[j]->value = las[j-1]->value + las[j]->value;
				cur[j]->lparent = las[j-1];
				cur[j]->rparent = las[j];
				las[j-1]->rchild = cur[j];
				las[j]->lchild = cur[j];
			}
		}
		las.clear();
		las.assign(cur.begin(),cur.end());
		cur.clear();
	}

}

int main()
{
	BaseNode* node = new BaseNode();
	node->value = 1;
	node->depth = 1;
	cout<<"Please input n:"<<endl;
	int n;
	cin>>n;
	genPascalTri(node,n);
	cout<<node->value<<endl;
	for(int i=1;i<n;++i){
		if(i%2 == 1) node = node->lchild;
		else node = node->rchild;
		for(int j=0;j<i;++j){
			cout<<node->value<<" ";
			if(i%2 == 1)node = node->rparent->rchild;
			else node = node ->lparent ->lchild;
		}
		cout<<node->value<<endl;
	}

	return 0;
}