c++ 遍历二叉树（基本二叉树方法）

【实例截图】

【核心代码】

# include <stdio.h>
# include <malloc.h>

typedef char ElemType;

typedef struct BitNode{
	ElemType data;
	struct BitNode * lChild;
	struct BitNode * rChild;
}BitNode, *BitSortTree;

BitNode * creatBitSortTree();		//构建二叉排序树
void traverseTree(BitSortTree);		//遍历二叉树

int main(void) {
	
	BitSortTree bst = creatBitSortTree();

	traverseTree(bst);

	return 0;
}

BitNode * findPos(BitSortTree bst, char findElem) {
	BitNode * preNode = bst;	//记录前驱节点
	while(bst != NULL) {
		preNode = bst;
		if(bst->data > findElem) {
			bst = bst->lChild;
		} else {
			bst = bst->rChild;
		}
	}
	return preNode;
}

BitNode * creatBitSortTree() {
	int num;
	printf("输入需要创建多少个节点：");
	scanf("%d", &num);
	ElemType * arr = (ElemType *)malloc(sizeof(ElemType));
	for(int index=0; index<num; index  ) {
		printf("请输入第%d个节点：", index 1);
		getchar();
		scanf("%c", &arr[index]);
	}
/*
	for(int index=0; index<num; index  ) {
		printf("%c ", arr[index]);
	}
*/
	//根据序列创建排序树并返回
	BitNode * bst = NULL;

	for(int index=0; index<num; index  ) {	//寻找位置，并添加
		if(bst == NULL) {
			bst = (BitNode *)malloc(sizeof(BitNode));
			bst->data = arr[index];
			bst->lChild = NULL;
			bst->rChild = NULL;
			continue;
		}
		BitNode * preNode = findPos(bst, arr[index]);
		BitNode * tmptNode = (BitNode *)malloc(sizeof(BitNode));
		tmptNode->data = arr[index];
		tmptNode->rChild = NULL;
		tmptNode->lChild = NULL;
		if(preNode->data > arr[index]) {
			preNode->lChild = tmptNode;
		} else {
			preNode->rChild = tmptNode;
		}
	}

	return bst;
}

void traverseTree(BitSortTree bst) {
	if(NULL == bst) {
		printf("# ");
		return;
	}
	printf("%c ", bst->data);
	traverseTree(bst->lChild);
	traverseTree(bst->rChild);
}