二叉树的结构设计：

typedef char ElemType;
typedef struct BtNode {
	struct BtNode* left;//左节点
	struct BtNode* right;//右节点
	ElemType data;//数据域
}BtNode,*BinaryTree;

二叉树的遍历方式：
1.前序遍历
访问根节点
前序遍历左子树
前序遍历右子树

void Psoder(BtNode* ptr)
{
	cout<<ptr->data;
	PsOder(ptr->left);
	PsOder(ptr->right);
}

2.中序遍历
中序遍历左子树
访问根节点
中序打印右子树

void Inoder(BtNode* ptr)
{
	InOder(ptr->left);
	cout<<ptr->data;
	InOder(ptr->right);
}

3.后续遍历
后续遍历左子树
后序遍历右子树
访问根节点

void Lsoder(BtNode* ptr)
{
	LsOder(ptr->left);
	cout<<ptr->data;
	LsOder(ptr->right);
}

创建二叉树：

struct BtNode* CreateTree()
{
	ElemType item;//定义一个ElenType(char)类型的字符串
	struct BtNode* s = NULL;//构建一个结构体S
	cin >> item;//输入我们要构建的二叉树比如ABC##DE##F##G#H##
	if (item != END)//如果字符不等于END
	{
		s = buynode();//首先购买一个节点
		s->data = item;//将这个节点的数据域赋值为第一个字符
		s->left = CreateTree();//递归调用左孩子域
		s->right = CreateTree();//递归调用右孩子域
	}
	return s;
}

struct BtNode* CreateTree2(const char *&pstr)//输入我们要构建的二叉树比如ABC##DE##F##G#H##
{
	struct BtNode* s = NULL;
	if (*pstr != NULL && *pstr != END)
	{
		s = buynode();
		s->data = *pstr;
		s->left = CreateTree2(++pstr);
		s->right = CreateTree2(++pstr);
	}
	return s;
}

非递归遍历二叉树
思想：构建一个栈来对它进行操作,首先判断字符串是否为空，如果为空直接return，如果不为空，首先构建一个栈空间。
判断字符串是否为空或者栈满，如果二者中其一，退出。
否则，先将根节点入栈，然后入栈左节点，直到左节点为空时，退出循环。
打印节点值然后压栈右节点,如果有节点的值为空的话，不执行while循环，直接弹出栈。
中序遍历：

void NiceInoder(BtNode* ptr)
{
	if(ptr==NULL) return;
	stack<BtNode*> st;
	while(ptr!=NULL||!st.empty())
	{
		while(ptr!=NULL)
		{
			st.push(ptr);
			ptr=ptr->left();
		}
		ptr=st.top();st.pop()
		ptr=ptr->right;
	}
}

后续遍历：
思想：设置一个标志位tag为空，首先判断字符串是否为空或是否栈满
当字符串不为空时，压栈，字符串指向左节点
当左节点压完后，说明左节点压完，弹出节点值，但是此时不能直接打印这个值
还需要判断它的右节点是否为空或者字符串指向的右孩子域是否为tag，如果为tag说明已经遍历过这个右孩子域。
如果为空说明它的左右孩子已经遍历完成，打印节点值。tag指向字符值，字符指向空
如果字符没有指向空，那么在下一轮循环中字符还是指向这个节点，那么就会将这个节点再次入栈弹出打印
如果它的右孩子不为空说明还没有遍历完，将这个节点再次入栈，然后将它指向它的右节点

void NicePsorder(BtNode* ptr)
{
	if(ptr==NULL) return;
	stack<BtNode*> st;
	BtNode* tag=NULL;//标志位
	while(ptr!=NULL||!st.empty())
	{
		while(ptr!=NULL)
		{
			st.push(ptr);
			ptr=ptr->left;
		}//当这个循环结束，左孩子已经遍历到最后一个
		ptr=st.top();st.pop();//将这个节点从栈中弹出
		if(ptr->right==NULL||ptr->right==tag)//如果命中说明右孩子为空
		{
			cout<<ptr->data;
			tag=ptr;//让tag指向ptr
			ptr==NULL//ptr置为空，防止死循环
		}
		else//说明右孩子不为空
		{
			st.push(ptr);//将该节点重新入栈
			ptr=ptr->right;//遍历右孩子
		}
	}
}

先序遍历
思想:构建一个栈，先将根节点入栈，打印
然后将它的右节点入栈，再将左节点入栈，这是因为先入栈的后出，所以我们先将右节点入栈再将左节点入栈，这样出的时候是左节点先出栈，然后是右节点出栈

void NicePsoder(BtNode *ptr)
{
	if(ptr==NULL) return;
	stack<BtNode*> st;
	st.push(ptr);
	while(ptr!=NULL||!st.empty())
	{
		ptr=st.top();st.pop();
		cout<<ptr->data;
		if(ptr->right!=NULL)
		{
			st.push(ptr->right);
		}
		if(ptr->left!=NULL)
		{
			st.push(ptr->left);
		}
	}
}

层次遍历
思想：构建一个队列,先将根节点入栈弹出打印，然后将该节点的左节点和右节点依次入栈，每次遍历一个节点都将它的左右节点依次入栈

