考研數(shù)據(jù)結構之樹與二叉樹(C語言實現(xiàn))

樹
一、樹的基本概念
栗子樹

1.結點的度: 結點子結點的個數(shù).
A結點，也就是根節(jié)點的度為3分別是BCD
K，L節(jié)點的度為0

2.樹的度: 樹中最大的節(jié)點的度為樹的度.
栗子樹的度為3

3.結點的高度和深度：
高度是自下向上累計
深度是自上向下累計
A節(jié)點的高度為4，深度為1
K節(jié)點的高度為1，深度為4

4.樹的高度和深度：
☆樹中結點最大的層數(shù)栗子樹的高度和深度為4，同時層數(shù)也為4

5.路徑：
自上而下的有向的，A和E的路徑為A->B->E,E和F這樣的兄弟結點是不存在路徑的。

6.路徑長度：
路徑上所經(jīng)歷邊的個數(shù)，A->B->E的路徑長度為2

二、樹的性質.

1.樹中的結點數(shù) = 所有結點度數(shù) + 1
解釋：結點度的含義指的就是，結點有幾個孩子，那么，每個節(jié)點的度都可以和相應的結點對應，因為根結點是最頂層，然沒有父結點，所以，所有結點的度 + 根節(jié)點 = 樹中的結點數(shù)

2.度為M的樹的，任意結點的度數(shù)小于等于M，結點最多M個孩子

3.度為M的樹，至少有一個結點的度為M

4.度為M的樹，一定是非空樹，至少有M+1個節(jié)點

5.N叉樹，任意結點的度小于等于N

6.N叉樹，允許所有結點的度小于N

7.N叉樹，可以是空樹

8.度為M的樹，第i層最多有M^(i-1)個節(jié)點，其中i>=1
解析:最多結點樹，我們可以假設每個節(jié)點的度都為M，i>=1，說明了層數(shù)從第一層開始計數(shù)，一共層，第一層M0個，第二層M1，第三層就是M2...第i層就是M(i-1)次方個。

9.高度為H的M叉樹最多有1-M^H/1-M
解析:高度為H說明了一共有H層，M叉樹最多，可以假設，是滿M叉二叉樹，那么第一層有M^0 第二層有M1...第H層有M(h-1),因為是從零開始計數(shù)的0~H-1剛好H項，等比數(shù)列求和
1*(1-M^H)/(1-M) = 1-M^H/1-M

10.具有N個結點的M叉樹最小高度為logM^(1-N(1-M))
解析：最小高度就是當M叉樹為滿M叉樹的時候，具有N個結點
1-M^H/1-M = N => H = logM^(1-N(1-M))

三、二叉樹

  • 基本概念
    1.由一個根節(jié)點和兩個互不相交的左子樹和右子樹組成，同是左右子樹也是一個二叉樹，利用遞歸進行定義的數(shù)據(jù)結構.
    2.二叉樹有五種狀態(tài)：空二叉樹、只有左子樹，只有右子樹，只有根節(jié)點，左右子樹都有。

  • 邏輯結構
    幾種特殊的二叉樹：

1.滿二叉樹
①高度為h的滿二叉樹，有2^h -1個結點.
②只有最后一層含有葉子節(jié)點，不存在度為1的節(jié)點
③按照層序從1開始編號，i節(jié)點的左孩子為2i,i節(jié)點的右孩子為2i+1,父節(jié)點為i/2
④i<=n/2為分支節(jié)點，i>n/2為葉子節(jié)點.

2.完全二叉樹
①當且僅當每個結點都與高度為h的滿二叉樹中編號為1~n的節(jié)點一一對應時，稱為完全二叉樹
②只有最后兩層可能出現(xiàn)葉子節(jié)點
③最多只有一個度為1的節(jié)點
④結點i的左孩子為2i右孩子為2i+1，父親節(jié)點i/2
⑤i<=n/2為分支節(jié)點，i>n/2為葉子節(jié)點.

3.二叉排序樹
①左子樹所有的節(jié)點關鍵字小于根節(jié)點小于右子樹關鍵字.
②左右子樹又是一顆二叉排序樹

4.平衡二叉樹
①樹上任意結點的左子樹和右子樹深度只差不超過1

  • 二叉樹常考性質
    1.度為0,1,2的結點個數(shù)分別為N0,N1,N2則N0 = N2 + 1
    解析：設2插樹總結點樹為n=>
    ①n = N0 + N1 + N2
    樹的結點樹 = 總度數(shù) + 1 =>
    ②n = N1 + 2N2 + 1
    ①②聯(lián)立 => N0 = N2 + 1即度數(shù)為0的結點數(shù)量 = 度數(shù)為2的結點 + 1

2.二叉樹第i層最多2^(i-1)i>=1
3.高度為h的二叉樹最多有 2^h - 1個結點.

  • 存儲結構
    順序存儲
    1.順序存儲只適合存儲完全二叉樹
    解析：二叉樹是完全二叉樹的時候可以通過，2i，2i+1, i/2
    來找到結點之間的關系，當樹為普通二叉樹的時候，我們可以將普通二叉樹轉換成完全二叉樹，這樣的話，會有一部分空間導致浪費。
    浪費的空間

所以二叉樹很少使用順序存儲，一般樹為完全二叉樹的時候，可以使用.

2.鏈式存儲代碼


