数据结构8-树、二叉树、森林、哈夫曼树

树

树型结构（非线性结构）

• 结点之间有分支
• 具有层次关系

树的定义：
树（Tree)是n(n≥0)个结点的有限集。
若n=0,称为空树；
若n>0,则它满足如下两个条件：
(1)有且仅有一个特定的称为根（Root)的结点；
(2)其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm,其中每一个集合本身又是一棵树，并称为根的子树（SubTree)。

树的基本术语：

树结构与线性结构比较

二叉树

为何要重点研究每结点最多只有两个“叉”的树？

• 二叉树的结构最简单，规律性最强；
• 可以证明，所有树都能转为唯一对应的二叉树，不失一般性。
• 普通树（多叉树）若不转化为二叉树，则运算很难实现
• 二叉树在树结构的应用中起着非常重要的作用，因为对二叉的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。

二叉树的定义
二叉树是n(n>=0)个结点的有限集，它或者是空集（n=0),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右
子树的二叉树组成。
特点
1、每个结点最多有俩孩子（二叉树中不存在度大于2的结点）。
2、子树有左右之分，其次序不能颠倒。
3、二叉树可以是空集合，根可以有空的左子树或空的右子树。

注:二叉树不是树的特殊情况，它们是两个概念。

• 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树世
  行区分，说明它是左子树，还是右子树。
• 树当结点只有一个孩子时，就无须区分它是左还是右的次序。因此
  二者是不同的。这是二叉树与树的最主要的差别。
  
  (也就是二叉树每个结点位置或者说次序都是固定的，可以是空，但是不
  可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的
  结点时，它就无所谓左右了）,
  
  

---

树和二叉树的抽象数据类型定义

树的一些基本操作：

二叉树的性质

满二叉树和完全二叉树

二叉树的存储结构

顺序存储

---

链式存储

二叉树的遍历

• 遍历定义——顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次（又称周游）。
  • “访问”的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。
• 遍历目的——得到树中所有结点的一个线性排列。
• 遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。
  

先序遍历

中序遍历

后序遍历

遍历算法分析

中序遍历的非递归算法

使用栈

二叉树的层次遍历

算法设计思路：使用一个队列

1. .将根结点进队；
2. 队不空时循环：从队列中出列一个结点*p,访问它；
   • 若它有左孩子结点，将左孩子结点进队；
   • 若它有右孩子结点，将右孩子结点进队。

二叉树遍历算法的应用

1. 二叉树的建立
   
   
2. 复制二叉树
   
3. 计算二叉树的深度
   
4. 计算二叉树的节点总数
   
5. 计算叶子节点数
   

二叉树的应用 线索二叉树

利用二叉链表中的空指针域：
如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；
如果某结点的右孩子为空，则将空的右孩子指针域改为指向其后继
——这种改变指向的指针称为“线索”
加上了线索的二叉树称为线索二叉树（Threaded Binary Tree)，对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化

为区分lrchid和rchild指针到底是指向孩子的指针，还是指向前驱或者后继的指针，对二叉链表中每个结点增设两个标志域Itag和rtag,并约定：
Itag=0 Ichild指向该结点的左孩子
ltag=1 lchild指向该结点的前驱
rtag=0 rchild指向该结点的右孩子
rtag=1 rchild指向该结点的后继

为了避免空指针：
增设了一个头结点：
Itag=0, lchild指向根结点，
rtag=1,rchild指向遍历序列中最后一个结点
遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点

二叉排序树（二叉查找树）

树上任意结点如果存在左子树和右子树，则左子树上所有结点元素的值都小于该结点，右子树上所有结点元素的值都大于该结点。

平衡二叉树

平衡二叉树(Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree)是一种二叉排序树，其中每一个节点的左子树和右子树的高度差不超过1。

如何构建一棵平衡二叉树

