(六)數(shù)據(jù)結(jié)構(gòu)--二叉樹-創(chuàng)新互聯(lián)

1、樹

定義：樹是n(n≥0)個(gè)節(jié)點(diǎn)的有限集，當(dāng)n=0時(shí)，稱為空數(shù)
非空樹要滿足：

超過10多年行業(yè)經(jīng)驗(yàn)，技術(shù)領(lǐng)先，服務(wù)至上的經(jīng)營模式，全靠網(wǎng)絡(luò)和口碑獲得客戶，為自己降低成本，也就是為客戶降低成本。到目前業(yè)務(wù)范圍包括了：成都做網(wǎng)站、網(wǎng)站建設(shè)，成都網(wǎng)站推廣，成都網(wǎng)站優(yōu)化，整體網(wǎng)絡(luò)托管，成都小程序開發(fā)，微信開發(fā)，手機(jī)APP定制開發(fā)，同時(shí)也可以讓客戶的網(wǎng)站和網(wǎng)絡(luò)營銷和我們一樣獲得訂單和生意！

有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)。
當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1，T2，…，Tm,其中每個(gè)集合本事又是一顆樹，并且稱為根的子樹。

特點(diǎn)：樹作為一種邏輯結(jié)構(gòu)，同時(shí)也是一種分層結(jié)構(gòu)

樹的跟結(jié)點(diǎn)沒有前驅(qū)，除根結(jié)點(diǎn)外的所有結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)
所有結(jié)點(diǎn)可以有零個(gè)或者多個(gè)后繼

A是第一層，B/C/D是第二層，E/F/G/H/I/J是第三層，K/L/M第四層

2、二叉樹

特點(diǎn)：每個(gè)樹節(jié)點(diǎn)最多只有兩顆子樹(不存在度大于2的結(jié)點(diǎn))，且二叉樹的子樹有左右之分，次序不能隨意顛倒

滿二叉樹每層結(jié)點(diǎn)個(gè)數(shù):2^(n-1)；
如果k結(jié)點(diǎn)去掉，就不是完全二叉樹了

3、二叉樹的存儲(chǔ)

說明：圖中的.表示該點(diǎn)沒有內(nèi)容，個(gè)人筆記習(xí)慣

順序存儲(chǔ)
一層一層逐一放置，如果該節(jié)點(diǎn)不存在用0補(bǔ)齊

1	2	3	0	4	0	5	0	0	6	0

鏈?zhǔn)酱鎯?chǔ)
數(shù)據(jù)結(jié)構(gòu)：