代碼中對應的樹
#include<stdio.h>
#include<stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode* leftChild;
    struct TreeNode* rightChild;
}TreeNode,Tree;

Tree* inintTree(char root);

TreeNode* getTreeNode(char data);

void preOrder(Tree* tree);

void inOrder(Tree* tree);

void postOrder(Tree* tree);

void visit(TreeNode* treeNode);

int main() {
    // 構建樹.  
    TreeNode* tree = inintTree('a');
    TreeNode* rootA = tree;
    TreeNode* nodeB = getTreeNode('b');
    TreeNode* nodeC = getTreeNode('c');
    TreeNode* nodeD = getTreeNode('d');
    TreeNode* nodeE = getTreeNode('e');
    rootA->leftChild = nodeB;
    rootA->rightChild = nodeC;
    nodeB->leftChild = nodeD;
    nodeB->rightChild = nodeE;
    
    //前序遍歷
    preOrder(tree);
    printf("\n");
    // 中序遍歷
    inOrder(tree);
    printf("\n");
    // 層序遍歷 
    postOrder(tree);
    printf("\n");
}

Tree* inintTree(char root) {
    return getTreeNode(root);
} 

TreeNode* getTreeNode(char data) {
    TreeNode* treeNode = (TreeNode*)malloc(sizeof(TreeNode));
    treeNode->data = data;
    treeNode->leftChild = NULL;
    treeNode->rightChild = NULL;
    return treeNode;
}

void preOrder(Tree* tree){
    if(tree!=NULL) {
        visit(tree);
        preOrder(tree->leftChild);
        preOrder(tree->rightChild);
    }
}

void inOrder(Tree* tree){
    if(tree!=NULL) {
        inOrder(tree->leftChild);
        visit(tree);
        inOrder(tree->rightChild);
    }
}

void postOrder(Tree* tree){
    if(tree!=NULL) {
        postOrder(tree->leftChild);
        postOrder(tree->rightChild);
        visit(tree);
    }
}

void visit(TreeNode* treeNode) {
    printf("%c ",treeNode->data);
}
  1. 二叉樹的遍歷
    ①前序遍歷
    ②中序遍歷
    ③后序遍歷
    ④層序遍歷
    思想：初始化一個輔助隊列，根節(jié)點入隊，若隊列非空，隊頭節(jié)點出隊，出隊節(jié)點存在左右孩子則插入隊尾，重復上述，直到隊列為空.
  • 根據(jù)遍歷順序推出二叉樹的結構
    1.前中 √
    2.后中√
    3.層中√
    必須要有中序遍歷，否則無法推導二叉樹結構.
四、線索二叉樹

1.中序線索二叉樹

#include<stdio.h>

typedef struct TreeNode {
    char data;
    struct TreeNode leftChild,rightChild;
    int leftFlag,rightFlag;
}TreeNode,Tree;

TreeNode* getTreeNode(char data);

void buildThreadBinaryTree(Tree* tree);

void dealTree(Tree* tree);

TreeNode* pre = NULL;

int main() {
    
    TreeNode* treeNodeA = getTreeNode('a');
    TreeNode* treeNodeB = getTreeNode('b');
    TreeNode* treeNodeC = getTreeNode('c');
    TreeNode* treeNodeD = getTreeNode('d');
    TreeNode* treeNodeE = getTreeNode('e');
    
    treeNodeA->leftChild = treeNodeB;
    treeNodeA->rightChild = treeNodeC;
    treeNodeB->leftChild = treeNodeD;
    treeNodeE->rightChild = treeNodeE;
    
    //這里以中序線索二叉樹為例. 
    buildThreadBinaryTree(treeNodeA);
    //處理最后一個結點. 
    if(pre->rightChild == NULL) {
        pre->rightFlag = 1;
    } 
}

TreeNode* getTreeNode(char data) {
    TreeNode* treeNode = (TreeNode*)malloc(sizeof(TreeNode));
    treeNode->data = data;
    treeNode->leftChild = NULL;
    treeNode->leftFlag = 0;
    treeNode->rightChild = NULL;
    treeNode->rightFlag = 0;
    return treeNode;
}

void buildThreadBinaryTree(Tree* tree) {
    if(tree != NULL) {
        buildThreadBinaryTree(tree->leftChild);
        dealTree(tree);
        buildThreadBinaryTree(tree->rightChild);
    }
}

void dealTree(Tree* tree) {
    //找前驅 
    if(tree->leftChild == NULL) {
        tree->leftChild = pre;
        tree->leftFlag = 1;
    }
    //找后繼 
    if(pre != NULL && pre->rightChild == NULL) {
        pre->rightChild = tree;
        pre->rightFlag = 1;
    }
    pre = tree;
}

2.前序遍歷

void buildThreadBinaryTree(Tree* tree) {
    if(tree != NULL) {
        dealTree(tree);
        //為了防止轉圈的問題.
        if(tree->leftFlag == 0) {
            buildThreadBinaryTree(tree->leftChild); 
        } 
        buildThreadBinaryTree(tree->rightChild);
    }
}

3.后序遍歷

void buildThreadBinaryTree(Tree* tree) {
    if(tree != NULL) {
        buildThreadBinaryTree(tree->leftChild);
        buildThreadBinaryTree(tree->rightChild);
        dealTree(tree);
    }
}

4.找前驅和后繼

待更新....
最后編輯于 ：
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容