淘先锋技术网

首页 1 2 3 4 5 6 7

1.树的原理

树(Tree)是n(n≥0)个节点的有限集合T,它满足两个条件 :

        1.有且仅有一个特定的称为根(Root)的节点;

        2.其余的节点可以分为m(m≥0)个互不相交的有限集合T1、T2、……、Tm,其中每一个集合又是一棵树,并称为其根的子树

表示方法 :树形表示法目录表示法

        一个节点的子树的个数称为该节点的度数

        一棵树的度数是指该树中节点的最大度数,

        度数为零的节点称为树叶终端节点,

        度数不为零的节点称为分支节点

        除根节点外的分支节点称为内部节点

  • 若树中每个节点的各个子树的排列为从左到右,不能交换,即兄弟之间是有序的,则该树称为有序树
  • m(m≥0)棵互不相交的树的集合称为森林
  • 树去掉根节点就成为森林,森林加上一个新的根节点就成为树。

2.二叉树

定义

        二叉树是n(n ≥ 0)个节点的有限集合;要么是空集(n=0),要么是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成,严格区分左孩子和右孩子,即使只有一个子节点也要区分左右。

性质

性质1 二叉树第i层上的结点数目最多为2^(i-1),(i≥1)。
性质2 深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3 在任意-棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则no=n2+1。

顺序存储 

链式存储

typedef int data_t;		
typedef struct node_t;		
{
	data_t data; 		
	struct node_t *lchild ,*rchild ; 	
} bitree_t; 			
bitree_t *root; 	 

二叉树由根节点指针决定。 

3. 二叉树的遍历

        遍历 :沿某条搜索路径周游二叉树,对树中的每一个节点访问一次且仅访问一次。

        二叉树是非线性结构,每个结点有两个后继,则存在如何遍历即按什么样的搜索路径进行遍历的问题。

由于二叉树的递归性质,遍历算法也是递归的。三种基本的遍历算法如下 :

        1.先访问树根,再访问左子树,最后访问右子树;(根左右)

        2.先访问左子树,再访问树根,最后访问右子树;(左根右)

        3.先访问左子树,再访问右子树,最后访问树根;(左右根)

 注:当遍历算法为左根右时,先对根节点A进行左根右判断,得到B,此时B有子树,那么把B当作根,继续左根右判断,发现没有左节点,根是B,故B入队,右是C,C有子树,那么把C当作根,继续左根右,D是左且没有子树,故D入队,根C入队,此时A的左侧遍历完成,根A入队,右为E,有子树,将E作为根,左没值,故E入队,右F有子树,来到左G,G有子树,来到左H,H没子树,H入队,根G入队,右K入队F入队,中序序列:BDCAEHGKF

 4.二叉树遍历的实现

创建树

// 递归的方法
bitree * tree_create() {
	data_t ch;
	bitree *r;  // 根节点

	scanf("%c", &ch);
	if (ch == '#') // 符号# 用来表示这里的节点是空
		return NULL;

	if ((r = (bitree *)malloc(sizeof(bitree))) == NULL) {
		printf("malloc failed\n");
		return NULL;
	}
	r->data = ch;
	r->left  = tree_create();  // 这里用 只有树根的树结构去理解
	r->right = tree_create();  // r->left和r->right均为NULL
	return r;
}

这里使用了先序的方式来创建树,以上图为例,输入scanf 的序列应该是:

A B # C D # # # E # F G H # # K # # #

先序遍历

void preorder(bitree * r) {  // 先序遍历
	if (r == NULL) {
		return;
	}
  // 这三行的递归 也体现出了对于树的每个内部节点,都会将其视为根,进行根左右的遍历
	printf("%c", r->data);
	preorder(r->left); 
	preorder(r->right);
}

中序遍历

void inorder(bitree * r) {   // 中序遍历
	if (r == NULL) {
		return;
	}
	inorder(r->left);
	printf("%c", r->data);
	inorder(r->right);
}

后序遍历

void postorder(bitree * r) {  // 后序遍历
	if (r == NULL) {
		return;
	}
	postorder(r->left);
	postorder(r->right);
	printf("%c", r->data);
}

层次遍历

// 代码整体看下来,就是按照树的层数由一层到末层、从左到右依次遍历
void layerorder(bitree * r) { // 传入参数是树的根节点,不是整个树
	linkqueue * lq;  // 用于访问

	if ((lq = queue_create()) == NULL) 
		return;

	if (r == NULL) 
		return;

	printf("%c", r->data);
	enqueue(lq, r); // 树根入队

	while (!queue_empty(lq)) {
		r = dequeue(lq); //循环①树根出队 循环②:左孩子出队 循环③:右孩子出队 循环④:左孩子的左右孙子继续循环
		if (r->left) {
			printf("%c", r->left->data); // 这就相当于遍历到了
			enqueue(lq, r->left);
		}
		if (r->right) {
			printf("%c", r->right->data);
			enqueue(lq, r->right);
		}
	}		
	puts("");
}