C語言數(shù)據(jù)結構之二叉鏈表創(chuàng)建二叉樹
更新時間：2022年02月11日 09:39:35 作者：正弦定理
這篇文章主要介紹了C語言數(shù)據(jù)結構之?二叉鏈表創(chuàng)建二叉樹，下文我們?yōu)榱烁奖愕氖褂枚鏄浣Y構體，可以使用?typedef?對結構體進行命名，具體內(nèi)容需要的小伙伴可以參考一下
一、思想（先序思想創(chuàng)建）
第一步先創(chuàng)建根節(jié)點,然后創(chuàng)建根節(jié)點左子樹,開始遞歸創(chuàng)建左子樹，直到遞歸創(chuàng)建到的節(jié)點下不繼續(xù)創(chuàng)建左子樹，也就是當下遞歸到的節(jié)點下的左子樹指向NULL，結束本次左子樹遞歸，返回這個節(jié)點的上一個節(jié)點，開始創(chuàng)建右子樹，然后又開始以當下這個節(jié)點，繼續(xù)遞歸創(chuàng)建左子樹，左子樹遞歸創(chuàng)建完，就遞歸創(chuàng)建右子樹，直到遞歸結束返回到上一級指針節(jié)點（也就是根節(jié)點下），此時根節(jié)點左邊子樹創(chuàng)建完畢，開始創(chuàng)建右邊子樹，原理和根節(jié)點左邊創(chuàng)建左右子樹相同
二、創(chuàng)建二叉樹
二叉樹的操作通常使用遞歸方法，如果遞歸不太明白，建議去對此進行一下學習和練習。二叉樹的操作可以分為兩類，一類是需要改變二叉樹的結構的，比如二叉樹的創(chuàng)建、節(jié)點刪除等等，這類操作，傳入的二叉樹的節(jié)點參數(shù)為二叉樹指針的地址，這種參入傳入，便于更改二叉樹結構體的指針（即地址）。這里稍微有一點點繞，可能需要多思考一下
如下是二叉數(shù)創(chuàng)建的函數(shù)，這里我規(guī)定，節(jié)點值為整數(shù)，如果輸入的數(shù)為-1，則表示結束繼續(xù)往下創(chuàng)建子節(jié)點的操作。然后我們使用遞歸的方法以此創(chuàng)建左子樹和右子樹
二叉樹結構體初始化：
為了更方便的使用二叉樹結構體，可以使用 typedef 對結構體進行命名
typedef struct Tree{
?
?int data;?? ??? ??? ??? ??? ?//?? ?存放數(shù)據(jù)域
?struct Tree *lchild;?? ??? ??? ?//?? ?遍歷左子樹指針
?struct Tree *rchild;?? ??? ??? ?//?? ?遍歷右子樹指針
?
}Tree,*BitTree;這里展示兩種傳參類型的創(chuàng)建方法，其中深意可多次參考理解，加深指針理解
(1)傳一級參數(shù)方法
BitTree CreateLink()
{
?? ?int data;
?? ?int temp;
?? ?BitTree T;
?? ?
?? ?scanf("%d",&data);?? ??? ?//?? ?輸入數(shù)據(jù)
?? ?temp=getchar();?? ??? ??? ?//?? ?吸收空格
?? ?
?? ?if(data == -1){?? ??? ??? ?//?? ?輸入-1 代表此節(jié)點下子樹不存數(shù)據(jù)，也就是不繼續(xù)遞歸創(chuàng)建
?? ??? ?
?? ??? ?return NULL;
?? ?}else{
?? ??? ?T = (BitTree)malloc(sizeof(Tree));?? ??? ??? ?//?? ??? ?分配內(nèi)存空間
?? ??? ?T->data = data;?? ??? ??? ??? ??? ??? ??? ??? ?//?? ??? ?把當前輸入的數(shù)據(jù)存入當前節(jié)點指針的數(shù)據(jù)域中
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);?? ??? ?
?? ??? ?T->lchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始遞歸創(chuàng)建左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);?? ??? ??? ?
?? ??? ?T->rchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始到上一級節(jié)點的右邊遞歸創(chuàng)建左右子樹
?? ??? ?return T;?? ??? ??? ??? ??? ??? ??? ?//?? ??? ?返回根節(jié)點
?? ?}?? ?
?? ?
}
(2)傳二級參數(shù)方法
BitTree CreateLink(BitTree *T)?? ??? ?//?? ?次數(shù) T為指向根節(jié)點的指針的地址
{
?? ?int data;?? ?
?? ?
?? ?scanf("%d",&data);
?? ?
?? ?if(data == -1){
?? ??? ?
?? ??? ?*T=NULL;?? ??? ??? ??? ?//?? ?結束遞歸時，讓指針當前節(jié)點的指針地址的 指針 指向NULL
?? ?}else{
?? ??? ?
?? ??? ?*T = (BitTree)malloc(sizeof(Tree));?? ??? ?//?? ?對指向節(jié)點指針地址的指針 分配內(nèi)存
?? ?
?? ??? ?if(!(*T) ){?? ??? ??? ?//?? ?*T = NULL ?表示分配內(nèi)存失敗，也就是結束遞歸創(chuàng)建了
?? ??? ??? ?printf("內(nèi)存分配失敗\n");
?? ??? ??? ?exit(-1);
?? ??? ?}
?? ??? ?
?? ??? ?
?? ??? ?(*T)->data = data;?? ??? ?//?? ?給節(jié)點指針地址內(nèi)的數(shù)據(jù)域，存入數(shù)據(jù)
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);
?? ??? ?CreateLink(&(*T)->lchild);?? ??? ?//?? ?開始遍歷左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);
?? ??? ?CreateLink(&(*T)->rchild);?? ??? ?//?? ?開始遍歷右子樹，遍歷的思想文章開頭處解釋
?? ??? ??? ?
?? ?}?? ?
?? ?
}
（1）一級參數(shù)完整例子：
#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
?
?int data;?? ??? ??? ??? ??? ?//?? ?存放數(shù)據(jù)域
?struct Tree *lchild;?? ??? ??? ?//?? ?遍歷左子樹指針
?struct Tree *rchild;?? ??? ??? ?//?? ?遍歷右子樹指針
?
}Tree,*BitTree;
BitTree CreateLink()
{
?? ?int data;
?? ?int temp;
?? ?BitTree T;
?? ?
?? ?scanf("%d",&data);?? ??? ?//?? ?輸入數(shù)據(jù)
?? ?temp=getchar();?? ??? ??? ?//?? ?吸收空格
?? ?
?? ?if(data == -1){?? ??? ??? ?//?? ?輸入-1 代表此節(jié)點下子樹不存數(shù)據(jù)，也就是不繼續(xù)遞歸創(chuàng)建
?? ??? ?
?? ??? ?return NULL;
?? ?}else{
?? ??? ?T = (BitTree)malloc(sizeof(Tree));?? ??? ??? ?//?? ??? ?分配內(nèi)存空間
?? ??? ?T->data = data;?? ??? ??? ??? ??? ??? ??? ??? ?//?? ??? ?把當前輸入的數(shù)據(jù)存入當前節(jié)點指針的數(shù)據(jù)域中
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);?? ??? ?
?? ??? ?T->lchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始遞歸創(chuàng)建左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);?? ??? ??? ?
?? ??? ?T->rchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始到上一級節(jié)點的右邊遞歸創(chuàng)建左右子樹
?? ??? ?return T;?? ??? ??? ??? ??? ??? ??? ?//?? ??? ?返回根節(jié)點
?? ?}?? ?
?? ?
}
void ShowXianXu(BitTree T)?? ??? ??? ?//?? ??? ?先序遍歷二叉樹
{
?? ?if(T==NULL)
?? ?{
?? ??? ?return;
?? ?}
?? ?printf("%d ",T->data);
?? ?ShowXianXu(T->lchild);?? ??? ??? ?//?? ?遞歸遍歷左子樹
?? ?ShowXianXu(T->rchild);?? ??? ??? ?//?? ?遞歸遍歷右子樹
}
int main()
{
?? ?BitTree S;
?? ?printf("請輸入第一個節(jié)點的數(shù)據(jù):\n");
?? ?S = CreateLink();?? ??? ??? ?//?? ??? ?接受創(chuàng)建二叉樹完成的根節(jié)點
?? ?ShowXianXu(S);?? ??? ??? ??? ?//?? ??? ?先序遍歷二叉樹
?? ?
?? ?return 0;?? ?
}?
（2）二級參數(shù)完整例子
#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
?? ?
?? ?int data;
?? ?struct Tree *lchild;
?? ?struct Tree *rchild;
}Tree,*BitTree;
BitTree CreateLink(BitTree *T)?? ??? ?//?? ?次數(shù) T為指向根節(jié)點的指針的地址
{
?? ?int data;?? ?
?? ?
?? ?scanf("%d",&data);
?? ?
?? ?if(data == -1){
?? ??? ?
?? ??? ?*T=NULL;?? ??? ??? ??? ?//?? ?結束遞歸時，讓指針當前節(jié)點的指針地址的 指針 指向NULL
?? ?}else{
?? ??? ?
?? ??? ?*T = (BitTree)malloc(sizeof(Tree));?? ??? ?//?? ?對指向節(jié)點指針地址的指針 分配內(nèi)存
?? ?
?? ??? ?if(!(*T) ){?? ??? ??? ?//?? ?*T = NULL ?表示分配內(nèi)存失敗，也就是結束遞歸創(chuàng)建了
?? ??? ??? ?printf("內(nèi)存分配失敗\n");
?? ??? ??? ?exit(-1);
?? ??? ?}
?? ??? ?
?? ??? ?
?? ??? ?(*T)->data = data;?? ??? ?//?? ?給節(jié)點指針地址內(nèi)的數(shù)據(jù)域，存入數(shù)據(jù)
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);
?? ??? ?CreateLink(&(*T)->lchild);?? ??? ?//?? ?開始遍歷左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);
?? ??? ?CreateLink(&(*T)->rchild);?? ??? ?//?? ?開始遍歷右子樹，遍歷的思想文章開頭處解釋
?? ??? ??? ?
?? ?}?? ?
?? ?
}
void ShowXianXu(BitTree T)?? ??? ?//?? ?先序遍歷二叉樹
{
?? ?if(T==NULL)
?? ?{
?? ??? ?return;
?? ?}
?? ?printf("%d ",T->data);
?? ?ShowXianXu(T->lchild);?? ??? ?//?? ?遍歷左子樹
?? ?ShowXianXu(T->rchild);?? ??? ?//?? ?遍歷右子樹
}
int main()
{
?? ?BitTree *S;?? ??? ??? ?//?? ?創(chuàng)建指向這個結構體指針地址 的指針
?? ?printf("請輸入第一個節(jié)點的數(shù)據(jù):\n");
?? ?CreateLink(&S);?? ??? ?//?? ?傳二級指針地址
?? ?ShowXianXu(S);?? ??? ?
?? ?
?? ?return 0;?? ?
}?到此這篇關于C語言數(shù)據(jù)結構之 二叉鏈表創(chuàng)建二叉樹的文章就介紹到這了,更多相關C語言 二叉鏈表創(chuàng)建二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了實例分析一個簡單的Win32程序,對于Win32應用程序的原理、執(zhí)行流程、實現(xiàn)方法主要環(huán)節(jié)都做了較為詳細的分析,有助于讀者深入理解Windows應用程序設計,需要的朋友可以參考下2014-09-09
這篇文章主要為大家詳細介紹了利用C語言實現(xiàn)時間處理工具的相關資料，文中的示例代碼講解詳細，具有一定的借鑒價值，需要的可以參考一下2022-09-09
引用是C++一個很重要的特性,顧名思義是某一個變量或?qū)ο蟮膭e名，對引用的操作與對其所綁定的變量或?qū)ο蟮牟僮魍耆葍r,這篇文章主要給大家總結介紹了C++中引用的相關知識點,需要的朋友可以參考下2022-03-03
為了免去在窗口排隊買票的麻煩,飛機訂票系統(tǒng)應運而生,下面這篇文章主要給大家介紹了關于C語言實現(xiàn)飛機訂票系統(tǒng)的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-06-06
本文主要介紹了C/C++字節(jié)序的深入理解，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
這篇文章主要介紹了c++遞歸解數(shù)獨方法示例,需要的朋友可以參考下2014-03-03
這篇文章主要為大家詳細介紹了C++有理數(shù)的表達和計算，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
結構體、聯(lián)合體是C語言中的構造類型,結構體我們平時應該都用得很多,下面這篇文章主要給大家介紹了關于c語言中聯(lián)合體和枚舉用法的相關資料,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2023-12-12
從下面表中的數(shù)據(jù)來看寫入用時vector和deque很快，因為他們內(nèi)存分配次數(shù)少，關聯(lián)容器和list都是一個一個分配的，一個一個分配也會造成內(nèi)存碎片，內(nèi)存利用率低2013-09-09
這篇文章主要介紹了Cocos2d-x觸摸事件實例,本文代碼中包含大量注釋來說明Cocos2d-x中的觸摸事件使用示例,需要的朋友可以參考下2014-09-09