void NiceLeveLorder(BtNode* ptr)
{
	if(ptr==NULL) return;
	queue<BtNode*> que;
	que.push(ptr);
	while(!que.empty())
	{
		ptr=que.front();que.pop();//去除队列头指针，移除
		cout<<ptr->data;
		if(ptr->left!=NULL)
		{
			que.push(ptr->left);
		}
		if(ptr->right!=NULL)
		{
			que.push(ptr->right);
		}
	}
}

"之"字形层次遍历
思想：定义两个栈Lst,Rst来实现，先将ptr入Lst栈，然后判断Lst是否为空，如果不为空，出栈，打印
，然后先将左节点Rst再将右节点入Rst,如果Lst为空，退出循环
判断Rst是否为空，如果不为空，弹出栈顶指针并移除，打印。然后将右孩子和左孩子依次入栈Lst
第一个循环判断不为空入栈的方式是因为打印根节点后，需要从右边开始打印，所以先入左孩子，再入右孩子，弹出时先弹出右孩子，再弹出左孩子
第二个循环的入栈方式是因为，要从左往右打印，所以先入右孩子再入左孩子

void ZNiceLeveLorder(BtNode* ptr)
{
	if(ptr==NULL) return;
	stack<BtNode*> Lst;
	stack<BtNode*> Rst;
	Lst.push(ptr);
	while(!lst.empty()||!rst.empty())
	{
		while(!lst.empty())
		{
			ptr=lst.top();;st.pop();
			cout<<ptr->data;
			if(ptr->left!=NULL)
			{
				rst.push(ptr->left);
			}
			if(ptr->right!=NULL)
			{
				rst.push(ptr->right);
			}
		}
		while(!rst.empty())
		{
			ptr=rst.top();rst.pop();
			cout<<ptr->data;
			if(ptr->right!=NULL)
			{
				lst.push(ptr->right);
			}
			if(ptr->left!=NULL)
			{
			lst.push(ptr->left);
			}
		}
	}
}

利用前序和中续遍历后续
思想：判断ps和is长度是否相等，如果相等进入函数。定义一个BtNode*类型的变量s等于空
如果N>0，说明长度不为0，首先购买一个节点，然后将它的data域赋值为先序的第一个字符，也就是先序的根节点，递归遍历它的左孩子。每次遍历时，先序的根节点都在变化，往前移一个位置，此时所要找的范围就是pos的大小
如果先序遍历到空，则开始递归遍历右节点，先序遍历的时候需要从ps+pos+1的位置开始遍历（ps+pos是根节点的位置）,后续列表也要从is+pos+1的位置开始，那么它所要遍历的范围就是n-pos-1

int findis(char* is, int n, char val)
{
	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (is[i] == val)
		{
			pos = i;
			break;
		}
	}
	return pos;
}
BtNode* createpi(char* ps,char* is,int n)
{
	BtNode *s=NULL;
	if(n>0)
	{
		s=buynode();
		s->data=ps[0];
		int pos=finds(is,n,ps[0]);
		if(pos==-1) exit(EXIT_FAILURE);
		s->left=createpi(ps+1,is,pos);
		s->right=createpi(ps+pos+1,is+pos+1,n-pos-1);
	}
	return s;
}
BtNode* createtreepi(char* ps,char* is,int n)
{
	BtNode*s=NULL;
	if(ps!=NULL&&is!=NULL&&n>0)
	{
		s=createpi(ps,is,n);
	}
	return s;
}
int main()
{
	BinaryTree root = NULL;
	char ps[] = "ABCDEFGH";
	char is[] = "CBEDFAGH";
	int psn = strlen(ps);
	int isn = strlen(is);
	if (psn == isn)
	{
		root = CreateTreepi(ps, ls, psn);
	}
}

利用先序和中序推演后序

int findis(char* is, int n, char val)
{
	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (is[i] == val)
		{
			pos = i;
			break;
		}
	}
	return pos;
}
BtNode* createil(char* is, char* ls, int n)
{
	BtNode* s = NULL;
	if (n > 0)
	{
		s = buynode();
		s->data = ls[n - 1];
		int pos = findis(is, n, ls[n-1]);
		if (pos == -1) exit(EXIT_FAILURE);
		s->left = createil(is, ls, pos);
		s->right = createil(is + pos + 1, ls + pos, n - pos - 1);
	}
	return s;
}
BtNode* createtreeil(char* is, char* ls, int n)
{
	BtNode* root = NULL;
	if (is != NULL && ls != NULL && n > 0)
	{
		root = createil(is, ls, n);
	}
	return root;
}
int main()
{
	BinaryTree root = NULL;
	char is[] = "CBEDFAGH";
	char ls[] = "CEFDBHGA";
	int isn = strlen(is);
	int lsn = strlen(ls);
	if (lsn == isn)
	{
		root = createtreeil(is, ls, lsn);
	}
}

获取二叉树的节点个数

int findcount(BtNode* ptr)
{
	if(ptr==NULL) return ;
	else return findcount(ptr->left)+findcount(ptr->right)+1;
}

获取二叉树的深度

int get_depth(BtNode* ptr)
{
	if (ptr == NULL) return 0;
	//else return std::max(get_depth(ptr->left), get_depth(ptr->right))+1;
	int len1 = get_depth(ptr->left);
	int len2 = get_depth(ptr->right);
	return  len1 > len2 ? len1+1 : len2+1;
}