【資料結構筆記】資料結構基礎—樹

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("");
}