1. 本质上跟构建二叉排序树一致
2. 在构建二叉排序树的过程中，如果发现树不符合特性，需要进行调整。
   如何判断调整类型？
   1. 找到失衡树的根节点root
   2. 找到导致树失衡的节点node,'node在root的哪一侧
   3. 判断node在root孩子的哪一侧

四种情况：

• LL：取中间节点，将它父亲作为自己的右孩子，如果自己有右孩子的话，那么将自己的右孩子，连接到父亲的左孩子上面
• RR：取中间的节点，使它的父亲诚为它的左孩子，如果它有左孩子的话，那么这个左孩子连接到父亲的右孩子上面
• RL：取最后一个节点，作为父亲节点，将它原先的父亲作为自己的右孩子，将父亲的父亲作为自己的左孩子，如果自己有左孩子或者右孩子的话，自己原先的左孩子连接到父亲的父亲有孩子上，自己原先的右孩子连接到父亲的左孩子上
• LR：取最后一个节点，作为父节点，将它的父亲作为自己的左孩子，将它的父亲的父亲作为自己的右孩子，如果它有左孩子或者右孩子的话，它原先的左孩子，连接到父亲的右孩子上，它原先的右孩子，连接到父亲的父亲的左孩子上
  

树和森林

树的存储结构

双亲表示法

孩子链表

带双亲的孩子链表

孩子兄弟表示法

树与二叉树的转换

将树转换成二叉树

①加线：在兄弟之间加一连线
②抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
③旋转：以树的根结点为轴心，将整树顺时针转45°

树变二叉树：兄弟相连留长子

将二叉树转换成树:

①加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子……沿分支找到的所有右孩子，都与p的双亲用线连起来
②抹线：抹掉原二叉树中双亲与右孩子之间的连线
③调整：将结点按层次排列，形成树结构

二叉树变树：
左孩右右连双亲，
去掉原来右孩线。

森林转换成二叉树（二叉树与多棵树之间的关系）

①将各棵树分别转换成二叉树
②将每棵树的根结点用线相连
③以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

森林变二叉树：树变二叉根相连。

二叉树转化为森林

二叉树转换成森林
①抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所
有右孩子间连线全部抹掉，使之变成孤立的二叉树
②还原：将孤立的二叉树还原成树

二叉树变森林：去掉全部右孩线，孤立二叉再还原。

树与森林的遍历

森林的遍历

• 先序遍历：
  若森林不空，则
  1.访问森林中第一棵树的根结点；
  2.先序遍历森林中第一棵树的子树森林；
  3.先序遍历森林中（除第一棵树之外）其余树构成的森林。
  即：依次从左至右对森林中的每一棵树进行先根遍历。
• 中序遍历：
  若森林不空，则即：依次从左至右对森林中的每一棵树进行后根遍历。
  1.中序遍历森林中第一棵树的子树森林；
  2.访问森林中第一棵树的根结点；
  3.中序遍历森林中（除第一棵树之外）其余树构成的森林。
  

哈夫曼树

最优二叉树 ，即带权路径长度WPL最短的树
满二叉树不一定是哈夫曼树
哈夫曼树中权越大的叶子离根越近
具有相同带权结点的哈夫曼树不惟一

相关概念：

• 路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。
• 结点的路径长度：两结点间路径上的分支数。
• 树的路径长度：从树根到每一个结点的路径长度之和。记作：TL
  
• 权(weight)又称权重：将树中结点赋给一个有着某种含义的数值，(具体的意义根据树使用的场合确定)则这个数值称为该结点的权。
• 结点的带权路径长度：从根结点到该结点之间的路径长度与结点上权的乘积
• 结点的路径长度：两结点间路径上的分支数。
• 树的带权路径长度：树中所有叶子结点的带权路径长度之和。
• 树的路径长度：从树根到每一个结点的路径长度之和。
  

哈夫曼树的构造算法

哈夫曼树中权越大的叶子离根越近
贪心算法：构造哈夫曼树时首先选择权值小的叶子结点

• 包含 n 个叶子结点的哈夫曼树中共有2n-1个结点。
• 哈夫曼树的结点的度数为0或2,没有度为1的结点。
• 包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生/个新结点

