網站首頁 編程語言 正文
一、思想（先序思想創建）
第一步先創建根節點,然后創建根節點左子樹,開始遞歸創建左子樹，直到遞歸創建到的節點下不繼續創建左子樹，也就是當下遞歸到的節點下的左子樹指向NULL，結束本次左子樹遞歸，返回這個節點的上一個節點，開始創建右子樹，然后又開始以當下這個節點，繼續遞歸創建左子樹，左子樹遞歸創建完，就遞歸創建右子樹，直到遞歸結束返回到上一級指針節點（也就是根節點下），此時根節點左邊子樹創建完畢，開始創建右邊子樹，原理和根節點左邊創建左右子樹相同
二、創建二叉樹
二叉樹的操作通常使用遞歸方法，如果遞歸不太明白，建議去對此進行一下學習和練習。二叉樹的操作可以分為兩類，一類是需要改變二叉樹的結構的，比如二叉樹的創建、節點刪除等等，這類操作，傳入的二叉樹的節點參數為二叉樹指針的地址，這種參入傳入，便于更改二叉樹結構體的指針（即地址）。這里稍微有一點點繞，可能需要多思考一下
如下是二叉數創建的函數，這里我規定，節點值為整數，如果輸入的數為-1，則表示結束繼續往下創建子節點的操作。然后我們使用遞歸的方法以此創建左子樹和右子樹
二叉樹結構體初始化：
為了更方便的使用二叉樹結構體，可以使用 typedef 對結構體進行命名
typedef struct Tree{
?
?int data;?? ??? ??? ??? ??? ?//?? ?存放數據域
?struct Tree *lchild;?? ??? ??? ?//?? ?遍歷左子樹指針
?struct Tree *rchild;?? ??? ??? ?//?? ?遍歷右子樹指針
?
}Tree,*BitTree;這里展示兩種傳參類型的創建方法，其中深意可多次參考理解，加深指針理解
(1)傳一級參數方法
BitTree CreateLink()
{
?? ?int data;
?? ?int temp;
?? ?BitTree T;
?? ?
?? ?scanf("%d",&data);?? ??? ?//?? ?輸入數據
?? ?temp=getchar();?? ??? ??? ?//?? ?吸收空格
?? ?
?? ?if(data == -1){?? ??? ??? ?//?? ?輸入-1 代表此節點下子樹不存數據，也就是不繼續遞歸創建
?? ??? ?
?? ??? ?return NULL;
?? ?}else{
?? ??? ?T = (BitTree)malloc(sizeof(Tree));?? ??? ??? ?//?? ??? ?分配內存空間
?? ??? ?T->data = data;?? ??? ??? ??? ??? ??? ??? ??? ?//?? ??? ?把當前輸入的數據存入當前節點指針的數據域中
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);?? ??? ?
?? ??? ?T->lchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始遞歸創建左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);?? ??? ??? ?
?? ??? ?T->rchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始到上一級節點的右邊遞歸創建左右子樹
?? ??? ?return T;?? ??? ??? ??? ??? ??? ??? ?//?? ??? ?返回根節點
?? ?}?? ?
?? ?
}
(2)傳二級參數方法
BitTree CreateLink(BitTree *T)?? ??? ?//?? ?次數 T為指向根節點的指針的地址
{
?? ?int data;?? ?
?? ?
?? ?scanf("%d",&data);
?? ?
?? ?if(data == -1){
?? ??? ?
?? ??? ?*T=NULL;?? ??? ??? ??? ?//?? ?結束遞歸時，讓指針當前節點的指針地址的 指針 指向NULL
?? ?}else{
?? ??? ?
?? ??? ?*T = (BitTree)malloc(sizeof(Tree));?? ??? ?//?? ?對指向節點指針地址的指針 分配內存
?? ?
?? ??? ?if(!(*T) ){?? ??? ??? ?//?? ?*T = NULL ?表示分配內存失敗，也就是結束遞歸創建了
?? ??? ??? ?printf("內存分配失敗\n");
?? ??? ??? ?exit(-1);
?? ??? ?}
?? ??? ?
?? ??? ?
?? ??? ?(*T)->data = data;?? ??? ?//?? ?給節點指針地址內的數據域，存入數據
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);
?? ??? ?CreateLink(&(*T)->lchild);?? ??? ?//?? ?開始遍歷左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);
?? ??? ?CreateLink(&(*T)->rchild);?? ??? ?//?? ?開始遍歷右子樹，遍歷的思想文章開頭處解釋
?? ??? ??? ?
?? ?}?? ?
?? ?
}
（1）一級參數完整例子：
#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
?
?int data;?? ??? ??? ??? ??? ?//?? ?存放數據域
?struct Tree *lchild;?? ??? ??? ?//?? ?遍歷左子樹指針
?struct Tree *rchild;?? ??? ??? ?//?? ?遍歷右子樹指針
?
}Tree,*BitTree;
BitTree CreateLink()
{
?? ?int data;
?? ?int temp;
?? ?BitTree T;
?? ?
?? ?scanf("%d",&data);?? ??? ?//?? ?輸入數據
?? ?temp=getchar();?? ??? ??? ?//?? ?吸收空格
?? ?
?? ?if(data == -1){?? ??? ??? ?//?? ?輸入-1 代表此節點下子樹不存數據，也就是不繼續遞歸創建
?? ??? ?
?? ??? ?return NULL;
?? ?}else{
?? ??? ?T = (BitTree)malloc(sizeof(Tree));?? ??? ??? ?//?? ??? ?分配內存空間
?? ??? ?T->data = data;?? ??? ??? ??? ??? ??? ??? ??? ?//?? ??? ?把當前輸入的數據存入當前節點指針的數據域中
?? ??? ?
?? ??? ?printf("請輸入%d的左子樹: ",data);?? ??? ?
?? ??? ?T->lchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始遞歸創建左子樹
?? ??? ?printf("請輸入%d的右子樹: ",data);?? ??? ??? ?
?? ??? ?T->rchild = CreateLink();?? ??? ??? ??? ??? ?//?? ??? ?開始到上一級節點的右邊遞歸創建左右子樹
?? ??? ?return T;?? ??? ??? ??? ??? ??? ??? ?//?? ??? ?返回根節點
?? ?}?? ?
?? ?
}
void ShowXianXu(BitTree T)?? ??? ??? ?//?? ??? ?先序遍歷二叉樹
{
?? ?if(T==NULL)
?? ?{
?? ??? ?return;
?? ?}
?? ?printf("%d ",T->data);
?? ?ShowXianXu(T->lchild);?? ??? ??? ?//?? ?遞歸遍歷左子樹
?? ?ShowXianXu(T->rchild);?? ??? ??? ?//?? ?遞歸遍歷右子樹
}
int main()
{
?? ?BitTree S;
?? ?printf("請輸入第一個節點的數據:\n");
?? ?S = CreateLink();?? ??? ??? ?//?? ??? ?接受創建二叉樹完成的根節點
?? ?ShowXianXu(S);?? ??? ??? ??? ?//?? ??? ?先序遍歷二叉樹
?? ?
?? ?return 0;?? ?
}?
（2）二級參數完整例子
#include<stdio.h>
#include<stdlib.h>
typedef struct Tree{
?? ?
?? ?int data;
?? ?struct Tree *lchild;
?? ?struct Tree *rchild;
}Tree,*BitTree;
BitTree CreateLink(BitTree *T)?? ??? ?//?? ?次數 T為指向根節點的指針的地址
{
?? ?int data;?? ?
?? ?
?? ?scanf("%d",&data);
?? ?
?? ?if(data == -1){
?? ??? ?
?? ??? ?*T=NULL;?? ??? ??? ??? ?//?? ?結束遞歸時，讓指針當前節點的指針地址的 指針 指向NULL
?? ?}else{
?? ??? ?
?? ??? ?*T = (BitTree)malloc(sizeof(Tree));?? ??? ?//?? ?對指向節點指針地址的指針 分配內存
?? ?
?? ??? ?if(!(*T) ){?? ??? ??? ?//?? ?*T = NULL ?表示分配內存失敗，也就是結束遞歸創建了
?? ??? ??? ?printf("內存分配失敗\n");
?? ??? ??? ?exit(-1);
?? ??? ?}
?? ??? ?
?? ??? ?
?? ??? ?(*T)->data = data;?? ??? ?//?? ?給節點指針地址內的數據域，存入數據
?? ??? ?
?? ??? ?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;?? ??? ??? ?//?? ?創建指向這個結構體指針地址 的指針
?? ?printf("請輸入第一個節點的數據:\n");
?? ?CreateLink(&S);?? ??? ?//?? ?傳二級指針地址
?? ?ShowXianXu(S);?? ??? ?
?? ?
?? ?return 0;?? ?
}?原文鏈接：https://blog.csdn.net/chinesekobe/article/details/110873792
相關推薦
- 2022-09-02 Pytorch-LSTM輸入輸出參數方式_python
- 2022-07-19 react props深入使用:children屬性、props校驗、props的默認值
- 2022-05-13 Shell腳本命令結果保存到變量，保留換行符
- 2022-08-05 Python?如何給圖像分類(圖像識別模型構建)_python
- 2022-09-22 git-lfs 離線安裝
- 2022-12-24 fetch()函數說明與使用方法詳解_基礎知識
- 2023-02-01 深入分析C語言存儲類型與用戶空間內部分布_C 語言
- 2022-12-06 React?Hook中的useEffecfa函數的使用小結_React
- 最近更新
-
- window11 系統安裝 yarn
- 超詳細win安裝深度學習環境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權
- redisson分布式鎖中waittime的設
- maven:解決release錯誤：Artif
- restTemplate使用總結
- Spring Security之安全異常處理
- MybatisPlus優雅實現加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務發現-Nac
- Spring Security之基于HttpR
- Redis 底層數據結構-簡單動態字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應用詳解
- 聊聊消息隊列，發送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速