c語言數(shù)據(jù)結(jié)構(gòu)完全二叉樹

快速開始

直接參考示例代碼即可

介紹

概念

二叉樹（Binary tree）是樹形結(jié)構(gòu)的一個(gè)重要類型。

許多實(shí)際問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹形式，即使是一般的樹也能簡單地轉(zhuǎn)換為二叉樹，

二叉樹的存儲結(jié)構(gòu)及其算法都較為簡單。

二叉樹特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹，且有左右之分。

類型

基本類型描述

空二叉樹	(NULL)
二叉樹根	只有一個(gè)節(jié)點(diǎn)的二叉樹
左樹	每個(gè)結(jié)點(diǎn)只有左子節(jié)點(diǎn)的樹（鏈表）
右樹	每個(gè)節(jié)點(diǎn)只有右子節(jié)點(diǎn)的樹
完全二叉樹	每個(gè)深度都是滿節(jié)點(diǎn)的二叉樹

示例代碼：建立二叉樹

介紹

• 該示例代碼介紹了一個(gè)完全二叉樹的建立，以及前序遍歷，中序遍歷和后序遍歷的索引結(jié)果。（源代碼完成了命名自注釋，不再贅述）

• 頭文件建立了一個(gè)DH_ibtree的二叉樹類型，核心數(shù)據(jù)是data，核心接口是data_info

代碼結(jié)構(gòu)

代碼結(jié)構(gòu)： - ./|-- DH_btree.h-- DH_basic_btree.c

DH_btree.h

/** copyright DH.*/#ifndef DH_BTREE #define DH_BTREE/* 標(biāo)識，說明該參數(shù)是入?yún)⑦€是出參 */ #define IN #define OUT #define INOUT /* 數(shù)據(jù)結(jié)構(gòu)為整型的基本二叉樹示例 */ typedef struct _DH_ibtree {int data;int deep;void (*data_info)(int data);struct _DH_ibtree *left;struct _DH_ibtree *right; } DH_ibtree;#endif

DH_basic_btree.c

#include <stdio.h> #include <stdlib.h> #include "DH_btree.h"static void logDataInfo(int data) {printf("[當(dāng)前節(jié)點(diǎn)信息] 節(jié)點(diǎn)數(shù)據(jù)　= %d\n", data); }/* 利用前序遍歷完成二叉樹構(gòu)建 */ static void preOrderSetUp(IN int *tree_arr, IN int arr_len,INOUT DH_ibtree *father_node,IN int father_node_index) {if (father_node == NULL) {return;}if (father_node_index > arr_len) {return;}if (father_node_index * 2 > arr_len) {return;}father_node->left = (DH_ibtree *)calloc(1, sizeof(DH_ibtree));father_node->left->data = tree_arr[father_node_index * 2 -1];father_node->left->data_info = logDataInfo;// printf("%d\n", tree_arr[father_node_index * 2 -1]);preOrderSetUp(tree_arr, arr_len, father_node->left, father_node_index * 2);father_node->right = (DH_ibtree *)calloc(1, sizeof(DH_ibtree));father_node->right->data = tree_arr[father_node_index * 2];father_node->right->data_info = logDataInfo;// printf("%d\n", tree_arr[father_node_index * 2]);preOrderSetUp(tree_arr, arr_len, father_node->right, father_node_index * 2 + 1); }/** 功能：前序遍歷初始化一個(gè)二叉樹* 輸入：原始二叉樹數(shù)組，二叉樹數(shù)組大小* 輸出：無* 返回：初始化的二叉樹*/ DH_ibtree *DH_ibtree_init(IN int *tree_arr, IN int arr_len) {DH_ibtree *new_tree = (DH_ibtree *)calloc(1, sizeof(DH_ibtree));new_tree->data = tree_arr[0];new_tree->data_info = logDataInfo;preOrderSetUp(tree_arr, arr_len, new_tree, 1);return new_tree; }/** 功能：二叉樹前序遍歷****/ void DH_ibtree_preOrderLoop(IN DH_ibtree *node) {if (!node) {return;}node->data_info(node->data);DH_ibtree_preOrderLoop(node->left);DH_ibtree_preOrderLoop(node->right); }/** 功能：二叉樹中序遍歷****/ void DH_ibtree_inOrderLoop(IN DH_ibtree *node) {if (!node) {return;}DH_ibtree_inOrderLoop(node->left);node->data_info(node->data);DH_ibtree_inOrderLoop(node->right); }/** 功能：二叉樹后序遍歷****/ void DH_ibtree_postOrderLoop(IN DH_ibtree *node) {if (!node) {return;}DH_ibtree_postOrderLoop(node->left);DH_ibtree_postOrderLoop(node->right);node->data_info(node->data); }int main(void) {int arr[7] = {1, 2, 3, 4, 5, 6, 7};int arr_num = 7;DH_ibtree *tree = DH_ibtree_init(arr, arr_num);printf("preOrderLoop start\n");DH_ibtree_preOrderLoop(tree);printf("inOrderLoop start\n");DH_ibtree_inOrderLoop(tree);printf("postOrderLoop start\n");DH_ibtree_postOrderLoop(tree);}

總結(jié)

以上是生活随笔為你收集整理的【c语言数据结构】二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。