学步园

    最近数据结构看的还真是恶心额，脑子不好使，算法写不来额·····

    二叉树一大堆概念性的东西，不过还是写吧。

二叉树(binary tree)

二叉树的基本形态
　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
　　(1)空二叉树——(a)；  
      (2)只有一个根结点的二叉树——(b)；
　　(3)只有左子树——(c)；
　　(4)只有右子树——(d)；
　　(5)完全二叉树——(e)

度(Degree)：节点孩子的数目。
叶子(Leaf): 度为0的节点称为叶子。
深度(Depth):树中最大的层次(从最上0开始数)

满二叉树：一棵深度为k且有2^k -1个节点的二叉树。
完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子节点，并且叶子节点都是从左到右依次排布，这就是完全二叉树。

性质1:在二叉树的第i层上至多有2^(i-1)个节点(i >= 1)
性质2:深度为k的二叉树至多有2^k - 1个节点
性质3:任意一棵二叉树T，若其叶子节点数为n0,度为2的节点数为n2,则n0 = n2 + 1

对于完全二叉树:

性质4:具有n个节点的完全二叉树的深度是[log2n] + 1
性质5:有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
　　  若I为结点编号则 如果I<>1，则其父结点的编号为I/2；
　　  如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
　　  如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

二叉树按层次遍历----队列实现
1.创建二叉树，输入#代表NULL，调用递归创建二叉树。
2.构建一个队列专门用来储存二叉树节点指针，先把根节点入队，假设是A，对A元素进行访问，然后对A的左右孩子依次入队，假设B,C。A出队列，再是对B进行访问，同样将B的左右孩子入队列，B出对列······重复以上，知道队列为空。

下面是的代码是实现按层次从上到下遍历二叉树：

#include <Windows.h>
#include <stdio.h>

#define ElemType char 

typedef struct TreeNode{				//单位节点
	struct TreeNode *LChild;
	struct TreeNode *RChild;
	ElemType c;
}TreeNode,* p_Tree;

typedef struct Link{					//单向链表
	struct Link *Next;
	TreeNode *Node;
}Link,*P_Link;

typedef struct Queue{					//形成队列
	P_Link front;						
	P_Link rear;
	int Q_Len;
}Queue,*p_Queue;

BOOL PrintElement(ElemType e);			//对二叉树节点的操作，自定义，这里我设置为打印出内容
BOOL CreateTree(p_Tree* pBiTree);		//创建二叉树
P_Link InitLink(P_Link L);				//初始化链表				
P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q);				//插入队列
p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q);		//取出队列第一个元素，并且访问左右孩子
p_Queue InitQueue(p_Queue T,P_Link L);									//初始化队列

int main() 
{
	p_Tree Tree = NULL;			
	P_Link Link = NULL;
	p_Queue Queue = NULL;
	if(!CreateTree(&Tree))												//创建二叉树
	{
		printf("Create Tree Error\n");
		return 0;
	}
	p_Tree p_Temp_Node = Tree;
	Link = InitLink(Link);	
	Queue = InitQueue(Queue,Link);
	
	Link = InsertLink(Link,p_Temp_Node,&Queue);						 //根节点入队

	BOOL(*Operate)(ElemType);										//定义函数指针
	Operate = PrintElement;

	while(Queue->front != Queue->rear)
	{			
		Queue = GetTopLinkNode(Link,Operate,Queue);					//获取队列第一个节点
	    Link = InsertLink(Link,Queue->front->Node->LChild,&Queue);	//左孩子入队
		Link = InsertLink(Link,Queue->front->Node->RChild,&Queue);	//右孩子入队
	}

	return 0;
}

BOOL CreateTree(p_Tree* pBiTree)
{
	ElemType ch;
	ch = getchar();
	if (ch == '#')													//#代表NULL
	{
		(*pBiTree) = NULL;
	}
	else
	{
		(*pBiTree) = (p_Tree)calloc(1,sizeof(TreeNode));
		if (!(*pBiTree))
		{
			printf("Allocate Memory Error\n");
			return FALSE;
		}
		else
		{
			(*pBiTree)->c = ch;
			CreateTree(&(*pBiTree)->LChild);			//调用递归创建二叉树
			CreateTree(&(*pBiTree)->RChild);
		}
	}
		return TRUE;
}

P_Link InitLink(P_Link L)
{
	L = (P_Link)calloc(1,sizeof(Link));
	if (!L)
	{
		printf("Memory Error\n");
		return NULL;
	}
	L->Node = NULL;
	L->Next = NULL;
	return L;
}

p_Queue InitQueue(p_Queue T,P_Link L)
{
	T = (p_Queue)calloc(1,sizeof(Queue));
	T->Q_Len = 0;
	T->front = L;
	T->rear = L;
	return T;
}

P_Link InsertLink(P_Link L,TreeNode *Tree_Node,p_Queue *Q)
{
	if (Tree_Node == NULL)
	{	
		return L;
	}
	else
	{
		static P_Link p = L;
		P_Link pNew;
		pNew = (P_Link)calloc(1,sizeof(Link));
		if (!pNew)
		{
			printf("Memory Error\n");
			return 0;
		}	
		pNew->Node = Tree_Node;		//New Node
		pNew->Next = NULL;
		p->Next = pNew;				//p to Next
		p = pNew;
		(*Q)->rear = p;			   //Add Queue
		(*Q)->Q_Len++ ;			   //Q len ++
		return L;
	}
}

p_Queue GetTopLinkNode(P_Link L, BOOL(*Visit)(ElemType),p_Queue Q)
{
	Q->front = Q->front->Next;    //remove first Node
	Visit(Q->front->Node->c);
	Q->Q_Len--;
	return Q;
}

BOOL PrintElement(ElemType e)
{
	// 输出元素e的值
	printf("%c",e);
	return TRUE;
}