Tree

二叉树

二叉树是树的一种，每个节点最多只能有两个孩子。

树型结构是一种逻辑结构，他们同样可以用顺序结构和链式结构来实现。

结构

//树的相关数据结构
typedef char BiElemType;
typedef struct BiTNode {
	BiElemType c;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode, * BiTree;

层序建树

这里要用到一个辅助链表（不带头节点）。它将记录一个个节点，一层层，插入到树中的顺序。

流程图

代码实现

#include"Header.h"

void PreOrder(BiTree p) {
	if (p != NULL) {
		putchar(p->c);
		PreOrder(p->lchild);
		PreOrder(p->rchild);
	}
}

void InOrder(BiTree p) {
	if (p != NULL) {
		InOrder(p->lchild);
		putchar(p->c);
		InOrder(p->rchild);
	}
}

void PostOrder(BiTree p) {
	if (p != NULL) {
		PostOrder(p->lchild);
		PostOrder(p->rchild);
		putchar(p->c);
	}
}

int main() {
	BiTree pnew;//临时树节点
	char c;
	BiTree tree = NULL;//树根
	//phead就是链表头，ptail就是链表尾，pcur用于遍历链表
	ptag_t phead = NULL, ptail = NULL, listpnew=NULL, pcur=NULL;
	//abcdefghij
	while (scanf("%c", &c) != EOF)
	{
		if (c == '\n')
		{
			break;
		}
		pnew = (BiTree)calloc(1, sizeof(BiTNode));//申请树结点
		pnew->c = c;//数据放进去
		listpnew = (ptag_t)calloc(1, sizeof(tag_t));//申请链表结点
		listpnew->p = pnew;
		if (NULL == tree)
		{
			tree = pnew;//树的根
			phead = listpnew;//链表头
			ptail = listpnew;//链表尾
			pcur = listpnew;
			continue;//建立好了根节点
		}
		else {
			//尾插法
			ptail->pnext = listpnew;
			ptail = listpnew;
		}//pcur始终指向要插入的结点的位置
		if (NULL == pcur->p->lchild)//如何把新结点放入树
		{
			pcur->p->lchild = pnew;//把新结点放到要插入结点的左边
		}
		else if (NULL == pcur->p->rchild)
		{
			pcur->p->rchild = pnew;//把新结点放到要插入结点的右边
			pcur = pcur->pnext;//左右都放了结点后，pcur指向队列的下一个
		}
	}
	PreOrder(tree);
	printf("\n");
	InOrder(tree);
	printf("\n");
	PostOrder(tree);
}

二叉树的遍历

层序遍历（广度优先遍历）

从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。

void levelOrder(BiTree tree) {
	LinkQueue lq;
	InitQueue(lq);
	EnQueue(lq, tree);

	BiTree p;
	while (!QueueEmpty(lq))
	{
		DeQueue(lq, p);//节点出队，并把节点赋给p
		printf("%c", p->c);
		if (p->lchild) {
			EnQueue(lq, p->lchild);
		}
		if (p->rchild) {
			EnQueue(lq, p->rchild);
		}
	}
}

深度优先遍历

对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。

先序遍历

void PreOrder(BiTree p) {
	if (p != NULL) {
		putchar(p->c);
		PreOrder(p->lchild);
		PreOrder(p->rchild);
	}
}

中序遍历

void InOrder(BiTree p) {
	if (p != NULL) {
		InOrder(p->lchild);
		putchar(p->c);
		InOrder(p->rchild);
	}
}

后序遍历

void PostOrder(BiTree p) {
	if (p != NULL) {
		PostOrder(p->lchild);
		PostOrder(p->rchild);
		putchar(p->c);
	}
}

线索二叉树

它建立在二叉树的基础之上，分为前序，中序后序线索二叉树。线索化的时候，根据前序，中序，后序遍历的顺序形成一个链表。

如果lchild==NULL，那么指向前驱节点，ltag=1；否则ltag=0;

如果rchild==NULL，那么让指向后继节点，rtag=1；否则rtag=0;

二叉排序树（二叉查找树）(Binary Search Tree)

注意：这里要理解递归的思想。递归的思想就是二叉树的思想，

1. 先把二叉树看成只有1个根，1个左孩子，1个右孩子构成（递归的第一层）。

2. 接下来，又把左孩子看成根，根和根的左右孩子，他们3个又组成一颗树。（递归的第二层）。

3. 又把右孩子看成根，根和根的左右孩子，他们3个又组成一颗树。（递归的第三层）。

4. 结束条件：如果左孩子或者右孩子为空。

5. 重复2，3的过程，这样整颗树就遍历完成

BST的三原则

1. 左子树的所有节点要比根小
2. 右子树的所有节点要比根大
3. 左子树右子树又可以是一颗二叉排序树

BST的创建

流程图

代码实现

typedef int BiElemType ;

typedef struct BiTNode {
	BiElemType data;
	struct BiTNode* lchild;
	struct BiTNode* rchild;
}BiTNode,*BiTree;

bool Insert_BST(BiTree& t, BiElemType e) {
	if (NULL == t) {
		t = (BiTree)calloc(1, sizeof(BiTNode));
		t->data = e;
		return true;
	}
	else if (e == t->data) {
		return false;
	}
	else if (e < t->data) {
		return Insert_BST(t->lchild, e);
	}
	else
	{
		return Insert_BST(t->rchild, e);
	}
}

void Create_BST(BiTree &t, BiElemType *arr, int n) {
	for (size_t i = 0; i < n; i++)
	{
		Insert_BST(t, arr[i]);
	}
}

BST的查找（折半查找）

因为二叉查找树是有序的，所以，我们可以用折半查找的方法，可以提高查找效率。BST的查找次数最多只是树的高度。

int Binary_Search(ElemType e, ElemType* arr, int n) {
	int low = 0, high=n-1, mid;//记录数组下标
	while (low <= high)
	{
		mid = (low + high) / 2;
		if (arr[mid] == e) {
			return mid;
		}
		else if (e < arr[mid]) {
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
}