树的定义

树形结构：一对多的结构

注意：第一层下标为0。

二叉树的概念

（递归定义）

左右孩子也是二叉树
左子树和右子树的数据互不相交！

二叉树的定义

满二叉树

证明：n0=n2+1
解：因为 n=n0+n1+n2 ，分枝数：一个结点针对一个分枝，2 * n2+ 1n1=L。根节点由root指向，分枝和root没关系。即n=2n2+1*n1+1。所以将两式结合。得出：n0=n2+1

完全二叉树

注意：是从右向左依次缺少若干个结点。

证明：

二叉树的存储结构(3种)

1、顺序存储结构
（用于堆排序）

对二叉树，从上到下，从左到右，依次编号，即作为数组的下标。

上图是二叉树的逻辑结构。
下图是二叉树的存储结构。

逻辑结构就是你画的图。存储结构就是把数据存在内存中，也叫做物理结构。

我们所谓的逻辑结构和物理结构有映射关系！！！
答：在这里，如何描述这个关系？
一种数学关系。
1、父与子的关系： 当某个结点在数组的i下标。它的左子树下标：2 * i+1,它的右子树下标：2*i+2。
2、子与父的关系：子的下标是j，父的下标就是(j-1)/2 。
这就是关系！！！

顺序存储方式对完全二叉树是非常可以的。但是对普通二叉树不大好。
普通二叉树仿照完全二叉树来存放。

编号即作为数组的下标，没有数据，我们拿空代表空。
极端情况下，如果这个程序光有右子树，无左子树，会造成空间的大量浪费！！！
如果都把数据左移，节省空间，但是打乱了关系！

2、链式存储结构


a图是二叉树的逻辑表示。b,c是二叉树的物理表示。

二叉链表和三叉链表各有各的好处：
如果要找G的双亲，对于三叉链表可以直接找到，时间复杂度O（1）, 对于二叉链表，找G的双亲并不容易。
但是三叉链表和二叉链表的存储密度不一样。对于三叉链表来说，它的存储密度比较小，浪费了空间。而二叉链表的存储密度比较高。

3、静态结构

a图是逻辑结构。右边的表格是物理结构。
下图代表的是关系。

二叉树的结构定义

typedef char ElemType;
typedef struct BtNode 
{
	BtNode* leftchild;
	BtNode* rightchild;
	ElemType data;
}BtNode, * BinaryTree;

如何对二叉树进行遍历？

三角形代表先序遍历
ABCDE

圆代表中序遍历
CBDAE

正方形代表后序遍历
CDBEA

中序遍历
若二叉树为空，则结束；
否则：中序遍历左子树；访问根节点；中序遍历右子树。
如果没有中序两个字，就变成非递归了。

如果根节点不为空，我们中序遍历它的左孩子。

左孩子是二叉树，如果不为空，再去中序遍历它的左孩子。（递归概念）
中序遍历到C的左孩子，为空，返回到根节点B，遍历B的右孩子，右孩子为空，返回到根节点B，返回到B的时候，它左右边都遍历完了，访问根节点，中序遍历A的右孩子。

写出下图的前，中，后序遍历

前序遍历：ABCDEFGH
中序遍历：CBEDFAGH
后序遍历：CDEFBHGA

实际上中序遍历还有一种规则：
我们的根节点A在中间，它的左右是BG。
BAG
B的两边是C,D
CBDAG
D的两边是E，F
CBEDFAG
G的两边是H
CBEDFAGH

代码如下：

void PreOrder(BtNode* ptr)//前序遍历 
{
	if (ptr != nullptr)
	{
		cout << ptr->data << " ";//先访问根节点 
		PreOrder(ptr->leftchild);//访问左孩子 
		PreOrder(ptr->rightchild);//访问右孩子 
	}
}
void InOrder(BtNode* ptr)//中序遍历 
{
	if (ptr != nullptr)
	{
		InOrder(ptr->leftchild);//先访问左孩子
		cout << ptr->data << " ";//访问根节点 
		InOrder(ptr->rightchild);//访问右孩子 
	}
}
void PastOrder(BtNode* ptr)//后序遍历 
{
	if (ptr != nullptr)
	{
		PastOrder(ptr->leftchild);//访问左孩子 
		PastOrder(ptr->rightchild);//访问右孩子 
		cout << ptr->data << " ";//最后访问根节点 
	}
}

