树定义

       专业定义：有且只有一个称为根的节点，有若干个互不相交的子树，这些子树的本身也是一棵树。

       通俗的定义：树是由节点和边组成；每个节点只有一个父节点但可以有多个子节点；但有一个节点例外，该节点没有父节点，此节点称为根节点。

专业术语

       节点 父节点 子节点 子孙 堂兄弟 深度

深度：从根节点到底层节点的层数称之为深度。根节点是第一层.

叶子节点：没有子节点的节点.

非终端节点：实际上就是非叶子节点.

度：子节点的个数称之为度.

树的分类

       一般树：任意一个节点的子节点的个数都不受限制.

       二叉树：任意一个节点的子节点的个数最多2个，且子节点的位置不可更改。

       二叉树是有序树。

森林：n个互不相交的树的集合.

二叉树的分类

       一般二叉树

       满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树就是满二叉树.

       完全二叉树：如果只是删除满二叉树最底层、最右边的连续若干个节点，这样形成的二叉树就是完全二叉树.

       满二叉树是完全二叉树的一个特例.

树的存储

       二叉树的存储

              连续存储【完全二叉树】

                     优点：查找某个节点的父节点和子节点

                     缺点：耗用内存空间过大.

       一般树的存储

              双亲表示法

                     求父节点方便----求下标，从0开始

              孩子表示法

              求子节点方便

       双亲孩子表示法

              求父节点和子节点都很方便

二叉树的表示法

       把一个普通树转化程二叉树来存储.

具体转化方法：

       设法保证任意一个节点的左指针域指向它的第一个孩子，

       右指针域指向它的下一个兄弟.

只要能满足此条件，就可以把一个普通树转化为二叉树.

一个普通树转化为的二叉树，一定是没有右子树的。

森林的存储：

       先把森林转化为二叉树，再存储二叉树.

#include <stdio.h>
#include <malloc.h>

/**
  *静态构建一个二叉树
  *2014/8/30
  */
struct BTNode * CreateBTree(void);
void PreTraverseBTree(struct BTNode * pT);
void InTraverseBTree(struct BTNode * pT);
void PostTraverseBTree(struct BTNode * pT);

typedef struct BTNode
{
	int data;
	struct BTNode * pLchild; //p是指针， L是左， child是孩子
	struct BTNode * pRchild;
};

int main(void)
{
	struct BTNode * pT = CreateBTree();
//	PreTraverseBTree(pT);
//	InTraverseBTree(pT);
	PostTraverseBTree(pT);
	
	return 0;
}

//后序遍历
void PostTraverseBTree(struct BTNode * pT)
{
	if(NULL != pT)
	{
		if(NULL != pT->pLchild)
		{
			PreTraverseBTree(pT->pLchild);
		}

		if(NULL != pT->pRchild)
		{
			PreTraverseBTree(pT->pRchild);
		}

		printf("%c\n", pT->data);  //输出跟元素
		
	}
	
}

//中序遍历
void InTraverseBTree(struct BTNode * pT)
{
	if(NULL != pT)
	{
		if(NULL != pT->pLchild)
		{
			PreTraverseBTree(pT->pLchild);
		}
	
		printf("%c\n", pT->data);  //输出跟元素

		if(NULL != pT->pRchild)
		{
			PreTraverseBTree(pT->pRchild);
		}
		
	}
	
}

//先序遍历
void PreTraverseBTree(struct BTNode * pT)
{
	if(pT != NULL)
	{
		printf("%c\n", pT->data);  //输出跟元素

		if(NULL != pT->pLchild)
		{
			PreTraverseBTree(pT->pLchild);
		}

		if(NULL != pT->pRchild)
		{
			PreTraverseBTree(pT->pRchild);
		}
		// pT->pLchild  可以代表整个左子树
	}
	/**
		伪算法
		先访问根节点；
		再先序遍历左子树；
		再先序遍历右子树.
	*/
}

//静态创建二叉树
struct BTNode * CreateBTree(void)
{
	struct BTNode * pA = (struct BTNode*)malloc(sizeof(struct BTNode));
	struct BTNode * pB = (struct BTNode*)malloc(sizeof(struct BTNode));
	struct BTNode * pC = (struct BTNode*)malloc(sizeof(struct BTNode));
	struct BTNode * pD = (struct BTNode*)malloc(sizeof(struct BTNode));
	struct BTNode * pE = (struct BTNode*)malloc(sizeof(struct BTNode));
	
	pA->data = http://www.mamicode.com/'A';>
树的应用
树是数据库中数据组织一种重要形式。
操作系统子父进程的关系本身就是一棵树
面向对象语言中类的继承关系。
哈夫曼树。
 
排序和查找的关系
       排序是查找的前提。
       排序是重点。
/**
  *快速排序	
  *
  */
#include <stdio.h>

int FindPos(int *a, int low, int high);
void QuickSort(int *a, int low, int high);

int main(void)
{
	int a[6] = {2, 1, 0, 5, 4, 3};
	int i;

	//第二个参数代表第一个元素的下标
	//第三个参数代表最后一个元素的下标
	QuickSort(a, 0, 5);

	for(i=0; i<6; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");

	return 0;
}

void QuickSort(int *a, int low, int high)
{
	int pos;

	if(low < high)
	{
		pos = FindPos(a, low, high);
		QuickSort(a, low, pos-1);  //左边的一半
		QuickSort(a, pos+1, high); //右边的一半
	}
}

int FindPos(int *a, int low, int high)
{
	int val = a[low];

	while(low < high)
	{
		while(low < high && a[high] >= val)
		{
			--high;
		}
		a[low] = a[high];

		while(low < high && a[low] <= val)
		{
			++low;
		}
		a[low] = val;

	} //终止while循环之后， low和high一定是相等的

	return high;

}


（郝斌讲学）数据结构学习篇（七）---树