线索二叉树的建立（C/C++语言，非递归）

主要还是参考王道的C语言督学营，给自己做个笔记，方便以后复习吧，虽然以后这种简单的代码也许我可以随手写出来。递归更简单，但是我真的理解不了。

题目：读取10个元素 87  7 60 80 59 34 86 99 21  3，然后建立二叉查找树，中序遍历输出3  7 21 34 59 60 80 86 87 99

#define _CRT_SECURE_NO_WARNINGS//vs2019中要用scanf要有这个接口
#include
#include

//读取10个元素 87  7 60 80 59 34 86 99 21  3，
//然后建立二叉查找树，中序遍历输出3  7 21 34 59 60 80 86 87 99，
//针对有序后的元素，存入一个长度为10的数组中，
//通过折半查找找到21的下标（下标为2），然后输出2


//数据无重复
//定义树的节点
typedef struct BiTNode {
	int data;
	struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree;

bool BiTInsert(BiTree &tree, int key) {//tree为将要插入的树，key为要插入的值//其实这个函数中我有点理解不了为什么tree传进来是二级指针。我的C语言太差了。希望以后能理解
	BiTree pcur=tree;//pcur为当前插入节点
	BiTree pparent=NULL;//pparent为当前插入节点的父节点

	if (tree == NULL){//树中不存在元素，直接插入
		tree = (BiTree)calloc(1, sizeof(BiTNode));//tree只是一个指针，所以要申请节点，calloc和malloc的作用基本一致，但会为指针设定初始值为NULL
		tree->data = key;
		return true;
	}
	while (pcur != NULL) {//树中存在元素，找到待插入的节点
		if (pcur->data == key)//插入的元素已存在，则插入失败
			return false;
		if (pcur->data > key) {//当前节点的值比key大，则插入当前节点的左边
			pparent = pcur;
			pcur = pcur->lchild;//指向下一个节点
		}
		else//当前节点的值比key小，则插入当前节点的右边
		{
			pparent = pcur;
			pcur = pcur->rchild;//指向下一个节点
		}
	}

	//找到待插入节点的父节点后插入节点
	BiTree temp;//将要插入的节点
	temp = (BiTree)calloc(1, sizeof(BiTNode));//为插入的值申请树的节点
	temp->data = key;//将插入的值放到树的节点中，这个树的节点现在还是单独存在，还没有和树连在一起
	if (pparent->data > key)//判断插入的节点在父节点的左边还是右边
		pparent->lchild=temp;//将树连到树节点中
	else
		pparent->rchild=temp;
	return true;
}
//中序遍历输出二叉树,每个元素占3个字母位置
void InOrder(BiTree p) {
	if (p != NULL) {
		InOrder(p->lchild);
		printf("%d ", p->data);
		InOrder(p->rchild);
	}
}
//主函数
int main() {
	BiTree tree=NULL;//定义一棵树
	int d;//将要输入的元素
	for (int i = 0; i < 10; i++) {
		scanf("%d", &d);
		BiTInsert(tree, d);
	}
	InOrder(tree);
	return 0;
}