数据结构笔记——二叉树的基操，遍历、求高、查找、插入

🍎🍚蒟蒻的笔记二叉树笔记，感谢中国大学MOOC数据结构与算法实战的周强老师。 （后序遍历没讲，还就内个不会。）

//能用C++的stack和queue了，情结工。 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef struct Node* BinTree;
struct Node
{
	int Data;
	BinTree Left;
	BinTree Right;
};
//前序遍历（递归） 
void rPreorder(struct Node* BT) 
{
	if(BT==NULL)
	{
		printf("NULL\n"); return ;
	}
	printf("%d ",BT->Data);
    if(BT->Left)	rPreorder(BT->Left);
	if(BT->Right) rPreorder(BT->Right);
}
//前序遍历（迭代）大禹治水，三过家门而不入。前序指第一次过家门就入，先输出再压栈。中序则第二次，压栈完等弹栈再输出。后序则压栈完等弹栈等再压栈的时候输出？不会，蒟蒻石锤。 
void iPreorder(BinTree BT)
{
	if(BT==NULL)
	{
		printf("NULL\n"); return ;
	}
	stack  st;
	while(BT)
	{
		printf("%d ",BT->Data);
		st.push(BT);
		BT = BT->Left; //还就内个一路向左/向左常态化 
		while(BT==NULL&&!st.empty()) //如果为空，跳到上一个点然后向右。 
		{
			BT=st.top();
			st.pop();
			BT=BT->Right;
		}
	}
	puts("\n");
}
//中序遍历（递归） 
void rInorder(BinTree BT)
{
	if(BT==NULL)
	{
		printf("NULL\n");
		return ;
	}
	if(BT->Left) rInorder(BT->Left);
	printf("%d ",BT->Data);
	if(BT->Right) rInorder(BT->Right);
}
//中序遍历（迭代） 
void iInorder(BinTree BT)
{
	if(BT==NULL)
	{
		printf("NULL\n"); return ;
	}
	stack  st;
	while(BT)
	{
		//中序与前序的区别在于输出位置 
		st.push(BT);
		BT = BT->Left; //还就内个一路向左/向左常态化 
		while(BT==NULL&&!st.empty()) //如果为空，跳到上一个点然后向右。 
		{
			BT=st.top();
			st.pop();
			printf("%d ",BT->Data);
			BT=BT->Right;
		}
	}
	puts("\n");
	
}
//后序遍历（递归） 
void rLaterorder(BinTree BT)
{
	if(BT==NULL)
	{
		printf("NULL\n");
		return ;
	}
	if(BT->Left) rLaterorder(BT->Left);
	if(BT->Right) rLaterorder(BT->Right);
	printf("%d ",BT->Data);
}
//层次遍历（队列：先进先出/后进后出||数组模拟/感谢强哥） 
void Levelorder(BinTree BT)
{
	if(BT== NULL)
	{
		printf("NULL\n");
		return ; 
	}
    queue st;//入队，找把左右儿子入队，然后输出并出队，下一个继续，直到队为空。 
    st.push(BT); 
	while(!st.empty()) //队列不空 
	{
		printf("%d ",st.front()->Data);
		if(st.front()->Left) st.push(st.front()->Left);
		if(st.front()->Right) st.push(st.front()->Right);
		st.pop();
	}
	//模拟队列/感谢强哥 
    /*
	BinTree a[777]; BinTree ttemp;// ttemp用来存放队伍头
	int i,g; i = g = 0;
	a[i++] = BT;
	while(i!=g) //这个写法就很妙，入队是用i计数、出队用g计数，所有入队以后的元素反正都得出队，那么当二者相等，就相当于全部读取完毕。
	{
	 ttemp = a[g++];
	 printf("%d ",ttemp->Data);
	 if(ttemp->Left) a[i++] = ttemp->Left;
	 if(ttemp->Right) a[i++] = ttemp->Right;
    }
    */
}
//创建节点 
BinTree CreatNode(int root) 
{
	BinTree temp = (BinTree) malloc(sizeof(struct Node));
	temp->Data = root;
	temp->Left = temp->Right = NULL;
	return temp;
}
//求二叉树的高度 
int GetHight(BinTree BT)
{
	if(BT==NULL) return 0 ;
	int left = GetHight(BT->Left);
	int right = GetHight(BT->Right);
	if(left>right) return left+1;
	else return right+1;
}
//查找二叉树中的值 
BinTree rFindX(BinTree BT,int X)
{
	if(!BT) return NULL;
	if(BT->Data == X) return BT;
	BinTree found;
	found = rFindX(BT->Left,X);
	return found ? found : rFindX(BT->Right,X);
}
//强哥之插入
void Insert(BinTree BT,int LorR,int bin ,int data) //插入的树、左儿子还是右儿子、在哪个结点后边插入、要插入的数据 
{

	if(!BT) return ;
	BinTree found  = rFindX(BT,bin);//找 
		if(!found ) return;
		else 
		{
			if(LorR == 0)
			{
				if(found->Left == NULL) found->Left = CreatNode(data);
				else return ;
			}
			else 
			{
				if(found->Right == NULL) found->Right = CreatNode(data);
				else return ;
			}
		}
	
} 
int main (void)//测试
{
	BinTree BT = CreatNode(11);//先有根结点以后再插入 
	Insert(BT,0,11,22);
	Insert(BT,1,11,33);
	Insert(BT,0,22,44);
	Insert(BT,1,33,55);
	rInorder(BT); puts("\n");
	iInorder(BT);
	//Levelorder(BT);
	//int hight = GetHight(BT); printf("\n%d",hight);
	return 0 ;
}

树的结构，有点简单QAQ。 后续有望更新数组模拟栈的迭代遍历、后序遍历、BST。