[数据结构与算法]输出根节点到叶节点的所有路径，后序遍历，非递归，c/c++描述

??对二叉树的遍历操作是其他一切操作的基础，如查找，比较。本例中要求遍历二叉树节点时，遇到了叶节点就输出根节点到叶节点的路径。程序是在后序遍历非递归的程序基础上稍加修改而来的。前面文章里已详细写了后序遍历非递归的程序。此处就不再对遍历思路详细叙述。
??函数createBiTree：建立二叉树；函数displayBiTree输出二叉树的逗号表达式，以检验建立过程；函数allPathRootToLeafPostOrder输出根节点到叶节点的所有路径。
??完整代码如下，先是main函数所在源文件：

#include<iostream>
#include<stdio.h>
using namespace std;
#define STACKDEPTH 15
struct BiTreeNode {
	char value;
	BiTreeNode* leftChild;
	BiTreeNode* rightChild;
};
extern void createBiTree(BiTreeNode*& biTreeRoot, char* ptChar);
extern void displayBiTree(BiTreeNode*& biTreeRoot);
extern void allPathRootToLeafPostOrder(BiTreeNode*& biTreeRoot);
int main() {
	char array[] = "A(B(D(,G)),C(E,F))";
	BiTreeNode* biTreeRoot = NULL;

	createBiTree(biTreeRoot,array);
	cout << "the char array is :";
	for (int i = 0; array[i] != '\0'; i++)
		cout << array[i];
	cout<< endl<< "binary tree is    :";
	displayBiTree(biTreeRoot);

	cout <<endl<<endl<< "all path from root to leaf : " << endl;
	allPathRootToLeafPostOrder(biTreeRoot);

	return 0;
}

??接着是各函数所在源文件：

#include<iostream>
#include<stdio.h>
using namespace std;
#define STACKDEPTH 15
struct BiTreeNode {
	char value;
	BiTreeNode* leftChild;
	BiTreeNode* rightChild;
};
void createBiTree(BiTreeNode*& biTreeRoot, char* ptChar) {
	struct {
		BiTreeNode* ptsBiTree[STACKDEPTH];
		int indexTop = -1;
	}sequStack;

	BiTreeNode* ptNew = NULL;
	char s;
	int leftRight;//1 is left   2 is right
	while (*ptChar != '\0') {
		s = *ptChar;
		if ('A' <= s && s <= 'Z') {
			ptNew = new BiTreeNode;
			ptNew->value = s;
			ptNew->leftChild = ptNew->rightChild = NULL;

			if (biTreeRoot == NULL)
				biTreeRoot = ptNew;
			else if (leftRight == 1)
				sequStack.ptsBiTree[sequStack.indexTop]->leftChild = ptNew;
			else if (leftRight == 2)
				sequStack.ptsBiTree[sequStack.indexTop]->rightChild = ptNew;
		}
		else if (s == '(') {
			sequStack.indexTop++;
			sequStack.ptsBiTree[sequStack.indexTop] = ptNew;
			leftRight = 1;
		}
		else if (s == ',')
			leftRight = 2;
		else if (s == ')')
			sequStack.indexTop--;

		ptChar++;
	}
}
void displayBiTree(BiTreeNode*& biTreeRoot) {   // 本查找方法是先序遍历
	if (biTreeRoot == NULL)
		return;//if binary tree does not exsit,return
	cout << biTreeRoot->value;
	if (biTreeRoot->leftChild != NULL || biTreeRoot->rightChild != NULL) {
		cout << '(';
		displayBiTree(biTreeRoot->leftChild);
		if (biTreeRoot->rightChild != NULL) {
			cout << ',';
			displayBiTree(biTreeRoot->rightChild);
		}
		cout << ')';
	}
}

void allPathRootToLeafPostOrder(BiTreeNode*& biTreeRoot) {
	if (biTreeRoot == NULL)
		return;

	BiTreeNode* nodes[STACKDEPTH],*pt,*ptPopped = NULL;
	int indexTop = 0, pathCount = 0;
	nodes[indexTop] = biTreeRoot;
	bool checkLeftChild = true;

	while (indexTop >= 0) {
		pt = nodes[indexTop];
		while (checkLeftChild && pt->leftChild != NULL) {
			indexTop++;
			nodes[indexTop] = pt->leftChild;
			pt = pt->leftChild;
		}

		if (pt->rightChild == NULL && pt->leftChild == NULL) {
			pathCount++;
			cout << "path " << pathCount << " :";
			for (int i = 0; i <= indexTop; i++)
				cout << nodes[i]->value << " ";
			cout << endl;
		
			ptPopped = nodes[indexTop];
			indexTop--;

			checkLeftChild = false;
		}
		else if (pt->rightChild == NULL || pt->rightChild == ptPopped) {
			ptPopped = nodes[indexTop];
			indexTop--;
		}
		else {
			indexTop++;
			nodes[indexTop] = pt->rightChild;
			checkLeftChild = true;
			ptPopped = NULL;
		}
	}
}

??测试结果及对应二叉树如下：


谢谢阅读。