p指向A，不空，指向左边的B，B不空，指向C，C不空，再去指向C的左孩子，为空了，返回，打印C，然后访问C的右孩子为空，退回来，退回到B，B访问它的右孩子，就是D，然后依次访问下去。

如何创建二叉树？

1、用先序遍历和中序遍历来创建二叉树
先序遍历：ABCDEFGH
中序遍历：CBEDFAGH

对于先序遍历的第一个元素A，就是根节点，我们把A提出来，建立根节点A，我们要建立它的左右子树，我们就拿A在中序序列里去找，A在中序序列的下标为5，A前面有5个数据，我们把先序序列的BCDEF和中序序列CBEDF分别作为A左子树的先序遍历，中序遍历，GH是A的右子树的先序遍历，中序遍历。现在的数据量由8变成5，B也是我们所谓的根节点，以它作为根，在中序序列找到它的下标，C是左子树，DEF是右子树，以此类推。

BtNode* Buynode()//购买结点 
{
	BtNode* s = (BtNode*)malloc(sizeof(BtNode));
	if (nullptr == s) exit(1);
	memset(s, 0, sizeof(BtNode));
	return s;
}

int FindIs(const char* is, int n, ElemType val)//找位置 
{
	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (is[i] == val)
		{
			pos = i;
			break;
		}
	}
	return pos;
}

BtNode* CreatePI(const char* pr, const char* is, int n)
//先序，中序，n个数据 
{
	BtNode* s = nullptr;
	if (n > 0)
	{
		s = Buynode();
		s->data = pr[0]; //根节点
		int pos = FindIs(is, n, pr[0]);
		if (pos == -1) exit(1);
		s->leftchild = CreatePI(pr + 1, is, pos);
	    //递归调用的时候，这个pr要指向B了，is还是指向原来位置，数量变成5个了，就是pos的数值量
		s->rightchild = CreatePI(pr+pos+1,is+pos+1,n-pos-1);
		//右边要指向G
	}
	return s;
}

BtNode* CreateTreePI(const char* pr, const char* is)
{
	if (pr == nullptr || is == nullptr) return nullptr;
	int pn = strlen(pr);
	int in = strlen(is);
	if (pn != in) return nullptr;

	return CreatePI(pr, is, pn);
}
int main()
{
	BinaryTree root = nullptr;
	char pr[] = { "ABCDEFGH" };//先序遍历 
	char is[] = { "CBEDFAGH" };//中序遍历 
	char ps[] = { "CEFDBHGA" };//后序遍历 
	root = CreateTreePI(pr, is);
	NicePreOrder(root);
	NiceInOrder(root);
	NicePastOrder(root);
	return 0;
}
	

运行程序

2、用中序遍历和后序遍历进行创建二叉树
中序序列：CBEDFAGH
后序序列：CEFDBHGA

后序序列的最后一个元素就是根节点A，在中序序列找到A的下标为5，A在中序序列中前面有5个元素，即左子树。

BtNode* Buynode()//购买结点 
{
	BtNode* s = (BtNode*)malloc(sizeof(BtNode));
	if (nullptr == s) exit(1);
	memset(s, 0, sizeof(BtNode));
	return s;
}

int FindIs(const char* is, int n, ElemType val)//找位置 
{
	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (is[i] == val)
		{
			pos = i;
			break;
		}
	}
	return pos;
}

BtNode* CreateIP(const char* is, const char* ps, int n)
//中序，后序，数据个数 
{
	BtNode* s = nullptr;
	if (n > 0)
	{
		s = Buynode();
		s->data = ps[n - 1];//最后一个元素，即根节点
		int pos = FindIs(is, n, ps[n - 1]);//查找位置
		if (pos == -1) exit(1);
		s->leftchild = CreateIP(is, ps, pos);
		s->rightchild = CreateIP(is + pos + 1, ps + pos, n - pos - 1);
	}
	return s;
}