总结：

1、在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最
终形成哈夫曼树。
2、经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个
孩子的分支结点。
可见：哈夫曼树中共有n+n-1=2n-1个结点，且其所有的分支结点
的度均不为1。

哈夫曼树算法的实现

采用顺序存储结构——一维结构数组
结点类型定义：

typedef struct
{
    int weight;
    int parent, Ich, rch;
}HTNode,*HuffmanTree;

哈夫曼树中共有2n-1个结点,不使用0下标，数组大小为2n

---

算法步骤:

1. 初始化数组：长度2n-1，lch=rch=parent=0；
2. 输入初始n个叶子节点：输入每个节点的权值
3. 进行以下n-1次合并，依次产生n-1个结点HT[i],i=n+1…2n-1:
   • 在HT[1…i-1]中选两个未被选过（从parent==0的结点中选）的weight最小的两个结点HT[s1]和HT[s2],s1、s2为两个最小结点下标；
   • 修改HT[s1]和HT[s2]的parent值：HT[s1].parent=i;HT[s2].parent=i;
   • 修改新产生的HT[i]:
     • HT[i].weight=HT[s1].weight+HT[s2].weight;
     • HT[i]. Ich=s1; HT[i]. rch=s2;

伪代码如下：

void CreatHuffmanTree(HuffmanTree HT,int n)
{
//构造哈夫曼树——哈夫曼算法
   if(n<=1)return;
   m=2*n-1;//数组共2n-1个元素
   HT=new HTNode[m+1];//0号单元未用，HT[m]表示根结点
   for(i=1;i<=m;++i)
   {
   		//将2n-1个元素的lch、rch、parent置为0
   		HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;
   }
   for(i=1;i<=n;++i) cin>>HT[i].weight;//输入前n个元素的weight值
   
   //初始化结束，下面开始建立哈夫曼树
   for(i=n+1;i<=m;i++)
   {
   		//合并产生n-1个结点——构造Huffman树
   		Select(HT,i-1,s1,s2);//在HT[k](1≤k≤i-1)中选择两个其双亲域为0
   		//且权值最小的结点，并返回它们在HT中的序号s1和s2
   		HT[s1].parent=i;HT[s2].parent=i;//表示从F中删除s1,s2
   		HT[i].lch=s1;HT[i].rch=s2;//s1,s2分别作为的左右孩子
   		HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子权值之和
   	}
}

哈夫曼编码的应用

代码部分

1. 二叉树

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 

//函数结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;


