二叉树

1.二叉树的遍历

先序遍历（根->左子树->右子树）

void dfs(根){
    cout<<根；
    dfs(左子树)；
    dfs(右子树)；
}

中序遍历（左子树->根->右子树）

void dfs(根){
    dfs(左子树)；
    cout<<根；
    dfs(右子树)；
}

先序遍历（左子树->右子树->根）

void dfs(根){
    dfs(左子树)；
    dfs(右子树)；
    cout<<根；
}

2.二叉树的存储

• 按图的方法存储

• 广义表存储

输入：1(3(4)5((6)(7)))

void Tree(int u){
	bool flag=false;
	int x=0,c=-1;
	char z;
	while(cin>>z){
		if(z=='-')flag=true;
		if(z>='0'&&z<='9')x=x*10+z-'0';
		if(z=='('){
			if(flag){
				flag=false;
				x=-x;
			}
			tree[u]=x;
			c++;
			Tree(2*u+c);
		}
		if(z==')')break;
	}
}

树

树没有中序遍历。先根遍历按照根->左子树1->左子树2->……->右子树n的顺序，后根遍历按照左子树1->左子树2->……->右子树n->根的顺序。