非递归算法求二叉树兄弟结点，大佬能否画个图，或者让我理解
主要是不理解堆栈的作用，结点进栈退栈。//二叉树根结点为T
//请利用二叉树遍历的非递归算法写出求二叉树中由指针q所指结点(设q所指
//结点不是二叉树的根结点)的兄弟结点的算法
// 若二叉树中存在该兄弟结点，算法给出该兄弟结点的位置
//否则算法给出NULL
//算法核心思想：
//利用二叉树的前序遍历的非递归算法解决该问题。
//在遍历过程中，当访问一个结点时，判断该结点的左孩子或右孩子是否时q指结点，若是，返回该结点的左孩子或者右孩子的位置即可
BTREE FINDBROTHER(BTREE T,BTREE q)
{
//T 为二叉树根结点所在链结点的地址
BTREE STACK,p =T;
int top = -1;
do
{
while (p != NULL)
{
if(p -> lchild == q)
{return p->rchild;
}
if(p->rchild==q)
{return p->lchild;//访问当前p指的结点
}
STACK[++top] = p;//当前p指的结点的地址进栈
p = p->lchild; //将p移动其左孩子结点
}
p = STACK; //退栈
p = p->rchild; //将p移动到其右孩子结点
} while(p != NULL||top!=-1);
} 我先用语言描述一下你看看能不能懂- =，前序遍历的原则是 根-左-右，按照这个原则， P一开始指向的是根节点，然后分别与它的左右孩子结点比较，若没有找到则把指针移动向左孩子指针，并把P进栈，移动向左孩子指针就是要遍历左子树结点，而把P入栈可以理解成把它暂存起来，如果左子树没有找到的话就再把它拿出来并遍历它的右子树，即之后的P退栈，并移动向右孩子结点，之后的操作就是一直重复这个过程- =。
页:
[1]