typedef char  ElemType;    
typedef struct TreeNode {
	ElemType data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

void createTree(TreeNode** T, char* data, int* index);

void preOrder(TreeNode* T);

void inOrder(TreeNode* T);

void postOrder(TreeNode* T);


//
//层次遍历
typedef struct QueueNode {
	TreeNode* data;
	struct QueueNode* pre;
	struct QueueNode* next;
}QueueNode;

QueueNode* initQueue();

void enQueue(TreeNode* data, QueueNode* Q);

int isEmpty(QueueNode* Q);

QueueNode* deQueue(QueueNode* Q);

void levelTraverse(QueueNode* Q, TreeNode* T);

//
//非递归遍历
typedef struct StackNode {
	TreeNode* data;
	struct StackNode* next;
}StackNode;

StackNode* initStack();

void push(TreeNode* data, StackNode* S);

int isEmpty(StackNode* S);

StackNode* pop(StackNode* S);

StackNode* getTop(StackNode* S);

void preOrder_noRecurs(TreeNode* T);

void inOrder_noRecurs(TreeNode* T);

void postOrder_noRecurs(TreeNode* T);
///
#include "BiTree.h"

void createTree(TreeNode** T, char* data, int* index) {
	char ch;
	ch = data[*index];
	*index += 1;
	if (ch == '#') {
		// 此时为空节点
		*T = NULL;
	}
	else {
		// 此时不为空
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		// 创建左子树，逻辑一致，进行递归
		createTree(&((*T)->lchild), data, index);
		// 创建右子树，逻辑一致，进行递归
		createTree(&((*T)->rchild), data, index);
	}
}

void preOrder(TreeNode* T) {
	if (T == NULL) {
		return;
	}
	else {
		// 先办事
		printf("%c ", T->data);
		// 处理左孩子
		preOrder(T->lchild);
		// 处理右孩子
		preOrder(T->rchild);
	}
}

void inOrder(TreeNode* T) {
	if (T == NULL) {
		return;
	}
	else {
		// 处理左孩子
		inOrder(T->lchild);
		// 中办事
		printf("%c ", T->data);
		// 处理右孩子
		inOrder(T->rchild);
	}
}

void postOrder(TreeNode* T) {
	if (T == NULL) {
		return;
	}
	else {
		// 处理左孩子
		postOrder(T->lchild);
		// 处理右孩子
		postOrder(T->rchild);
		// 后办事
		printf("%c ", T->data);
	}
}



void test01()
{
	TreeNode* T;
	int index = 0;
	char * data = "ABD##E##CF##G##";
	createTree(&T, data, &index);
	printf("先序遍历："); preOrder(T);
	printf("n");
	printf("中序遍历："); inOrder(T);
	printf("n");
	printf("后序遍历："); postOrder(T);
	printf("n");
}


//
QueueNode* initQueue()
{
	QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));
	Q->data = NULL;
	Q->next = Q;
	Q->pre = Q;
	return Q;
}

void enQueue(TreeNode* data, QueueNode* Q)
{
	QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
	node->data = data;
	node->pre = Q;
	node->next = Q;
	Q->pre->next = node;
	Q->pre = node;
}

int isEmpty(QueueNode* Q)
{
	if (Q->next == Q) {
		return 1;
	}
	else {
		return 0;
	}
}



QueueNode* deQueue(QueueNode* Q)
{
	if (isEmpty(Q)) {
		return NULL;
	}
	else {
		QueueNode* node = Q->next;
		Q->next->next->pre = Q;
		Q->next = Q->next->next;
		return node;
	}
}

void levelTraverse(QueueNode* Q, TreeNode* T)
{
	enQueue(T, Q);
	while (!isEmpty(Q)) {
		QueueNode* node = deQueue(Q);
		printf("%c ", node->data->data);
		if (node->data->lchild) {
			enQueue(node->data->lchild, Q);
		}
		if (node->data->rchild) {
			enQueue(node->data->rchild, Q);
		}
	}
}
void test02()
{
	//层次遍历
	TreeNode* T;
	int index = 0;
	char * data = "ABD##E##CF##G##";
	createTree(&T, data, &index);
	QueueNode* Q = initQueue();
	preOrder(T);
	printf("n");
	levelTraverse(Q, T);
	printf("n");

}
//
//非递归遍历
StackNode* initStack()
{
	StackNode* S = (StackNode*)malloc(sizeof(StackNode));
	S->data = NULL;
	S->next = NULL;
	return S;
}

void push(TreeNode* data, StackNode* S) 
{
	StackNode* node = (StackNode*)malloc(sizeof(StackNode));
	node->data = data;
	node->next = S->next;
	S->next = node;
}

int isEmpty(StackNode* S)
{
	if (S->next == NULL) {
		return 1;
	}
	else {
		return 0;
	}
}

StackNode* pop(StackNode* S) 
{
	if (isEmpty(S)) {
		return NULL;
	}
	else {
		StackNode* node = S->next;
		S->next = node->next;
		return node;
	}
}

void preOrder_noRecurs(TreeNode* T)
{
	TreeNode* node = T;
	StackNode* S = initStack();
	while (node || !isEmpty(S)) {
		if (node) {
			printf("%c ", node->data);
			push(node, S);
			node = node->lchild;
		}
		else {
			node = pop(S)->data;
			node = node->rchild;
		}
	}
}

