?

目錄

一、二叉樹的順序存儲

存儲方式

總代碼

?二、二叉樹的鏈式存儲（二叉鏈表）

1、存儲結構

?2、創建二叉樹

?總代碼

---

一、二叉樹的順序存儲

存儲方式

//樹的順序存儲
typedef struct
{char data;
}BiTree;
BiTree tree[MAXSIZE];

總代碼

//二叉樹的順序存儲
#include<stdio.h>
#include<math.h>#define MAXSIZE 20
int num = 0, level = 0;//樹的順序存儲
typedef struct
{char data;
}BiTree;
BiTree tree[MAXSIZE];void Init_Bitree()
{int i = 0;for (i = 0; i < MAXSIZE - 1; i++){tree[i].data = ' ';}
}void Create_Bitree()
{int i = 0, j;printf("--------------------------------------可用'#'代替換行符------------------------------------\n");printf("請輸入二叉樹層數：\n");scanf_s("%d", &level);getchar();for (i = 0; i < level; i++){for (j = 0; j <= pow(2, i) - 1; j++){printf("\n請輸入第%d層第%d號結點數據：\n", i + 1, j + 1);scanf_s("%c", &tree[num].data);getchar();num++;}}
}void Traverse()
{int i, j, count = 0;for (i = 0; i < level; i++){for (j = 0; j <= pow(2, i) - 1; j++)if (tree[count].data != ' ')			//有值{printf("\n第%d個結點：%c\n", count, tree[count].data);printf("%c結點的層數：%d\t序號：%d\n", tree[count].data, i + 1, j + 1);count++;}if (count >= num)			//遍歷出了所有元素，不再浪費時間進行后續遍歷return;}
}int main()
{Init_Bitree();Create_Bitree();Traverse();return 0;
}

?二、二叉樹的鏈式存儲（二叉鏈表）

二叉樹的創建，通常會采用鏈式存儲。

1、存儲結構

//二叉樹的鏈式存儲
typedef struct BiTree
{char data;BiTree* Lchild, * Rchild;	//左右子樹BiTree* parent;					
}BiTree;
BiTree* head;						//根結點

?2、創建二叉樹

創建二叉樹采用前序遍歷的方式，主要思想是遞歸。先創建根結點，然后判斷是否有左葉子結點；有的話繼續創建lchild，沒有的話返回；然后繼續判斷是否有右葉子結點，有的話創建rchild，沒有的話返回。（具體實現過程可以看圖）

//創建二叉樹（默認前序遍歷）
void Create_Bitree(BiTree* T)
{if (str[index] == '#')			//為空{index++;T->data = '#';return;}T->data = str[index++];										//構造根結點T->Lchild = (BiTree*)malloc(sizeof(BiTree));T->Rchild = (BiTree*)malloc(sizeof(BiTree));Create_Bitree(T->Lchild);										//構造左子樹Create_Bitree(T->Rchild);									//構造右子樹
}

?總代碼

//二叉樹鏈式存儲
#include<stdio.h>
#include<malloc.h>
#include<string>int index = 0;
std::string str = "ABD###C#G##";				//(用數組也可以，一樣的)//二叉樹的鏈式存儲
typedef struct BiTree
{char data;BiTree* Lchild, * Rchild;	//左右子樹BiTree* parent;					
}BiTree;
BiTree* head;						//根結點void Init_BiTree()
{head = (BiTree*)malloc(sizeof(BiTree));head->parent = NULL;
}//創建二叉樹（默認前序遍歷）
void Create_Bitree(BiTree* T)
{if (str[index] == '#')			//為空{index++;T->data = '#';return;}T->data = str[index++];										//構造根結點T->Lchild = (BiTree*)malloc(sizeof(BiTree));T->Rchild = (BiTree*)malloc(sizeof(BiTree));Create_Bitree(T->Lchild);										//構造左子樹Create_Bitree(T->Rchild);									//構造右子樹
}int main()
{int i = 0;Init_BiTree();Create_Bitree(head);printf("測試創建效果：%c\n", head->Rchild->data);return 0;
}

總結

以上是生活随笔為你收集整理的数据结构与算法（6-2）二叉树的存储结构（顺序存储、链式存储）的全部內容，希望文章能夠幫你解決所遇到的問題。

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