【树的基本操作】

前言

因为某憨憨纠结于这里很久，所以本人决定还是把树的基本操作列出一个小结。

1）树的递归遍历

树的递归遍历非常简单。只要改变操作的位置就可以了（见代码）

但由于只有二叉树才有中序遍历，这里就不描述了。

代码

void Order(tree t) {
    if (!t) return;
    //前序遍历
        for (int i = 0; i < n; i++)
            Order(t->child[i]);
        //后序遍历
}

2）树的非递归遍历

树的遍历这一块可以简单分成两组（树和二叉树）。

但是二叉树毕竟也是一种树，所以我们讲二叉树会用一种其他的方法进行操作。

1.树的非递归前序遍历

首先讲树的前序遍历，也就是笼统意义的前序遍历

首先我们要知道：

前序遍历是按照一定顺序进行遍历的（当前节点->第一个子节点-> -> ->第n个子节点）。
要写非递归的遍历程序，我们要用到栈，利用后进先出的特性进行遍历。
而栈的意义就是储存没有操作完的节点。

即使这些我们都知道，那怎么用栈进行操作呢？

由于先序遍历是优先当前根节点的，所以我们第一步就是使用当前的根节点。
然后我们都知道前序遍历的顺序（上面讲了），所以根据栈后进先出的特性，我们应该把当前节点的子节点，倒序输入。
（由于当前正在使用第一个节点，我们就不将其存入栈中）
接下来依次类推，我们就会先将左侧的节点标记进栈。直到碰到叶子节点。
那碰到叶子节点怎么办呢？我们就前往下一个节点啦，所以取出栈顶元素就好啦（因为我们逆序存储，下一个节点就正好是我们栈中的下一个顶部元素）。
所以到最后，栈空了，表示我们操作完了，咱们就可以结束啦。

代码

void PreOrder(tree root) {
	std::stack<tree> st;
	tree front = root;
	while (!st.empty() || front)
		if (front) {
			printf("%c", front->data);
			int i = 0;
			for (i = degree - 1; i > 0; i--)
				if (front->child[i])
					st.push(front->child[i]);
			//从后往前入栈（不进第一个，因为直接用了）
			front = front->child[0];
		} 
		else {
			front = st.top();
			st.pop();
			//读到叶子节点使front变成栈顶元素（下一个元素），并弹出该元素（使用）
		}
}

2.二叉树的非递归前序遍历（及中序遍历）

而二叉树相对来说就简单很多了，因为只有左右两棵子树。

所以我们的操作原理就是：

同样用栈对节点进行储存。栈的意义也是一样：储存没有操作完的节点。（在这里就是指遍历了左节点，没有遍历右节点）
所以我们就好说了，因为操作简单，我们可以直接左子树一条龙到叶节点。
碰到叶节点时我们就返回并对其右节点访问。因为此时我们已经访问了其右节点，所以我们就可以删除该节点了。（因为我们已经操作完这个节点了）。
同样，一直访问到栈空时，就结束了。

除此之外，中序遍历和前序遍历的差别不大：

只有二叉树才有中序遍历，毕竟树的话都没有“中”这个概念。
中序遍历只要在对左子树和右子树中间进行操作就行了，所以我们可以在切换到右子树时，进行中序遍历。（详情见代码）

代码

void PreOrder(bintree t) {
    seqstack st; st.top = 0;
    bintree root = t;
    while (root || st.top) {
        while (root) {
            //printf("%c", root->data);先序遍历
            st.data[st.top++] = root;
            root = root->lchild;
        }
        if (st.top) {
            root = st.data[--st.top];
            //printf("%c", root->data);中序遍历
            root = root->rchild;
        }
    }
}

3.树的非递归后序遍历

同样，我们讲树的后序遍历，也就是笼统意义的后序遍历

非递归的后序遍历要比前序遍历难一些。因为和先序遍历并不是很相似。

首先我们要知道：

后序遍历是按照一定顺序进行遍历的（第一个子节点-> -> ->第n个子节点->当前节点）。
要写非递归的遍历程序，我们要用到栈，利用后进先出的特性进行遍历。
而栈的意义就是储存没有操作完的节点。

然后，怎么用栈进行操作呢？

由于后序遍历是最后操作当前根节点的，那我们可以转换一个思想：我们和前序遍历反着来，变成一个优先最右边节点的前序遍历。
但是终究是从左边开始到，所以我们最后倒序输出就好了。
这个思想给了我们一个启发，我们可以和前序遍历一样用一个栈来对树进行操作，用另外一个栈来保存我们要输出的值。（相当于先序遍历那里的直接输出）。
和前面一样，只要操作栈空了，我们就操作完了，就可以去输出啦！