void inOrder_noRecurs(TreeNode* T)
{
	TreeNode* node = T;
	StackNode* S = initStack();
	while (node || !isEmpty(S)) {
		if (node) {
			push(node, S);
			node = node->lchild;
		}
		else {
			node = pop(S)->data;
			printf("%c ", node->data);
			node = node->rchild;
		}
	}
}

StackNode* getTop(StackNode* S) {
	if (isEmpty(S)) {
		return NULL;
	}
	else {
		StackNode* node = S->next;
		return node;
	}
}

void postOrder_noRecurs(TreeNode* T)
{
	StackNode* S = initStack();
	StackNode* n = (StackNode*)malloc(sizeof(StackNode));
	
	TreeNode *ee = T;//根节点
	TreeNode *pp = NULL;

	while (ee != NULL || !isEmpty(S) )
	{
		if (ee!= NULL)
		{
			push(ee, S);
			ee = ee->lchild;
		}
		else
		{
			ee = getTop(S)->data;
			
			if ((ee->rchild!=NULL) && (ee->rchild!=pp))
			{
				ee = ee->rchild;
				push(ee, S);
				ee = ee->lchild;
			} 
			else
			{
				ee = pop(S)->data;
				printf("%c ", ee->data);
				pp = ee;
				ee = NULL;
			}
		}
		
	}
	

}
void test03()
{
	TreeNode* T;
	int index = 0;
	char * data = "ABD##E##CF##G##";
	createTree(&T, data, &index);
	preOrder_noRecurs(T);
	printf("n");
	inOrder_noRecurs(T);
	printf("n");
	postOrder_noRecurs(T);
	printf("n");
}

int main()
{
	
	test03();
	system("pause");
	return EXIT_SUCCESS;
	
}

2. 线索二叉树

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 

//函数结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

typedef char  ElemType;

typedef struct TreeNode 
{
	char data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
	struct TreeNode* parent;
	int ltag;
	int rtag;
}TreeNode;

void createTree(TreeNode** T, char* data, int* index);

void inThreadTree(TreeNode* T, TreeNode** pre);

TreeNode* getFirst_in(TreeNode* T);

TreeNode* getNext_in(TreeNode* node);
//
void preThreadTree(TreeNode* T, TreeNode** pre);

TreeNode* getNext_pre(TreeNode* node);

//
void createTree_post(TreeNode** T, char* data, int* index, TreeNode* parent);

void postThreadTree(TreeNode* T, TreeNode** pre);

TreeNode* getFirst_post(TreeNode* T);

TreeNode* getNext_post(TreeNode* node);
#########################################
#include "inThreadTree.h"
//
//中序遍历
void createTree(TreeNode** T, char* data, int* index)
{
	char ch;
	ch = data[*index];
	*index += 1;
	if (ch == '#') {
		// 此时为空节点
		*T = NULL;
	}
	else {
		// 此时不为空
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		(*T)->ltag = 0;
		(*T)->rtag = 0;
		// 创建左子树，逻辑一致，进行递归
		createTree(&((*T)->lchild), data, index);
		// 创建右子树，逻辑一致，进行递归
		createTree(&((*T)->rchild), data, index);
	}
}

void inThreadTree(TreeNode* T, TreeNode** pre)
{
	if (T)
	{
		inThreadTree(T->lchild, pre);

		if (T->lchild == NULL)
		{
			T->ltag = 1;
			T->lchild = *pre;
		}
		if (*pre != NULL && (*pre)->rchild == NULL)
		{
			(*pre)->rtag = 1;
			(*pre)->rchild = T;
		}
		*pre = T;
		inThreadTree(T->rchild, pre);
	}
}

TreeNode* getFirst_in(TreeNode* T)
{
	while (T->ltag == 0)
		T = T->lchild;
	return T;
}

TreeNode* getNext_in(TreeNode* node)
{
	if (node->rtag == 1)
		return node->rchild;
	else
		return getFirst_in(node->rchild);
}



