网络游戏排行榜前十名大型网络游戏_欧模网_外贸平台有哪些?_优化大师破解版app

打印值为x的节点的所有祖先

在二叉树中查找值为x的节点，试编写算法打印值为x的节点的所有祖先，假设值为x的节点不多于一个

算法思想

采用非递归后序遍历，最后访问根节点，访问到值为x的节点时，栈中所有元素均为该节点的祖先，依次出栈打印即可。

假设x是5，T入栈，沿左向下遍历，直到T指向NULL
依次将2，4也入栈，tag置为0，表示沿左子树访问

如果top不为0，将栈顶的节点的右孩子，并将tag置为1

由于4为NULL，没有右子树，将4出栈，接着访问2
将5入栈，找到值为x的节点，从栈底开始输出栈内的元素

typedef struct
{BTNode root;// tag=0表示左子女被访问，tag=1表示右子女被访问int tag;
}stack;
// 在二叉树T中，查找值为x的节点，并打印其所有祖先
void Search(BTNode T, ElemType x)
{// 栈的容量足够大ST s[];top = 0;while (T != NULL || top > 0){// 节点入栈while (T != NULL && T->data != x){s[++top].root = T;s[top].tag = 0;// 沿左分支向下T = T->left;}if (T != NULL && T->data == x){// 找到xprintf("所查节点的所有祖先节点的值为：\n");for (i = 1; i <= top; i++){// 遍历输出栈中的节点的值printf("%d", s[i].root->data);}exit(1);}while (top != 0 && s[top].tag == 1)// 退栈top--;if (top != 0){s[top].tag = 1;// 沿右分支向下遍历T = s[top].root->right;}}
}

1. 栈的结构定义：
   • 使用一个栈s来存储节点信息，每个元素包含：
     • 节点指针BTNode t。
     • 标志位tag：
       • tag = 0：表示从左子树访问。
       • tag = 1：表示从右子树访问。
2. 从根节点开始遍历：
   • 遇到一个节点时，将其入栈并沿左子树向下遍历。
3. 找到目标节点：
   • 如果当前节点 T 的值为 x，遍历栈中的所有节点，打印其值（这些节点即为目标节点的祖先）。
4. 回溯过程：
   • 如果当前节点没有右子树或者右子树已经被访问过（tag == 1），弹出栈顶节点。
   • 如果当前节点的右子树尚未访问，访问右子树并继续遍历。
5. 结束条件：
   • 找到目标节点后直接退出程序。
   • 如果遍历完整棵树未找到目标节点，循环退出。
     注意点
6. 栈的实现
   • 栈的容量应足够大以存储整棵树的所有节点（通常不会超过树的深度）。
   • 栈指针top用于操作栈。
7. 边界处理：
   • 如果T为NULL或遍历完成后未找到x，则程序结束。
8. 遍历方式：
   • 代码中采用非递归后序遍历：
     • 沿左子树向下直到找到目标节点或遍历完成。
     • 回溯并访问右子树，直至找到目标节点。

最近公共祖先节点

设一棵二叉树的结点结构为（LLINK，INFO，RLINK），ROOT为指向该二叉树根结点的指针，P和分别为指向该二叉树中任意两个结点的指针，试编写算法ANCESTOR（ROOT，P，a，r），找到p和q的最近公共祖先结点r。
12

算法思想

后序遍历最后访问根节点，在递归算法中，根是压在栈底的。设p在q的左边
采用后序非递归算法，栈中存放二叉树节点的指针，当访问到某节点时，栈中所有元素均为该节点的祖先。后序遍历必然先遍历到节点p，栈中元素均为p的祖先。
先将栈复制到另一个辅助栈中。继续遍历到节点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配的元素就是节点p和q的最近公共祖先。

typedef struct
{BTNode root;//tag=0表示左子女已被访问，tag=1表示右子女已被访问int tag;
}stack;
// 栈，容量足够大
ST s[], s1[];
// 求二叉树中p和q指向节点的最近公共节点
BTNode Ancestor(BTNode root, BTNode *p, BTNode *q)
{top = 0; top1 = 0; BTNode cur = root;while (cur != NULL || top > 0){// 沿左分支向下while (cur != NULL){s[++top].root = cur;s[top].tag = 0;cur = cur->left;}// 假定p在q左侧，遇到p时，栈中元素均为p的祖先while (top != 0 && s[top].tag == 1){// 将栈s中的元素转入辅助栈s1中保存if (s[top].root == p){for (i = 1; i <= top; i++){s1[i] = s[i];}top1 = top;}// 找到q节点if (s[top].root == q){// 将栈s中元素和s1中的去匹配for (i = top; i > 0; i--){for (j = top1; j > 0; j--){// 找到p和q的最近公共祖先if (s1[j].root == s[i].root)return s[i].root;}}}// 退栈top--;}// 沿右分支向下遍历if (top != 0){s[top].tag = 1;cur = s[top].root->right;}}// p和q无公共祖先return NULL;
}

• 核心思想：
  • 使用一个栈 s 进行非递归遍历，记录遍历过程中每个节点的路径。
  • 当遇到节点 p 时，将当前路径保存到辅助栈 s1。
  • 当遇到节点 q 时，将当前路径与 s1 中的路径匹配，找到最近的公共祖先节点。
• 主要流程：
  • 沿左分支向下遍历：不断压入节点及其状态（左子女是否访问）。
  • 遇到节点 p：保存路径到 s1。
  • 遇到节点 q：将当前路径与 s1 中的路径对比，找到最近的公共祖先。
  • 右子树遍历和回溯：继续沿右子树遍历，或回溯到父节点。