困扰了一周的有关问题,总是不对,大家帮小弟我看看
困扰了一周的问题,总是不对,大家帮我看看
//后序非递归遍历二叉树
void PostOrderIter() //二叉树非递归后序遍历
{
const int s = 100;
BinaryTreeNode * tempStack[s];
BinaryTreeNode * cur;
cur = root;
int top = -1;
while (top != -1 || cur!=NULL)
{
while (cur !=NULL)
{
top ++;
tempStack[top] = cur;
if (cur-> lChild != NULL)
{
cur = cur-> lChild;
}
else
{
cur = cur-> rChild;
}
}
cur = tempStack[top];
top -- ;
cout < < cur-> element < < " ";
while (top != -1 && tempStack[top]-> rChild == cur)
{
cur = tempStack[top--];
cout < <cur-> element < < " ";
}
if (top!=-1)
{
cur=tempStack[top]-> rChild;
}
else
{
cur = NULL;
}
}
}
-----------------
遍历代码在上面,节点结构如下:
class BinaryTreeNode
{
public:
int element;
BinaryTreeNode *lChild, *rChild;
//默认构造函数
BinaryTreeNode(){};
//带有三个参数的构造函数
BinaryTreeNode(int elem,BinaryTreeNode* left = NULL,BinaryTreeNode* right = NULL)
:element(elem),lChild(left),rChild(right){};
};
后序遍历如下的树,结果就是不对:
7
/ \
5 5
/ \ / \
3 43 4
请大家帮帮!
------解决方案--------------------
帮楼主顶吧
------解决方案--------------------
感觉是你的两颗子树使用了同一个对象。就是那两个 "5 "所代表的子树根节点,是否在构造时用了同一个?因为遍例函数中是使用指针来分辩左子树/右子树的。如果指针值相等。那么完成左子树时会被误认为完成了右子树的遍例。
因为没有看过你建树的代码,所以不敢肯定,这是感觉,说错勿怪。
//后序非递归遍历二叉树
void PostOrderIter() //二叉树非递归后序遍历
{
const int s = 100;
BinaryTreeNode * tempStack[s];
BinaryTreeNode * cur;
cur = root;
int top = -1;
while (top != -1 || cur!=NULL)
{
while (cur !=NULL)
{
top ++;
tempStack[top] = cur;
if (cur-> lChild != NULL)
{
cur = cur-> lChild;
}
else
{
cur = cur-> rChild;
}
}
cur = tempStack[top];
top -- ;
cout < < cur-> element < < " ";
while (top != -1 && tempStack[top]-> rChild == cur)
{
cur = tempStack[top--];
cout < <cur-> element < < " ";
}
if (top!=-1)
{
cur=tempStack[top]-> rChild;
}
else
{
cur = NULL;
}
}
}
-----------------
遍历代码在上面,节点结构如下:
class BinaryTreeNode
{
public:
int element;
BinaryTreeNode *lChild, *rChild;
//默认构造函数
BinaryTreeNode(){};
//带有三个参数的构造函数
BinaryTreeNode(int elem,BinaryTreeNode* left = NULL,BinaryTreeNode* right = NULL)
:element(elem),lChild(left),rChild(right){};
};
后序遍历如下的树,结果就是不对:
7
/ \
5 5
/ \ / \
3 43 4
请大家帮帮!
------解决方案--------------------
帮楼主顶吧
------解决方案--------------------
感觉是你的两颗子树使用了同一个对象。就是那两个 "5 "所代表的子树根节点,是否在构造时用了同一个?因为遍例函数中是使用指针来分辩左子树/右子树的。如果指针值相等。那么完成左子树时会被误认为完成了右子树的遍例。
因为没有看过你建树的代码,所以不敢肯定,这是感觉,说错勿怪。