void test01()
{
	TreeNode* T;
	TreeNode* pre = NULL;
	int index = 0;
	char * data = "ABD##E##C##";
	createTree(&T, data, &index);
	inThreadTree(T, &pre);
	pre->rtag = 1;
	pre->rchild = NULL;
	for (TreeNode* node = getFirst_in(T); node != NULL; node = getNext_in(node))
	{
		printf("%c ", node->data);
	}
	printf("n");
}
//

void preThreadTree(TreeNode* T, TreeNode** pre) 
{
	if (T) {
		if (T->lchild == NULL) 
		{
			T->ltag = 1;
			T->lchild = *pre;
		}
		if (*pre != NULL && (*pre)->rchild == NULL)
		{
			(*pre)->rtag = 1;
			(*pre)->rchild = T;
		}
		*pre = T;
		if (T->ltag == 0)
			preThreadTree(T->lchild, pre);
		preThreadTree(T->rchild, pre);
	}
}
TreeNode* getNext_pre(TreeNode* node)
{
	if (node->rtag == 1 || node->ltag == 1)
		return node->rchild;
	else
		return node->lchild;
}

void test02()
{
	TreeNode* T;
	TreeNode* pre = NULL;
	int index = 0;
	char * data = "ABD##E##C##";
	createTree(&T, data, &index);
	preThreadTree(T, &pre);
	pre->rtag = 1;
	pre->rchild = NULL;
	for (TreeNode* node = T; node != NULL; node = getNext_pre(node))
	{
		printf("%c ", node->data);
	}
	printf("n");
}

//
//后序遍历二叉树
void createTree_post(TreeNode** T, char* data, int* index, TreeNode* parent)
{
	char ch;
	ch = data[*index];
	*index += 1;
	if (ch == '#')
	{
		// 此时为空节点
		*T = NULL;
	}
	else 
	{
		// 此时不为空
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = ch;
		(*T)->ltag = 0;
		(*T)->rtag = 0;
		(*T)->parent = parent;
		// 创建左子树，逻辑一致，进行递归
		createTree_post(&((*T)->lchild), data, index, *T);
		// 创建右子树，逻辑一致，进行递归
		createTree_post(&((*T)->rchild), data, index, *T);
	}
}

void postThreadTree(TreeNode* T, TreeNode** pre)
{
	if (T) 
	{
		postThreadTree(T->lchild, pre);
		postThreadTree(T->rchild, pre);
		// do something
		if (T->lchild == NULL)
		{
			T->ltag = 1;
			T->lchild = *pre;
		}
		if (*pre != NULL && (*pre)->rchild == NULL) 
		{
			(*pre)->rtag = 1;
			(*pre)->rchild = T;
		}
		*pre = T;
	}
}

TreeNode* getFirst_post(TreeNode* T)
{
	while (T->ltag == 0)
		T = T->lchild;
	if (T->rtag == 0) {
		return getFirst_post(T->rchild);
	}
	return T;
}

TreeNode* getNext_post(TreeNode* node)
{
	if (node->rtag == 1)
		return node->rchild;
	else {
		// 如果是根节点
		if (node->parent == NULL) {
			return NULL;
		}
		// 如果是右孩子
		else if (node->parent->rchild == node) {
			return node->parent;
		}
		// 如果是左孩子
		else {
			if (node->parent->ltag == 0) {
				return getFirst_post(node->parent->rchild);
			}
			else {
				return node->parent;
			}
		}
	}
}

void test03()
{
	TreeNode* T;
	TreeNode* pre = NULL;
	int index = 0;
	char * data = "ABD##E##C##";
	createTree_post(&T, data, &index, NULL);
	postThreadTree(T, &pre);
	for (TreeNode* node = getFirst_post(T); node != NULL; node = getNext_post(node)) {
		printf("%c ", node->data);
	}
	printf("n");

}

int main()
{
	test01();
	system("pause");
	return EXIT_SUCCESS;

}

