二叉树，查找某一节点的祖先节点，c/c++描述

  查找某一节点的祖先节点，递归思路是，若某一节点的左右子节点即为所求，则输出该根节点，结束递归不再查找。否则递归其左右两棵子树，若其左右两棵子树里能找到所需节点，则仍输出该节点，作为所求节点的祖先节点。遇到空节点直接返回上层函数。这里函数会递归调用本身多次，每次在函数体里，查找核对的是根节点的左右子节点。并不核对根节点本身是否是所求节点。那么我们会有疑问，这样的查找是否是不重不漏呢？答案是确保了不重不漏的。因为每次在函数体里启用递归，对剩余的二叉树继续查找时，都已经确定了本函数里的形参根节点，要么不存在子节点，要么形参根节点的子节点都不是所求，所以才要启动递归，对剩余的二叉树继续查找。直到形参根节点为null或者找到为止。函数名findAncestor。
  全部代码如下：

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

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

			if (biTreeRoot == NULL)
				biTreeRoot = ptNew;
			else if (leftRight == 1)
				stack.nodes[stack.indexTop]->leftChild = ptNew;
			else if (leftRight == 2)
				stack.nodes[stack.indexTop]->rightChild = ptNew;
		}
		else if (c == '(') {
			stack.indexTop++;
			stack.nodes[stack.indexTop] = ptNew;
			leftRight = 1;
		}
		else if (c == ',')
			leftRight = 2;
		else if (c == ')')
			stack.indexTop--;
		
		ptChar++;
		c = *ptChar;
	}
}
void displayBiTree(BiTreeNode *&biTreeRoot) {
	if (biTreeRoot == NULL)
		return;
	cout << biTreeRoot->value;
	if (biTreeRoot->leftChild != NULL || biTreeRoot->rightChild != NULL) {
		cout << '(';
		displayBiTree(biTreeRoot->leftChild);
		if (biTreeRoot->rightChild != NULL) {
			cout << ',';
			displayBiTree(biTreeRoot->rightChild);
		}
		cout << ')';
	}
}
bool findAncestor(BiTreeNode *&biTreeRoot,char c) {
	if (biTreeRoot == NULL)
		return false;
	if (biTreeRoot->leftChild != NULL && biTreeRoot->leftChild->value == c ||
		biTreeRoot->rightChild != NULL && biTreeRoot->rightChild->value == c) {
		cout << biTreeRoot->value<< ' ';
		return true;
	}
	if (findAncestor(biTreeRoot->leftChild,c) ||
		findAncestor(biTreeRoot->rightChild,c)) {
		cout << biTreeRoot->value << ' ';
		return true;
	}
	else
		return false;
}

int main() {
	char arrayA[] = "A(B,C(D,E(,M)))";
	BiTreeNode* biTreeA = NULL;
	
	char* ptChar = arrayA;
	creatBiTree(biTreeA,ptChar);

	cout << "arrayA   ; ";
	for (ptChar = arrayA; *ptChar != '\0'; ptChar++)
		cout << *ptChar;

	cout << endl <<"biTree A ; "; displayBiTree(biTreeA); cout << endl;
	
	char c;
	cout << "input the char whose ancestors you want to find :";
	cin >> c;

	if (findAncestor(biTreeA, c)) {}
	else
		cout << "such node is not in this tree .";
		
	return 0;
}

  测试结果如下：

谢谢阅读。