二叉树创建以及基本操作

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TreeNode
{
	struct TreeNode* left;
	struct TreeNode* right;
	char data;
}bTree;
//创建二叉树
bTree* createTree();
//前序遍历递归
void preOrder1(bTree* bt);

//中序递归遍历
void onOrder1(bTree* bt);

//后序递归遍历
void postOrder1(bTree* bt);

void preOrder2(bTree* bt);

void onOrder2(bTree* bt);

void postOrder3(bTree* bt);

bool isSame(bTree* bt1, bTree* bt2);

bool isSonTree(bTree* bt1,bTree* bt2);

int getDepth(bTree* bt);

void levelOrder(bTree* bt);

bool isBalance(bTree* bt);

bool isSymmetric(bTree* bt);

bool isChildSymmetric(bTree* bt1,bTree* bt2);

#define _CRT_SECURE_NO_WARNINGS
#include "BTree.h"
#include <iostream>
#include <stack>
#include <queue>
using namespace std;



bTree* createTree()
{
	bTree* root = NULL;
	char ch;
	scanf("%c", &ch);
	if (ch != '#')
	{
		root = (bTree*)malloc(sizeof(bTree));
		if (root == NULL)
		{
			return NULL;
		}
		root->data = ch;
		root->left = createTree();
		root->right = createTree();
	}	
	return root;

}

void preOrder1(bTree* bt)
{
	//assert(bt);
	if (bt)
	{
		printf("%c ", bt->data);
		preOrder1(bt->left);
		preOrder1(bt->right);
	}
}

void onOrder1(bTree* bt)
{
	if (bt)
	{
		onOrder1(bt->left);
		printf("%c ", bt->data);
		onOrder1(bt->right);
	}
}

void postOrder1(bTree* bt)
{
	if (bt)
	{
		postOrder1(bt->left);
		postOrder1(bt->right);
		printf("%c ", bt->data);

	}
}

void preOrder2(bTree* root)
{
	stack<bTree*> s;
	bTree* bt = root;
	if (bt == NULL)
	{
		return;
	}
	while (bt || !s.empty())
	{
		while (bt)
		{
			printf("%c ", bt->data);
			s.push(bt);
			bt = bt->left;
		}
		if (bt == NULL)
		{
			bt = s.top();
			s.pop();
			bt = bt->right;
		}
	}
}

void onOrder2(bTree* bt)
{
	if (bt == NULL)
		return;
	stack<bTree*> s;
	bTree* p = bt;
	while (p || !s.empty())
	{
		while (p)
		{
			s.push(p);
			p = p->left;
		}
		if (p == NULL)
		{
			p = s.top();
			printf("%c ", p->data);
			s.pop();
			p = p->right;
		}
	}
}

/*
* 保证根节点是最后遍历的，就要把根节点存起来
*	两种情况下可以访问根节点：
*	    当前节点没有左右孩子的时候
*	    当前节点有左右孩子，但是左右孩子已经被访问/遍历过的时候
*	其余的情况，也就是左右孩子没有被访问过，需要先将右孩子入栈，再将左孩子入栈，
	这样可以保证 左在右 之前出栈访问

	A && (B || C) 等价于
	A && B || A && C
*/
void postOrder3(bTree* bt)
{
	stack<bTree*> s;
	bTree* p = bt;		//p代表当前节点
	bTree* pre = NULL;	//pre代表前一个访问过的节点

	s.push(p);			//先将根节点入栈
	while (!s.empty())
	{
		p = s.top();
		if ((p->left == NULL && p->right == NULL) || (pre != NULL && (pre == p->left || pre == p->right)))
		{
			printf("%c ", p->data);//先访问
			s.pop();				//再出栈
			pre = p;				//最后保存当前节点
		}
		else
		{
			//有左右孩子，并且未被访问过，将他们分别入栈
			if (p->right)
				s.push(p->right);
			if (p->left)
				s.push(p->left);
		}
	}
}

bool isSonTree(bTree* bt1, bTree* bt2)//判断bt2是否为bt1的子树
{
	if (bt1 == NULL || bt2 == NULL)//都为空，则不是
	{
		return false;
	}
	
	if (isSame(bt1,bt2))//递归判断左子树和右子树，和bt2比较
		return true;

	return isSonTree(bt1->left, bt2) && isSonTree(bt1->right, bt2);
}

int getDepth(bTree* bt)
{
	if (bt == NULL)//空树，相当于0层
		return 0;
	
	int left_depth = getDepth(bt->left);//递归求出左右子树的高度
	int right_depth = getDepth(bt->right);

	if (left_depth > right_depth)
		return left_depth+1;//判断左右子树哪个大，要加上最上面的根节点
	else
		return right_depth+1;

}

//依次把树中节点入队
//队列不空的情况挨个出队并访问
//然后判断是否有左右孩子，如果有则都入队
void levelOrder(bTree* bt)
{
	if (bt == NULL)
		return;
	bTree* p = bt;
	queue<bTree*> q;
	q.push(p);
	while (!q.empty())
	{
		p = q.front();
		printf("%c ", p->data);
		q.pop();
		
		if (p->left)
			q.push(p->left);
		if (p->right)
			q.push(p->right);
	}
}

bool isSame(bTree* bt1, bTree* bt2)
{	
	if (bt1 == NULL && bt2 == NULL)//两个都空，相同
		return true;
	if ((bt1 == NULL && bt2 != NULL) || (bt1 != NULL && bt2 == NULL))//一个空，一个不空，说明不相同
		return false;
	if (bt1->data == bt2->data)//比较数据域
		return true;

	return isSame(bt1->left, bt2->left) && isSame(bt1->right, bt2->right);	
	//两棵树，左边和左边比，右边和右边比，两边都相同才相同
}

//需要分别求出左右子树的高度，然后做差
bool isBalance(bTree* bt)
{
	if (bt == NULL)
		return true;
	int left_height = getDepth(bt->left);
	int right_height = getDepth(bt->right);
	int x = abs(left_height - right_height);

	return x <= 1 && isBalance(bt->left) && isBalance(bt->right);
}

//先判断根节点，然后再判断左右子树是否相同
bool isSymmetric(bTree* bt)
{
	if (bt == NULL) //单独判断根节点
	{
		return true;
	}

	if (isChildSymmetric(bt->left, bt->right))//然后再用一个函数判断根节点的左右子树
		return true;
}

bool isChildSymmetric(bTree* bt1,bTree* bt2)//和判断两棵树是否相同，一样的代码
{
	if (bt1 == NULL && bt2->right == NULL)
		return true;

	if (bt1== NULL && bt2 != NULL || bt2 == NULL && bt1 != NULL)
		return false;

	if (bt1->data != bt2->data)
		return false;

	return isChildSymmetric(bt1->left, bt2->left) && isChildSymmetric(bt1->right, bt2->right);
}


void test01()
{
	bTree* tree = createTree();
	//if (tree == NULL)
	//	return;
	//CreateBiTree1(&tree);
	//preOrder1(tree);
	printf("\n");
	preOrder2(tree);
	printf("\n");
	onOrder1(tree);
	printf("\n");
	onOrder2(tree);
	printf("\n");
	postOrder1(tree);
	printf("\n");
	postOrder3(tree);
	printf("\n");
	levelOrder(tree);
	//ABD##E##CF##G##

	printf("\n");
	printf("二叉树的高度是：%d", getDepth(tree));
}



int main(void)
{
	test01();
	return 0;
}