3. 二叉排序树

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 

//函数结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;


typedef char  ElemType;

typedef struct TreeNode {
	int data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

TreeNode* bstSearch(TreeNode* T, int data);

void bstInsert(TreeNode** T, int data);

void preOrder(TreeNode* T);
################################
#include "binarySearchTree.h"

TreeNode* bstSearch(TreeNode* T, int data)
{
	if (T)
	{
		if (T->data == data)
		{
			return T;
		}
		else if (data < T->data) 
		{
			return bstSearch(T->lchild, data);
		}
		else 
		{
			return bstSearch(T->rchild, data);
		}
	}
	else
	{
		return NULL;
	}
}

void bstInsert(TreeNode** T, int data)
{
	if (*T == NULL) 
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = data;
		(*T)->lchild = NULL;
		(*T)->rchild = NULL;
	}
	else if (data == (*T)->data) 
	{
		return;
	}
	else if (data < (*T)->data)
	{
		bstInsert(&((*T)->lchild), data);
	}
	else
	{
		bstInsert(&((*T)->rchild), data);
	}
}

void preOrder(TreeNode* T) 
{
	if (T) 
	{
		printf("%d ", T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}
void inOrder(TreeNode* T)
{
	if (T)
	{
		preOrder(T->lchild);
		printf("%d ", T->data);
		preOrder(T->rchild);
	}
}


void test01()
{
	TreeNode* T = NULL;
	int nums[6] = { 4, 5, 19, 23, 2, 8 };
	for (int i = 0; i < 6; i++) 
	{
		bstInsert(&T, nums[i]);
	}
	preOrder(T);
	printf("n");
	inOrder(T);
	printf("n");
}

int main()
{
	test01();
	system("pause");
	return EXIT_SUCCESS;

}

4. 平衡二叉树

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 

//函数结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

typedef char  ElemType;

typedef struct TreeNode {
	int data;
	int height;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;

int getHeight(TreeNode* node);

int max(int a, int b);

void rrRotation(TreeNode* node, TreeNode** root);

void llRotation(TreeNode* node, TreeNode** root);

void avlInsert(TreeNode** T, int data);

void preOrder(TreeNode* T);
####################################
#include "avl.h"

int getHeight(TreeNode* node) 
{
	return node ? node->height : 0;
}

int max(int a, int b)
{
	return a > b ? a : b;
}

void rrRotation(TreeNode* node, TreeNode** root) 
{
	TreeNode* temp = node->rchild;
	node->rchild = temp->lchild;
	temp->lchild = node;
	node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
	temp->height = max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
	*root = temp;
}

void llRotation(TreeNode* node, TreeNode** root)
{
	TreeNode* temp = node->lchild;
	node->lchild = temp->rchild;
	temp->rchild = node;
	node->height = max(getHeight(node->lchild), getHeight(node->rchild)) + 1;
	temp->height = max(getHeight(temp->lchild), getHeight(temp->rchild)) + 1;
	*root = temp;
}

void avlInsert(TreeNode** T, int data)
{
	if (*T == NULL) 
	{
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = data;
		(*T)->height = 0;
		(*T)->lchild = NULL;
		(*T)->rchild = NULL;
	}
	else if (data < (*T)->data)
	{
		avlInsert(&(*T)->lchild, data);
		// 拿到当前节点左右子树的高度
		int lHeight = getHeight((*T)->lchild);
		int rHeight = getHeight((*T)->rchild);
		// 判断高度差
		if (lHeight - rHeight == 2)
		{
			if (data < (*T)->lchild->data) 
			{
				// LL 调整
				llRotation(*T, T);
			}
			else
			{
				// LR 调整
				rrRotation((*T)->lchild, &(*T)->lchild);
				llRotation(*T, T);
			}
		}
	}
	else if (data > (*T)->data)
	{
		avlInsert(&(*T)->rchild, data);
		// 拿到当前节点左右子树的高度
		int lHeight = getHeight((*T)->lchild);
		int rHeight = getHeight((*T)->rchild);
		// 判断高度差
		if (rHeight - lHeight == 2) 
		{
			if (data > (*T)->rchild->data) 
			{
				// RR 调整
				rrRotation(*T, T);
			}
			else
			{
				// RL 调整
				llRotation((*T)->rchild, &(*T)->rchild);
				rrRotation(*T, T);
			}
		}
	}
	(*T)->height = max(getHeight((*T)->lchild), getHeight((*T)->rchild)) + 1;
}

void preOrder(TreeNode* T)
{
	if (T)
	{
		printf("%d ", T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}
}

void test01() 
{
	TreeNode* T = NULL;
	int nums[5] = { 1,8,6,7,10 };
	for (int i = 0; i < 5; i++) 
	{
		avlInsert(&T, nums[i]);
	}
	preOrder(T);
	printf("n");
}

int main()
{
	test01();
	system("pause");
	return EXIT_SUCCESS;	
}

5. 哈夫曼树

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
#include 

//函数结果状态代码 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;

typedef char  ElemType;

typedef struct TreeNode 
{
	int weight;
	int parent;
	int lchild;
	int rchild;
}TreeNode;

typedef struct HFTree
{
	TreeNode *data;
	int length;
}HFTree;

HFTree* initTree(int* weight, int length);

int* selectMin(HFTree* T);

void createHFTree(HFTree* T);

void preOrder(HFTree* T, int index);
#####################################
#include "huffmantree.h"

int* selectMin(HFTree* T)
{
	int min = 10000;
	int secondMin = 10000;
	int minIndex = 0;
	int secondIndex = 0;
	for (int i = 0; i < T->length; i++)
	{
		if (T->data[i].parent == 0)
		{
			if (T->data[i].weight < min)
			{
				min = T->data[i].weight;
				minIndex = i;
			}
		}
	}
	for (int i = 0; i < T->length; i++)
	{
		if (T->data[i].parent == 0 && i != minIndex)
		{
			if (T->data[i].weight < secondMin)
			{
				secondMin = T->data[i].weight;
				secondIndex = i;
			}
		}
	}
	int *res = (int *)malloc(sizeof(int) * 2);
	res[0] = minIndex;
	res[1] = secondIndex;
	return res;
}

void createHFTree(HFTree* T)
{
	int* res;
	int min;
	int secondMin;
	int length = T->length * 2 - 1;
	for (int i = T->length; i < length; i++)
	{
		res = selectMin(T);
		min = res[0];
		secondMin = res[1];
		T->data[i].weight = T->data[min].weight + T->data[secondMin].weight;
		T->data[i].lchild = min;
		T->data[i].rchild = secondMin;
		T->data[i].parent = 0;

		T->data[min].parent = i;
		T->data[secondMin].parent = i;
		T->length++;
	}
}

void preOrder(HFTree* T, int index)
{
	if (index != -1) {
		printf("%d ", T->data[index].weight);
		preOrder(T, T->data[index].lchild);
		preOrder(T, T->data[index].rchild);
	}
	
}

HFTree* initTree(int* weight, int length) {
	HFTree* T = (HFTree*)malloc(sizeof(HFTree));
	T->data = (TreeNode*)malloc(sizeof(TreeNode) * (2 * length - 1));
	T->length = length;
	for (int i = 0; i < length; i++) {
		T->data[i].weight = weight[i];
		T->data[i].parent = 0;
		T->data[i].lchild = -1;
		T->data[i].rchild = -1;
	}
	return T;
}

void test01()
{
	int weight[7] = { 5,1,3,6,11,2,4 };
	HFTree* T = initTree(weight, 7);
	//int* res=selectMin(T);
	//printf("%d    ", res[0]);
	//printf("%d    ", res[1]);
	createHFTree(T);
	preOrder(T, T->length - 1);
	printf("n");
}
int main()
{
	test01();
	system("pause");
	return EXIT_SUCCESS;
	
}