def: 樹是n個結點的有限集合

非空樹應該滿足一下幾點

1)有且隻有一個特定的稱為根的結點.

2)當n>1,其餘結點可分為m個互不相交的有限集合

樹的定義是遞歸的

樹适合表示具有層次結構的數據

樹的性質

已經調整過了,但還是歪啦

二叉樹

def: 是另外一種樹形結構,特點是每個結點嘴都隻有2棵子樹,子樹有左右之分,順序不能颠倒

特殊形式(滿二叉樹 完全二叉樹 二叉排序樹 平衡二叉樹)

性質:

二叉樹遍曆(算法模闆片段)

void PreOrder(BiTree T)//先序遍曆 { if (T != NULL); { visit(T); PreOrder(T->lchild); preOrder(T->rchild); } } void InOrder(BiTree T)//中序遍曆 { if (T != NULL); { PreOrder(T->lchild); visit(T); PreOrder(T->rchild); } } void PostOrder(BiTree T)//後序遍曆 { if (T != NULL); { PreOrder(T->lchild); PreOrder(T->rchild); visit(T); } } void LevelOrder(BiTree T)//層次遍曆 { InitQueue(Q);//初始化輔助隊列 BiTree p; EnQueue(Q, T);//根節點入隊 while (!IsEmpty(Q))//隊列不空循環 { DnQueue(Q, p);//隊頭元素出隊 visit(p); if (p->lchild = NULL) EnQueue(Q, p->lchild);//左子樹不空,則入隊 if (p->rchild = NULL) EnQueue(Q, p->rchild);//右子樹不空,則入隊 } }

樹的遍曆實例代碼(簡單的先,中,後遍曆,所以沒有注釋)

#include<stdio.h> #include<stdlib.h> #include<string.h> struct BiTNode { int data; struct BiTNode *lchild, *rchild; }; typedef struct BiTNode BiTNode; typedef struct BiTNode BiTree; void preOrder(BiTNode *root) { if (root == NULL) { return; } printf("%d", root->data); preOrder(root->lchild); preOrder(root->rchild); } void inOrder(BiTNode *root) { if (root == NULL) { return; } inOrder(root->lchild); printf("%d", root->data); inOrder(root->rchild); } void postOrder(BiTNode *root) { if (root == NULL) { return; } postOrder(root->lchild); postOrder(root->rchild); printf("%d", root->data); } void main() { BiTNode t1, t2, t3, t4, t5; memset(&t1, 0, sizeof(BiTNode)); memset(&t2, 0, sizeof(BiTNode)); memset(&t3, 0, sizeof(BiTNode)); memset(&t4, 0, sizeof(BiTNode)); memset(&t5, 0, sizeof(BiTNode)); t1.data = 1; t2.data = 2; t3.data = 3; t4.data = 4; t5.data = 5; t1.lchild = &t2; t1.rchild = &t3; t2.lchild = &t4; t3.lchild = &t5; preOrder(&t1); inOrder(&t1); postOrder(&t1); printf("hello...\n"); system("pause"); return; }

計算葉子節點個數(核心代碼)

把全局變量變成參數

void coutLeaf(BiTNode *T,int *sum)//指針做函數參數 { if (T != NULL) { if (T->lchild == NULL&& T->rchild == NULL) { (*sum) ;//指針所指向的内存空間的數據 1,不是指針 1.一定要加括号 } if (T->lchild) { coutLeaf(T->lchild,sum); } if (T->rchild) { coutLeaf(T->rchild,sum); } } }

求樹的高度(也相當于是遍曆的過程)

int Depth(BiTNode *T) { int deptleft = 0; int deptright = 0; int deptval = 0; if (T == NULL) { deptval = 0; return deptval ; } deptleft = Depth(T->lchild); deptright = Depth(T->rchild); deptval = 1 (deptleft > deptright) ? deptleft : deptright; return deptval; }

樹的拷貝

BiTNode *CopyTree(BiTNode*T)//拷貝 { BiTNode *newNode = NULL; BiTNode *newLp = NULL; BiTNode *newRp = NULL; if (T == NULL) { return NULL; } if (T->lchild != NULL) { newLp = CopyTree(T->lchild); } else { newLp = NULL; } if (T->rchild != NULL) { newRp = CopyTree(T->rchild); } else { newRp = NULL; } newNode = (BiTNode*)malloc(sizeof(BiTNode)); if (newNode == NULL) { return NULL; } newNode->lchild = newLp; newNode->rchild = newRp; newNode->data = T->data; return NULL; }