代码

void PostOrder(tree root) {
	std::stack<tree> st1, st2; //待处理节点栈，处理完毕节点栈 
	tree front = root; 
	if (front) st1.push(front);//特判空树 
	while (!st1.empty()) {
		front = st1.top(); st1.pop();
		for (int i = 0; i < degree; ++i) 
			if (front->child[i])
				st1.push(front->child[i]);
				//子节点全部进栈
		st2.push(front); //root处理完毕（子节点全部入栈），在子节点之后输出
	}
	while (!st2.empty()) {
		printf("%c", st2.top()->data);
		st2.pop();
	}
}

4.二叉树的非递归后序遍历

既然是二叉树，我们的非递归后序遍历自然好操作一点，毕竟只有两个孩子。

所以原理就是：

我们先用一个栈保存还没操作完的的节点。
我们再新建一个tag数组，来记录每个节点是否已经访问完全（左右节点都操作过了）
所以我们再判断左节点的时候给当前的tag=0，我们再操作完了右节点的时候就给当前的tag=1。
我们只要在回溯前进行对访问情况（tag）进行判断就可以了。
最后，每个节点的tag都会=1，而这个时候，我们的栈也操作空了，我们就可以结束辽。

代码

void PostOrder(bintree t) {
    seqstack st; st.top = 0;
    bintree root = t;//移动指针
    while (root || st.top != 0) {
        while (root) {
            st.data[st.top] = root;
            st.tag[st.top++] = 0;//只访问过该节点左孩子（置零）
            root = root->lchild;
        }
        if (st.top != 0)
            if (st.tag[st.top - 1] == 1) {
                root = st.data[--st.top];
                printf("%c", t->data);
                root = NULL;
            }
            //该节点已经被完全访问（走过了右节点）
            else {
                root = st.data[st.top - 1];
                st.tag[st.top - 1] = 1;
                root = root->rchild;
            }
            //未被访问完全（向右节点移动）
    }
}

3）树的表示法转换

括号表示法->孩子表示法

表示法的转换也不是非常难，我们只要知道每一个符号有什么意义就好了。

所以转换的操作可以分成以下几点：

我们要先了解每一个字符的意义：
'('：表示前面的一个节点时括号内节点的根。
','：分隔符，在确定树的孩子位置时有用（可以加一个参数以确定孩子位置），我们此处孩子优先放在靠左。
')'：表示当前根已经没有更多子节点了。
字母：表示节点的编号，遇到直接加到当前的根节点上去。
在这里，我们发现两个点：一个是我们要获得前一个节点，并加到根上去；另一个是我们要对当前根节点进行操作，所以我们肯定要用到栈。
于是，我们就可以这样操作：
遇到字母，我们就建立一个新的节点，并加到当前的栈顶上面去。（若栈顶不存在就是根节点了）。
遇到'('我们就把上一个建立好的节点入栈。
遇到')'我们就删掉栈顶节点（表示建立好了这棵子树）。
到最后一个字符一定是')'，栈空了我们的循环就结束了，我们只要把根节点返回就好了。

代码

tree Ct(char s[MAXLEN])	{
	std::stack<tree> st;//自定义栈 
	tree root = NULL, child = NULL;//root记录当前根节点位置（保持与栈顶一致），child记录上一个插入的节点 
	int cnt = 0, flag = 0;//cnt记录数组位置，flag记录栈空/满 
	while (!flag && s[cnt]) {
		if (s[cnt] == '(') {
			root = child;
			st.push(root);
		}
		//遇到'('时，讲栈顶元素和根节点指向'('前的元素 
		else if (s[cnt] == ')') {
			st.pop();
			if (st.empty()) flag = 1;
			else root = st.top();
		}
		//遇到')'时，弹出栈顶元素，root也回调。 
		else if (s[cnt] == ','); 
		else {
			child = (tree)malloc(sizeof(node));
			child->data = s[cnt];
			int i;
			for (i = 0; i < m; i++)
				child->child[i] = NULL;
			//初始化新节点 
			if (root) 
				for (i = 0; i < m; i++)
					if (root->child[i] == NULL) {
						root->child[i] = child;
						break;
					}
			//父节点不为空时（特判第一个节点），插入根的最后一个非空位置 
		}
		//遇到节点时，将节点元素变成当前栈顶的子节点 
		cnt++;
	}
	return root;
}