|
//4.4 二叉树的遍历方法 #define n0 100 struct node { int data; int llink,rlink; }; node tree[n0+1]; int root; //树的根节点位置 //递归方式实现前序，中序，后序遍历 void preorder(int p) { if(!p) {//如果根节点不为空 cout<<tree[p].data; preorder(tree[p].llink); preorder(tree[p].rlink); } } void inorder(int p) { if(!p) {//如果根节点不为空 inorder(tree[p].llink); cout<<tree[p].data; inorder(tree[p].rlink); } } void postorder(int p) { if(!p) {//如果根节点不为空 postorder(tree[p].llink); postorder(tree[p].rlink); cout<<tree[p].data; } } //非递归算法的前序，中序，后序遍历 //前序列的算法思想 ：从二叉树的根节点开始，令指针变量P指向根节点，访问当前节点p，并将p压入栈中。 //然后令p指向当前指向节点的左孩子节点。若p不为空，继续访问当前节点p，并将p压入栈中。如此反复直到p为空 //从栈中弹出栈顶元素赋给指针变量p，并令p指向它的右孩子节点，重复上述过程，当p为空，并且栈也为空时候，遍历结束。 void preorder() { int s[n0+1]; //栈 int t; //栈指针 int p = root;//树指针 while(p||t) {//当p不为空或者栈不为空时 if(p) {//当期指针不为空时候 cout<<tree[p].data; //访问当前节点 s[++t] = p; //当前地址入栈 p = tree[p].llink; //p指向p的左孩子 } else {//如果p指向的p的左孩子为空，就是没有左孩子 p = s[t--];//p返回到它的父亲节点 p = tree[p].rlink; //p指向它的父亲节点的右孩子 } } } //中序算法：和前序算法基本上一致，但是数据访问在出栈的时候 //前序列的算法思想 ：从二叉树的根节点开始，令指针变量p指向根节点，访问当前节点p，并将p压入栈中。 //然后令p指向当前指向节点的左孩子节点。若p不为空，继续访问当前节点p，并将p压入栈中。如此反复直到p为空 //从栈中弹出栈顶元素赋给指针变量p，并令p指向它的右孩子节点，重复上述过程，当p为空，并且栈也为空时候，遍历结束。 void preorder() { int s[n0+1]; //栈 int t; //栈指针 int p = root;//树指针 while(p||t) {//当p不为空或者栈不为空时 if(p) {//当期指针不为空时候 s[++t] = p; //当前地址入栈 p = tree[p].llink; //p指向p的左孩子 } else {//如果p指向的p的左孩子为空，就是没有左孩子 p = s[t--];//p返回到它的父亲节点 cout<<tree[p].data; //访问当前节点 p = tree[p].rlink; //p指向它的父亲节点的右孩子 } } } //后序遍历 //算法思路：当遇到非空的二叉树时候，首先将根节点地址和该节点的“右子树没有遍历”标记压入栈，然后沿 //左子数下降去遍历根节点的左子树，当遇到空二叉树时候，也就是这个节点没有左子树了，弹出栈顶元素， //取得这个节点根节点的位置和，该根节点的右子树是否已经遍历的标记。 //1如果右子树已经遍历，就访问这个根节点。 //2如果右子树没有遍历，就把这个根节点的地址和这个根节点的“右子树已经遍历”的标记，压入栈中。然后沿 //右子树去遍历这个根节点的右子树。 //s[t] > 0 ：此节点右子树没有遍历 //s[t] < 0 : 此节点右子树已经遍历 void postorder() { int s[n0+1]; //栈 int t = 0; //栈指针 int p = root;//p指向当前节点 while(p||t) {//当当前指针不为空 或者 栈不为空的时候 if(p) {//如果当前指针不为空 s[++t] = p ;//同时p>0表示这个节点的右孩子还没有被遍历 p = tree[p].llink; //沿着左孩子向下遍历 } else {//如果当期指针为空了，表示栈顶节点的左孩子为空 if(s[t]<0) {//如果这个栈顶节点的右孩子被访问过了 p = -s[t--]; //出栈，得到当前节点的父亲节点的地址 cout<<tree[p].data; //访问根节点 } else {//如果栈顶节点的右孩子没有被访问过 s[t] = -s[t]; //表示栈顶节点的右孩子已经被遍历过了 p = s[t]; // p = tree[s[t]]->rlink; } } } } |
|
|
