1.樹

1.1結(jié)構(gòu)特點(diǎn)

• 非線性結(jié)構(gòu)，有一個直接前驅(qū)，但可能有多個直接后繼
• 有遞歸性，樹中還有樹
• 可以為空，即節(jié)點(diǎn)個數(shù)為零

1.2相關(guān)術(shù)語

• 根：即根結(jié)點(diǎn)，沒有前驅(qū)
• 葉子：即終端結(jié)點(diǎn)，沒有后繼
• 森林：即樹的集合
• 結(jié)點(diǎn)的度：直接后繼的個數(shù)
• 樹的度：結(jié)點(diǎn)的度的最大值
• 樹的深度高度：結(jié)點(diǎn)的最大層數(shù)

1.3樹的表示法

1.3.1圖形表示法

1.3.2廣義表表示法

1.3.3左孩子右兄弟表示法

將一顆多插樹轉(zhuǎn)化為二叉樹，如下

其中，結(jié)點(diǎn)結(jié)構(gòu)為

左結(jié)點(diǎn)為孩子結(jié)點(diǎn)，右節(jié)點(diǎn)為兄弟結(jié)點(diǎn)

2.二叉樹

2.1定義

一個根節(jié)點(diǎn)和兩棵不相交的二叉樹組成，即1:2

2.2基本特征

每個節(jié)點(diǎn)最多有兩棵子樹——每個節(jié)點(diǎn)的度<=2

左子樹和右子樹的順序不能顛倒——有序樹

2.3二叉樹性質(zhì)

滿二叉樹：深度為k，有2^k-1個節(jié)點(diǎn)

完全二叉樹：除最后一層，每一層節(jié)點(diǎn)數(shù)達(dá)到最大值，在最后一層只缺右邊的若干節(jié)點(diǎn)

2.4二叉樹的遍歷

//單個結(jié)點(diǎn)
struct BinaryNode
{char ch;struct BinaryNode* lChild;struct BinaryNode* rChild;
};

void test()
{struct BinaryNode A = { 'A',NULL,NULL };struct BinaryNode B = { 'B',NULL,NULL };struct BinaryNode C = { 'C',NULL,NULL };struct BinaryNode D = { 'D',NULL,NULL };struct BinaryNode E = { 'E',NULL,NULL };struct BinaryNode F = { 'F',NULL,NULL };struct BinaryNode G = { 'G',NULL,NULL };struct BinaryNode H = { 'H',NULL,NULL };//創(chuàng)建節(jié)點(diǎn)之間的關(guān)系A(chǔ).lChild = &B;A.rChild = &F;B.rChild = &C;C.lChild = &D;C.rChild = &E;F.rChild = &G;G.lChild = &H;//先序遍歷printf("先序遍歷\n");PreorderTraversal(&A);printf("中序遍歷\n");InorderTraversal(&A);printf("后序遍歷\n");PostorderTraversal(&A);
}

先序遍歷：DLR

//DLR
void PreorderTraversal(struct BinaryNode* node)
{if (node == NULL){return NULL;}printf("%c\n",node->ch);PreorderTraversal(node->lChild);PreorderTraversal(node->rChild);
}

中序遍歷：LDR

//LDR
void InorderTraversal(struct BinaryNode* node)
{if (node == NULL){return NULL;}InorderTraversal(node->lChild);printf("%c\n", node->ch);InorderTraversal(node->rChild);
}

后序遍歷：LRD

//LRD
void PostorderTraversal(struct BinaryNode* node)
{if (node == NULL){return NULL;}PostorderTraversal(node->lChild);PostorderTraversal(node->rChild);printf("%c\n", node->ch);
}

2.5統(tǒng)計(jì)二叉樹的葉子數(shù)量

左孩子和右孩子都為空指針時，即為葉子結(jié)點(diǎn)

//統(tǒng)計(jì)葉子數(shù)量
void calculateLeadNum(struct BinaryNode* root, int* p)
{if (root == NULL){return NULL;}if (root->lChild == NULL && root->rChild == NULL){(*p)++;}calculateLeadNum(root->lChild, p);calculateLeadNum(root->rChild, p);
}

2.6統(tǒng)計(jì)二叉樹的高度

比較左子樹和右子樹的高度，取最大的一個加一，即為樹的高度

//計(jì)算樹的高度
int calculateHeight(struct BinaryNode* root)
{if (root == NULL){return NULL;}int lp = calculateHeight(root->lChild);int rp = calculateHeight(root->rChild);int height = lp > rp ? lp + 1 : rp + 1;return height;
}

2.7拷貝二叉樹

• 拷貝左子樹
• 拷貝右子樹
• 創(chuàng)建新節(jié)點(diǎn)
• 將拷貝的左子樹和右子樹掛載到新節(jié)點(diǎn)上
• 將新節(jié)點(diǎn)賦值

//拷貝二叉樹
struct BinaryNode* copyTree(struct BinaryNode* root)
{if (root == NULL){return NULL;}struct BinaryNode* lp=copyTree(root->lChild);struct BinaryNode* rp=copyTree(root->rChild);struct BinaryNode* newNode = malloc(sizeof(struct BinaryNode));if (newNode == NULL){return;}newNode->lChild = lp;newNode->rChild = rp;newNode->ch = root->ch;return newNode;
}

2.8釋放二叉樹

• 釋放左子樹
• 釋放右子樹
• 釋放根節(jié)點(diǎn)

//釋放二叉樹
void releaseTree(struct BinaryNode* root)
{if (root == NULL){return NULL;}releaseTree(root->lChild);releaseTree(root->rChild);printf("%c結(jié)點(diǎn)已被釋放", root->ch);releaseTree(root);
}

2.9二叉樹的非遞歸遍歷

將每個節(jié)點(diǎn)設(shè)一個標(biāo)志，默認(rèn)false

（1）將根節(jié)點(diǎn)壓入棧中

（2）進(jìn)入循環(huán)（只要棧中元素個數(shù)大于0，進(jìn)行循環(huán)操作）

• 彈出棧頂元素
• 若棧頂元素標(biāo)志為true，輸出此元素并執(zhí)行下一次循環(huán)
• 若棧頂元素標(biāo)志為false，將節(jié)點(diǎn)標(biāo)志設(shè)為true
• 將該節(jié)點(diǎn)的右子樹、左子樹、根壓入棧中
• 執(zhí)行下一次循環(huán)