二叉树的各种操作

二叉树的各种操作
1、树的递归遍历
2、求二叉树中节点的个数
3、求二叉树中叶子节点的个数
4、求二叉树的深度
5、求第k层节点数
6、树的非递归遍历
7、求一棵二叉树的镜像
8、判断两棵树的结构是否相同
9、判断一棵树是否平衡
10、将二叉查找树变为有序的双向链表

下面是树的结构：

typedef struct treeNode {
	int data;
	struct treeNode* left;
	struct treeNode* right;
}Tree;
#define  max(a,b) (((a)>(b))?(a):(b))

1、树的递归遍历

void pre_traverse(Tree *T)    //前序遍历
{
	if (T)
	{
		printf("%d",T->data);
		if (T->left)
			pre_traverse(T->left);
		if (T->right)
			pre_traverse(T->right);
	}
}

void mid_traverse(Tree *T)    //中序遍历
{
	if (T)
	{
		if (T->left)
			mid_traverse(T->left);
		printf("%d",T->data);
		if (T->right)
			mid_traverse(T->right);
	}
}

void beh_traverse(Tree *T)    //后序遍历
{
	if (T)
	{
		if (T->left)
			beh_traverse(T->left);
		if (T->right)
			beh_traverse(T->right);
		printf("%d",T->data);
	}
}

void level_traverse(Tree* T)           //层次遍历
{
	queue<int>q;
	if (T) {
		q.push(T->data);
		while(!q.empty()) {
			printf("%d",q.front());
			q.pop();
			if (T->left)q.push(T->left->data);
			if (T->right)q.push(T->right->data);
		}
	}
}

2、求二叉树中节点的个数

int getNodes(Tree *T)  
{
	if (T == NULL)
		return 0;
	else
		return getNodes(T->left) + getNodes(T->right) + 1;
}

3、求二叉树中叶子节点的个数

int getLeafNodes(Tree* T)   
{
	if (T == NULL)
		return 0;
	if (T->left == NULL && T->right == NULL)
		return 1;
	int leftLeafNodes = getLeafNodes(T->left);
	int rightLeafNodes = getLeafNodes(T->right);
	return leftLeafNodes + rightLeafNodes;
}

4、求二叉树的深度

int Depth(Tree *T)  
{
	if (T == NULL)
		return 0;
	else
		return max(Depth(T->left), Depth(T->right)) + 1;
}

5、求第k层节点数

int getLevelNodes(Tree *T,int k)   
{
	if (T == NULL || k==0)
		return 0;
	if (k == 1)
		return 1;
	return getLevelNodes(T->left, k - 1) + getLevelNodes(T->right,k-1);
}

6、树的非递归遍历

void preOrdertrvael(Tree *T)   //非递归前序遍历
{
	if (T == NULL)return;
	stack<Tree*>s;
	Tree *temp=T;
	s.push(temp);
	while (!s.empty())
	{
		temp = s.top();
		printf("%d\n",temp->data);
		s.pop();
		if (T->right)
			s.push(T->right);
		if (T->left)
			s.push(T->left);
	}
}

void midOrdertravel(Tree *T)    //非递归中序遍历
{
	if (T == NULL)return;
	stack<Tree*>s;
	Tree *temp = T;
	
	while (temp != NULL || !s.empty())
	{
		if (temp) {
			s.push(temp);
			temp = temp->left;
		}
		else {
			temp = s.top();
			s.pop();
			printf("%d",temp->data);
			temp = temp->right;
		}
	}
}

void postOrdertravel(Tree *T)   //非递归后序遍历
{
	if (T == NULL)return;
	stack<Tree*>s1;
	stack<Tree*>s2;
	Tree *temp = T;
	s1.push(temp);
	while (!s1.empty())
	{
		temp = s1.top();
		s1.pop();
		s2.push(temp);
		if (temp->left)
			s1.push(temp->left);
		if (temp->right)
			s1.push(temp->right);
	}
	while (!s2.empty())
	{
		temp = s2.top();
		printf("%d",temp->data);
		s2.pop();
	}
}

void levelOrdertravel(Tree *T) //树的非递归层次遍历
{
	if (T == NULL)
		return;
	queue<Tree*>q;
	Tree* temp = T;
	q.push(temp);
	while (!q.empty())
	{
		temp = q.front();
		printf("%d",temp->data);
		if (temp->left)
			q.push(temp->left);
		if (temp->right)
			q.push(temp->right);
	}
}

7、求一棵二叉树的镜像

Tree* MirrorTree(Tree *T)  
{
	if (T == NULL)
		return;
	Tree* pLeft = MirrorTree(T->left);
	Tree* pRight = MirrorTree(T->right);
	T->left = pRight;
	T->right = pLeft;
	return T;
}

8、判断两棵树的结构是否相同

bool CompareTreeStruct(Tree *T1, Tree *T2)   
{
	if (T1 == NULL && T2 == NULL)
		return true;
	if (T1 != T2)
		return false;

	bool leftResult = CompareTreeStruct(T1->left,T2->left);
	bool rightResult = CompareTreeStruct(T1->right,T2->right);
	return leftResult && rightResult;
}

9、判断一棵树是否平衡

bool isAvl(Tree* T)         
{
	int depth;
	return isAvlTree(T,depth);
}

bool isAvlTree(Tree *T,int depth)
{
	int leftDepth, rightDepth;
	if (T == NULL) {
		depth = 0;
		return true;
	}

	if (isAvlTree(T->left, leftDepth) && isAvlTree(T->right, rightDepth))
	{
		if (abs(leftDepth - rightDepth) <= 1) {
			depth = max(leftDepth,rightDepth)+1;
			return true;
		}
	}
	return false;
}

10、将二叉查找树变为有序的双向链表

void TreeToList(Tree* T, Tree* &pFirst, Tree* &pLast) 
{
	Tree* pLeftFirst(NULL), *pLeftLast(NULL), *pRightFirst(NULL), *pRightLast(NULL);
	if (T == NULL) {
		pFirst = NULL;
		pLast = NULL;
		return;
	}

	if (T->left == NULL) {
		pFirst = T;
	}
	else {
		TreeToList(T->left, pLeftFirst, pLeftLast);
		pLeftLast->right = T;
		T->left = pLeftLast;
		pFirst = pLeftFirst;
	}

	if (T->right == NULL) {
		pLast = T;
	}
	else {
		TreeToList(T->right, pRightFirst, pRightLast);
		pRightFirst->left = T;
		T->right = pRightFirst;
		pLast = pRightFirst;
	}
}