typedef char BiElemType;
typedef struct BiTNode{BiElemType c;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode, *BiTree;

樹中任何一個(gè)結(jié)點(diǎn)都是一個(gè)結(jié)構(gòu)體，他的空間是通過malloc申請(qǐng)出來

4、二叉樹層次建樹

向二叉樹中輸入a,b,c,d,e,f,g,h,i,j十個(gè)字母
實(shí)現(xiàn)效果：如圖

需要使用的輔助隊(duì)列

步驟：
1.把`a`放進(jìn)輔助隊(duì)列，此時(shí)pcur始終指向要放子節(jié)點(diǎn)的結(jié)點(diǎn)上；
2.把`b`放進(jìn)輔助隊(duì)列，判斷pcur所指的結(jié)點(diǎn)a的左孩子是不是為NULL，如果左孩子為NULL放在左邊；
3.把`c`放進(jìn)輔助隊(duì)列，判斷pcur所指的結(jié)點(diǎn)a的右孩子是不是為NULL，如果右孩子為NULL放在右邊；
4.當(dāng)a的左右孩子都不為NULL時(shí)，pcur后移一個(gè)

calloc申請(qǐng)的空間大小是兩個(gè)想乘，對(duì)申請(qǐng)的空間初始化，賦值為0
代碼實(shí)現(xiàn)：

function.h文件

#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H

#include#includetypedef char BiElemType;
// 二叉樹結(jié)構(gòu)體
typedef struct BiTNode{BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;
// 輔助隊(duì)列結(jié)構(gòu)體
typedef struct tag{BiTree p; //樹的某一個(gè)結(jié)點(diǎn)的地址值
    struct tag *pnext;
} tag_t, *ptag_t;
#endif //TREE_FUNCTION_H

main.cpp文件

#include "function.h"

int main() {//1.用來指向新申請(qǐng)的樹節(jié)點(diǎn)
    BiTree pnew;
    BiTree tree=NULL; //tree 指向樹根用來代表樹
    BiElemType c;
    // 2.輔助隊(duì)列
    ptag_t  phead=NULL,ptail=NULL,list_pnew=NULL,pcur=NULL;
    // abcdefghij
    while (scanf("%c",&c)){if (c=='\n'){break; //讀到換行就結(jié)束
        }
        pnew=(BiTree)calloc(1,sizeof(BiTNode));
        pnew->c=c;
        // 給隊(duì)列結(jié)點(diǎn)申請(qǐng)空間
        list_pnew=(ptag_t)calloc(1,sizeof(tag_t));
        list_pnew->p=pnew;
        // 判斷是否是樹的第一個(gè)結(jié)點(diǎn)
        if (tree==NULL) {tree = pnew; // tree指向樹的根節(jié)點(diǎn)
            phead = list_pnew; // 第一個(gè)結(jié)點(diǎn)即是隊(duì)列頭，也是隊(duì)列尾
            ptail = list_pnew;
            pcur = list_pnew; // 指向進(jìn)入樹的父親元素
            continue;
        } else {// 先入隊(duì)列
            ptail->pnext=list_pnew;
            ptail=list_pnew;
            // 把結(jié)點(diǎn)放入樹中
            if(pcur->p->lchild==NULL){pcur->p->lchild=pnew;
            } else if(pcur->p->rchild==NULL){pcur->p->rchild=pnew; //當(dāng)前左右結(jié)點(diǎn)都有了，pcur后移一個(gè)
                pcur=pcur->pnext;
            }
        }
    }
    return 0;
}

5、二叉樹的前序中序后序遍歷

每一個(gè)遍歷都必須和自己的父親挨著

前序遍歷(preOrder)–深度優(yōu)先遍歷

先打印自身，再打印左子樹，再打印右子樹
前序遍歷打印結(jié)果：abdhiejcfg

void preOrder(BiTree Tree){if (Tree!=NULL){printf("%c",Tree->c); //打印
        preOrder(Tree->lchild);
        preOrder(Tree->rchild);
    }
}

中序遍歷(inOrder)

先打印左子樹，再打印自身，再打印右子樹
bacdbeac…
中序遍歷打印結(jié)果：hdibjeafcg

void inOrder(BiTree Tree){if (Tree!=NULL){inOrder(Tree->lchild);
        printf("%c",Tree->c); //打印
        inOrder(Tree->rchild);
    }
}

后序遍歷(PostOrder)

先打印左子樹，再打印右子樹，在打印自身
后序遍歷打印結(jié)果：hidjebfgca

void postOrder(BiTree Tree){if (Tree!=NULL){postOrder(Tree->lchild);
        postOrder(Tree->rchild);
        printf("%c",Tree->c); //打印
    }
}

層序遍歷(LevelOrder)–廣度優(yōu)先遍歷

層序遍歷打印結(jié)果：abcdefghij

// 層序遍歷--廣度優(yōu)先遍歷
void levelOrder(BiTree Tree){// 定義一個(gè)隊(duì)列
    LinkQueue Q;
    // 初始化
    initQueue(Q);
    BiTree p;
    // 入隊(duì)
    EnQueue(Q,Tree);
    while (!isEmpty(Q)){// 判斷隊(duì)列是否為空
        DeQueue(Q,p); // 出隊(duì)當(dāng)前結(jié)點(diǎn)并打印
        putchar(p->c);
        if (p->lchild!=NULL){EnQueue(Q,p->lchild); // 入隊(duì)左孩子
        }
        if (p->rchild!=NULL){EnQueue(Q,p->rchild); // 入隊(duì)右孩子
        }
    }
}

代碼整理

結(jié)合上一節(jié)“(五)數(shù)據(jù)結(jié)構(gòu)–隊(duì)列”的代碼實(shí)現(xiàn)。
結(jié)合輔助隊(duì)列，
新建queue.cpp文件

#include "function.h"
// 隊(duì)列初始化使用帶頭結(jié)點(diǎn)的鏈表來標(biāo)識(shí)
void initQueue(LinkQueue &Q){Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); //鏈表頭和鏈表尾指向同一個(gè)結(jié)點(diǎn)
    Q.front->next=NULL; // 頭結(jié)點(diǎn)的next指針為NULL
}
// 判斷隊(duì)列是否為空
bool isEmpty(LinkQueue Q){if (Q.front==Q.rear){return true;
    } else{return false;
    }
}
// 入隊(duì)
void EnQueue(LinkQueue &Q, ElemType value){LinkNode *p=(LinkNode*)malloc(sizeof(LinkNode));
    p->data=value;
    p->next=NULL; //要讓next為NULL
    Q.rear->next=p; //尾指針的next指向p,從尾部入隊(duì);
    Q.rear=p; //rear指向新的尾部
}
// 出隊(duì)
bool DeQueue(LinkQueue &Q, ElemType &value){if (isEmpty(Q)){return false;  //隊(duì)列為空
    }
    LinkNode *q=Q.front->next; //拿到第一個(gè)結(jié)點(diǎn)，存入q
    value=q->data;
    Q.front->next=q->next;
    // 鏈表只剩余一個(gè)結(jié)點(diǎn)時(shí)，被刪除后要改變r(jià)ear
    if (Q.rear==q){Q.rear=Q.front;
    }
    free(q); // 斷鏈
    return true;
}

修改function.h中的代碼

#ifndef TREE_FUNCTION_H
#define TREE_FUNCTION_H

#include#includetypedef char BiElemType;
// 二叉樹結(jié)構(gòu)體
typedef struct BiTNode{BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;
// 輔助隊(duì)列結(jié)構(gòu)體
typedef struct tag{BiTree p; //樹的某一個(gè)結(jié)點(diǎn)的地址值
    struct tag *pnext;
} tag_t, *ptag_t;

+  typedef BiTree ElemType;
// 鏈表結(jié)點(diǎn)結(jié)構(gòu)體
+  typedef struct LinkNode{+      ElemType data;
+      struct LinkNode *next;
+  }LinkNode;
+  typedef struct {+      LinkNode *front, *rear; // 鏈表頭和鏈表尾
+  }LinkQueue;

+  void initQueue(LinkQueue &Q);
+  bool isEmpty(LinkQueue Q);
+  void EnQueue(LinkQueue &Q,ElemType value);
+  bool DeQueue(LinkQueue &Q,ElemType &value);

#endif //TREE_FUNCTION_H

main.cpp文件

#include "function.h"

// 前序遍歷--深度優(yōu)先遍歷
void preOrder(BiTree Tree){if (Tree!=NULL){printf("%c",Tree->c); //打印
        preOrder(Tree->lchild);
        preOrder(Tree->rchild);
    }
}
// 中序遍歷
void inOrder(BiTree Tree){if (Tree!=NULL){inOrder(Tree->lchild);
        printf("%c",Tree->c); //打印
        inOrder(Tree->rchild);
    }
}
// 后序遍歷
void postOrder(BiTree Tree){if (Tree!=NULL){postOrder(Tree->lchild);
        postOrder(Tree->rchild);
        printf("%c",Tree->c); //打印
    }
}
// 層序遍歷--廣度優(yōu)先遍歷
void levelOrder(BiTree Tree){// 定義一個(gè)隊(duì)列
    LinkQueue Q;
    // 初始化
    initQueue(Q);
    BiTree p;
    // 入隊(duì)
    EnQueue(Q,Tree);
    while (!isEmpty(Q)){// 判斷隊(duì)列是否為空
        DeQueue(Q,p); // 出隊(duì)當(dāng)前結(jié)點(diǎn)并打印
        putchar(p->c);
        if (p->lchild!=NULL){EnQueue(Q,p->lchild); // 入隊(duì)左孩子
        }
        if (p->rchild!=NULL){EnQueue(Q,p->rchild); // 入隊(duì)右孩子
        }
    }
}
int main() {//1.用來指向新申請(qǐng)的樹節(jié)點(diǎn)
    BiTree pnew;
    BiTree tree=NULL; //tree 指向樹根用來代表樹
    BiElemType c;
    // 2.輔助隊(duì)列
    ptag_t  phead=NULL,ptail=NULL,list_pnew=NULL,pcur=NULL;
    // abcdefghij
    while (scanf("%c",&c)){if (c=='\n'){break; //讀到換行就結(jié)束
        }
        pnew=(BiTree)calloc(1,sizeof(BiTNode));
        pnew->c=c;
        // 給隊(duì)列結(jié)點(diǎn)申請(qǐng)空間
        list_pnew=(ptag_t)calloc(1,sizeof(tag_t));
        list_pnew->p=pnew;
        // 判斷是否是樹的第一個(gè)結(jié)點(diǎn)
        if (tree==NULL) {tree = pnew; // tree指向樹的根節(jié)點(diǎn)
            phead = list_pnew; // 第一個(gè)結(jié)點(diǎn)即是隊(duì)列頭，也是隊(duì)列尾
            ptail = list_pnew;
            pcur = list_pnew; // 指向進(jìn)入樹的父親元素
            continue;
        } else {// 先入隊(duì)列
            ptail->pnext=list_pnew;
            ptail=list_pnew;
            // 把結(jié)點(diǎn)放入樹中
            if(pcur->p->lchild==NULL){pcur->p->lchild=pnew;
            } else if(pcur->p->rchild==NULL){pcur->p->rchild=pnew; //當(dāng)前左右結(jié)點(diǎn)都有了，pcur后移一個(gè)
                pcur=pcur->pnext;
            }
        }
    }
    printf("----------preOrder----------\n");
    preOrder(tree);
    printf("\n");
    printf("----------inOrder----------\n");
    inOrder(tree);
    printf("\n");
    printf("----------postOrder----------\n");
    postOrder(tree);
    printf("\n");
    printf("----------levelOrder----------\n");
    levelOrder(tree);
    printf("\n");
    return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

分享名稱：(六)數(shù)據(jù)結(jié)構(gòu)--二叉樹-創(chuàng)新互聯(lián)
本文來源：http://weahome.cn/article/djjcgi.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

(六)數(shù)據(jù)結(jié)構(gòu)--二叉樹-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管