二叉鏈表介紹

二叉樹每個結點最多有2個孩子，所以為它設計一個數據域和2個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。

二叉鏈表思路

二叉鏈表的數據結構，數據域，左右孩子指針域。每個樹結點都有左右孩子，如果沒有孩子那么孩子指針域為NULL。我們用char類型的數據來模擬二叉鏈表的創建和遍歷。

我們知道二叉鏈表的遍歷有3種，前序遍歷，中序遍歷，后序遍歷。那么創建鏈表的時候同樣我們可以約定是前序、中序還是后序的形式進行進創建樹結點。以下圖為例，我們使用前序遍歷的形式創建二叉鏈表，然后將用3種遍歷形式輸出。如圖按照前序遍歷的結果是：ABCDEG，中序遍歷結果：CBDAEG，后序遍歷結果：CDBGEA。

二叉鏈表代碼

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> typedef char EleType; typedef struct BiTNode {EleType data;//數據結點數據域struct BiTNode *lchild, *rchild;//左孩子，右孩子結點指針域 }BiTNode,*BiTree;//約定通過前序遍歷創建結點 //每個結點都有左右孩子，孩子不存在為NULL void CreatBiTree(BiTree* tree) {char c;scanf("%c",&c);if (' '== c){*tree = NULL;}else{*tree = (BiTNode*)malloc(sizeof(BiTNode));(*tree)->data = c;CreatBiTree(&(*tree)->lchild);//創建左子樹CreatBiTree(&(*tree)->rchild);//創建右子樹} } void visit(EleType data,int level) {printf("%c 第%d層\n", data,level);return; }//前序遍歷 void PreOrderTraverse(BiTree tree,int level) {if (NULL != tree){visit(tree->data, level);PreOrderTraverse(tree->lchild, level + 1);PreOrderTraverse(tree->rchild, level + 1);} } //中序遍歷 void MidOrderTraverse(BiTree tree, int level) {if (NULL != tree){MidOrderTraverse(tree->lchild, level + 1);visit(tree->data, level);MidOrderTraverse(tree->rchild, level + 1);} } //后序遍歷 void PostOrderTraverse(BiTree tree, int level) {if (NULL != tree){PostOrderTraverse(tree->lchild, level + 1);PostOrderTraverse(tree->rchild, level + 1);visit(tree->data, level);} }int main(int argc, char *argv[]) {BiTree tree = NULL;printf("請按前序遍歷的方式輸入結點數據，沒有結點不存在請使用空格代替：");CreatBiTree(&tree);printf("前序遍歷：\n");PreOrderTraverse(tree, 1);printf("中序遍歷：\n");MidOrderTraverse(tree, 1);printf("后序遍歷：\n");PostOrderTraverse(tree, 1);return 0; }

代碼運行驗證

在創建二叉鏈表時，我們約定空格個位NULL孩子結點，我們以前序遍歷的形式創建二叉鏈表輸入應該是:ABC ?D ?E G ?也就是ABC2個空格D2個空格E1個空格G2個空格換行。

總結

以上是生活随笔為你收集整理的树：二叉链表的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。