非递归算法求二叉树兄弟结点，大佬能否画个图，或者让我理解

大可爱

主要是不理解堆栈的作用，结点进栈退栈。

1. //二叉树根结点为T
   
2. //请利用二叉树遍历的非递归算法写出求二叉树中由指针q所指结点(设q所指
   
3. //结点不是二叉树的根结点)的兄弟结点的算法
   
4. // 若二叉树中存在该兄弟结点，算法给出该兄弟结点的位置
   
5. //否则算法给出NULL
   
6. //算法核心思想：
   
7. //利用二叉树的前序遍历的非递归算法解决该问题。
   
8. //在遍历过程中，当访问一个结点时，判断该结点的左孩子或右孩子是否时q指结点，若是，返回该结点的左孩子或者右孩子的位置即可
   
9. BTREE FINDBROTHER(BTREE T,BTREE q)
   
10. {
    
11.         //T 为二叉树根结点所在链结点的地址
    
12.         BTREE STACK[M],p =T;
    
13.         int top = -1;
    
14.         do
    
15.         {
    
16.                 while (p != NULL)
    
17.                 {
    
18.                         if(p -> lchild == q)
    
19.                         {return p->rchild;
    
20.                         }
    
21.                         if(p->rchild==q)
    
22.                         {return p->lchild;//访问当前p指的结点
    
23.                         }
    
24.                         STACK[++top] = p;//当前p指的结点的地址进栈
    
25.                         p = p->lchild; //将p移动其左孩子结点
    
26.                 }
    
27.                 p = STACK[top--];        //退栈
    
28.                 p = p->rchild;                 //将p移动到其右孩子结点
    
29.         } while(p != NULL||top!=-1);
    
30. }

复制代码

°希作先生丶

我先用语言描述一下你看看能不能懂- =，前序遍历的原则是 根-左-右，按照这个原则， P一开始指向的是根节点，然后分别与它的左右孩子结点比较，若没有找到则把指针移动向左孩子指针，并把P进栈，移动向左孩子指针就是要遍历左子树结点，而把P入栈可以理解成把它暂存起来，如果左子树没有找到的话就再把它拿出来并遍历它的右子树，即之后的P退栈，并移动向右孩子结点，之后的操作就是一直重复这个过程- =。