BtNode* CreateTreeIP(const char* is, const char* ps)
{
	if (is == nullptr || ps == nullptr) return nullptr;
	int in = strlen(is);
	int pn = strlen(ps);
	if (in != pn) return nullptr;
	return CreateIP(is, ps, in);
}
int main()
{
	BinaryTree root = nullptr;
	char pr[] = { "ABCDEFGH" };//先序遍历 
	char is[] = { "CBEDFAGH" };//中序遍历 
	char ps[] = { "CEFDBHGA" };//后序遍历 
	root = CreateTreeIP(is, ps);
	NicePreOrder(root);
	NiceInOrder(root);
	NicePastOrder(root);
	return 0;
}

运行程序

拿先序和后序无法创建二叉树，没有办法分割成左右

如果二叉树中数据有重复，就会创建出多种二叉树

非递归的中序遍历

我们首先定义一个栈，我们开始遍历树，这个树不空，我们把A入栈，然后访问A的左边，B不空，B入栈，B的左边不空，C入栈，然后访问C的左边，空了，把C出栈，访问C的右边，右边为空，这个结点访问完了，退回到B，出B，B的右子树不空，把D入栈，访问D的左边，E入栈，访问E的左边，为空，退回来，E出栈，访问E的右边，D出栈，右边不空，F入栈，F的左边空，F出栈，F的右边空，退回到A，A出栈，A的右边不为空，继续下去。

void NiceInOrder(BtNode* ptr)//非递归的中序遍历 
{
	if (ptr == nullptr) return;
	std::stack<BtNode*> st;
	while(ptr != nullptr || !st.empty())
	{ 
		while (ptr != nullptr)
		{
			st.push(ptr);
			ptr = ptr->leftchild;
		}
		ptr = st.top(); st.pop();
		cout << ptr->data << " ";
		ptr = ptr->rightchild;
    }
	cout << endl;
}

非递归的后序遍历

我们增加一个标志指针。
最开始tag=nullptr；

首先我们把A入栈，把B入栈，把C入栈，然后C的左边是空，把C出栈，但是后序遍历的规则是访问了C的左边和右边才打印C，我们怎么知道已经访问了C的右边呢？如果它的右子树等于这个标记，我们就可以打印C，打印完C，标记跟到C，把ptr指针置为空，意味着C要出栈了。B出栈，B的右边不空，不等于标志位，B入栈，D入栈，E入栈，E的左边为空，退出，把E出栈，如果E的右边为空，打印E，标志位指向E，ptr置为空，D出栈，D的右边不空，不等于标志位，把D入栈，ptr指向F，F入栈，以此类推。

void NicePastOrder(BtNode* ptr)//非递归的后序遍历 
{
	if (ptr == nullptr) return;
	BtNode* tag = nullptr;//标志指针 
	std::stack<BtNode*> st;
	while (ptr != nullptr || !st.empty())
	{
		while (ptr != nullptr)
		{
			st.push(ptr);
			ptr = ptr->leftchild;
		}
		ptr = st.top(); st.pop();
		if (ptr->rightchild == nullptr || ptr->rightchild == tag)
		{ 
			cout << ptr->data << " ";
			tag = ptr;
			ptr = nullptr;
		}
		else
		{
			st.push(ptr);
			ptr = ptr->rightchild;
		}
	}
	cout << endl;
}

非递归的先序遍历

我们首先把A入栈，栈不空，把A出栈，打印A，先右再左入，就是先左再右出！！！

void NicePreOrder(BtNode* ptr)//非递归的先序遍历 
{
	if (ptr == nullptr) return;
	std::stack<BtNode*> st;
	st.push(ptr);
	while (!st.empty())
	{
		ptr = st.top(); st.pop();
		cout << ptr->data << " ";
		if (ptr->rightchild != nullptr)
		{
			st.push(ptr->rightchild);
		}
		if (ptr->leftchild != nullptr)
		{
			st.push(ptr->leftchild);
		}
	}
	cout << endl;
}