二個輔助指針變量挖字符串(這個是為了二叉樹線索化的預備知識)

int spitString(const char *buf1, const char c, char buf[18][30], int *nycount) { char *p = NULL; int count = 0; char *pTmp = NULL; int tmpcount = 0; char buf2[1024]; pTmp = buf1; p = buf1; do { p = strchr(p, c); if (p != NULL) { tmpcount - p = pTmp; memcpy(buf[count], pTmp, tmpcount);//行成差值,然後歸并 buf[count][tmpcount] = '\0'; printf("%s\n", buf2); pTmp = p = p 1; count ; } else { break; } } while (*p != '\0'); } void main() { char *p = "aefasergazksdksakaddaweraerdfzdfzjfszg"; char c = ','; char buf[18][30]; int ncount; spitString(p, c, buf, &ncount); system("pause"); }

樹的存儲結構

雙親表示法(順存)

#define MAX_TREE_SIZE 100 //最多結點數 typedef struct //樹的結點定義 { ElemType data;//數據元素 int parent;//雙親位置域 }PTNode; typedef struct //樹的類型定義 { PTNode nodes(MAX_TREE_SIZE);//雙親表示 int n; }PTree;

孩子表示法(順 鍊)

孩子兄弟表示法(鍊)

樹的遍曆

先根遍曆

後根遍曆

樹的應用

并查集(支持三種操作)

#define SIZE 100 int UFSets[SIZE]; void Initial(int S[]) { for (int i = 0; i<size; i )//每個自成單元素集合 S[i] = -1; } int Find(int S[], int x) { while (S[x] >= 0)//循環尋找x的根 x = S[x]; return x; } void Union(int S[], int Root1, int Root2)//求兩個不相交子集合的名字 { S[Root2] = Root1; }

平衡二叉樹(左<根<右)

失衡以後調整方法(簡單介紹,不是重點)

LL(右單旋轉)

RR(左單旋轉)

RL(先右後左雙旋轉)

LR(先左後右雙旋轉)

隻有左孩子才能右上旋(孩子變爹,爹變孩子)

隻有右孩子才能左上旋(孩子變爹,爹變孩子)

紅黑樹以及其查找複雜

答：（1）紅黑樹來源于二叉搜索樹，其在關聯容器如map中應用廣泛，主要優勢在于其查找、删除、插入時間複雜度小，但其也有缺點，就是容易偏向一邊而變成一個鍊表。

紅黑樹是一種二叉查找樹，但在每個結點上增加一個存儲位表示結點的顔色，可以是Red或Black。也就是說，紅黑樹是在二叉

查找樹基礎上進一步實現的；

紅黑樹的五個性質：

性質1. 節點是紅色或黑色；

性質2. 根節點是黑色；

性質3 每個葉節點（指樹的末端的NIL指針節點或者空節點）是黑色的；

性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)；

性質5. 從任一節點到其每個尾端NIL節點或者NULL節點的所有路徑都包含相同數目的黑色節點。

（注：上述第3、5點性質中所說的NIL或者NULL結點，并不包含數據，隻充當樹的路徑結束的标志，即此葉結點非常見的葉子結點）。

因為一棵由n個結點随機構造的二叉查找樹的高度為lgn，所以順理成章，二叉查找樹的一般操作的執行時間為O(lgn)。但二叉查

找樹若退化成了一棵具有n個結點的線性鍊後，則這些操作最壞情況運行時間為O(n)；

紅黑樹雖然本質上是一棵二叉查找樹，但它在二叉查找樹的基礎上增加以上五個性質使得紅黑樹相對平衡，從而保證了

紅黑樹的查找、插入、删除的時間複雜度最壞為O(log n)。

（2）左旋右旋

紅黑樹插入或删除後，一般就會改變紅黑樹的特性，要恢複紅黑樹上述5個性質，一般都要那就要做2方面的工作：

1、部分結點顔色，重新着色

2、調整部分指針的指向，即左旋、右旋。

左旋右旋如圖所示：

左旋，如圖所示（左->右），以x->y之間的鍊為“支軸”進行，使y成為該新子樹的根，x成為y的左孩子，而y的左孩子則成為x的右孩

子。算法很簡單，旋轉後各個結點從左往右，仍然都是從小到大。

左旋代碼實現，分三步:

（1） 開始變化，y的左孩子成為x的右孩子；

（2） y成為x的父結點；

（3） x成為y的左孩子；

右旋類似，不再累述；

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!