不使用递归,如何遍历一颗树?

我这里所谓的"树"说的是UI里的树形控件,我不想用递归去遍历他的每个结点.

// 这是该树形控件的结点
struct SITEM
{
	SITEM*	pParent;	// 父项
	SITEM*	pRoot;	// 子项的根项(如果没有子项，则pRoot的pNext和pPrev都指向pRoot)
	SITEM*	pPrev;	// 前一项
	SITEM*	pNext;	// 下一项
};

12 个解决方案

#1

用栈或者几个指针都是可以的啊

#2

引用 1 楼 keeya0416 的回复:

用栈或者几个指针都是可以的啊

最好不要用栈等任何第3方存储结构，而只用纯C代码,即循环.分支等语句

#3

引用楼主 weiwuyuan 的回复:

我这里所谓的"树"说的是UI里的树形控件,我不想用递归去遍历他的每个结点.

C/C++ code


// 这是该树形控件的结点
struct SITEM
{
    SITEM*    pParent;    // 父项
    SITEM*    pRoot;    // 子项的根项(如果没有子项，则pRoot的pNext和pPrev都指向pRoot)
    SITEM……

你的前一项，后一项指的是什么？楼主这样表示一棵树。我不能明白！

#4

希望楼主赐教下！

#5

我说的树主要是树形控件里的树,
前一项:前一个兄弟
后一项:后一个兄弟
和pRoot则是子项的根

#6

知道链表吧?

我这个根链表有点相似,链表就是有root,prev,next
而我把"root,prev和next"作为一个结点,即每个结点都可以知道上一个兄弟是谁，下一个兄弟是谁，以及他的子项是什么,如果没有子项,则root->prev和root->next都指向root

#7

你的树结构定义有问题，前一个、后一个是什么？
是不是可以定义为：
struct SITEM
{
    struct SITEM*    pParent;    // 父项
    struct SITEM*    lChild;    // 左孩子指针
     struct SITEM*    rChild;    // 右孩子指针
     int Data;
};

#8

引用 7 楼 changchengz 的回复:

你的树结构定义有问题，前一个、后一个是什么？
是不是可以定义为：
struct SITEM
{
  struct SITEM* pParent; // 父项
  struct SITEM* lChild; // 左孩子指针
  struct SITEM* rChild; // 右孩子指针
  int Data;
};

不是，
我的定义的确和通常所说的“树”不太一样，我是用链表的描述方式去定义的。

再说一下：
pRoot是儿子指针
pPrev是上一个兄弟指针
pNext是下一个兄弟指针

#9

写出来了，很简单的几行代码：

void Test(SITEM* pItemRoot)
{
	SITEM* pCur = pItemRoot->pRoot->pNext;
	SITEM* pNext = NULL;

	while (pCur != pItemRoot->pRoot)
	{
		// 当前项是根项
		if (pCur == pCur->pParent->pRoot)
		{
			pCur = pCur->pParent->pNext;
			continue;
		}

		// 这里可以读取当前项数据
		// ...

		// 无子项
		if (pCur->pRoot->pNext == pCur->pRoot)
		{
			assert(pCur->pParent != NULL);
			pNext = pCur->pNext;

			// 若下一项是最后一项,则从上一层的下一项继续遍历
			if (pNext == pCur->pParent->pRoot)
				pCur = pCur->pParent->pNext;
			else
				pCur = pNext;
		}
		// 有子项,则进入到该子项的起始项
		else
		{
			pCur = pCur->pRoot->pNext;
		}
	}
}

#10

上楼的大大，想请教下流程图描述算法的原理，小弟没有积分帖，只有跟帖了，请多多指教！

#11

引用 10 楼 nclghaihai 的回复:

上楼的大大，想请教下流程图描述算法的原理，小弟没有积分帖，只有跟帖了，请多多指教！

我是菜鸟一个，不知何为流程图,何为算法原理

#12

用一次递归，你会受益无穷！