C++簡單又輕松建立鏈?zhǔn)蕉鏄淞鞒?/h1>
更新時間:2022年06月07日 09:30:13 作者:葉落秋白
二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)是指,用鏈表來表示一棵二叉樹,即用鏈來指示元素的邏輯關(guān)系。通常的方法是鏈表中每個結(jié)點(diǎn)由三個域組成,數(shù)據(jù)域和左右指針域,左右指針分別用來給出該結(jié)點(diǎn)左孩子和右孩子所在的鏈結(jié)點(diǎn)的存儲地址
遞歸建立二叉樹
二叉樹的結(jié)構(gòu)體
typedef struct Node
{
int data;
Node* lchild;
Node* rchild;
}BiNode,*BiTree;
二叉樹顧名思義最多只有兩個子結(jié)點(diǎn)和一個數(shù)據(jù)域,既然是鏈?zhǔn)侥敲醋咏Y(jié)點(diǎn)定義為結(jié)點(diǎn)指針類型,數(shù)據(jù)域就可以根據(jù)需要設(shè)置了,可以是整型也可以是字符型。
二叉樹初始化
BiTree createBiTree(BiTree &T)
{
int d;
cin >> d;
if (d == 0)
T = NULL;
else
{
T = (BiTree)malloc(sizeof(BiNode));
T->data = d;
T->lchild = createBiTree(T->lchild);
T->rchild = createBiTree(T->rchild);
}
return T;
}
這個初始化函數(shù)的返回值為BiTree是一個結(jié)構(gòu)體指針類型,用來返回初始化后的 T 二叉樹;整型數(shù)據(jù)d是用來給二叉樹的結(jié)點(diǎn)賦值的,當(dāng)輸入0的時候,該結(jié)點(diǎn)為空結(jié)點(diǎn);當(dāng)結(jié)點(diǎn)的數(shù)據(jù)域不為零,給該結(jié)點(diǎn)動態(tài)分配內(nèi)存空間,并把d賦值給T->data;然后就是對左右子樹的遞歸初始化了。
先序遍歷
void PreOrder(BiTree T)//先序
{
if (T)
{
cout << T->data<<" ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
先序遍歷就是先訪問根結(jié)點(diǎn),在訪問左子樹,最后訪問右子樹,這里也寫成遞歸形式;先訪問當(dāng)前結(jié)點(diǎn)的數(shù)據(jù),再對左右子樹進(jìn)行訪問。
中序遍歷
void InOrder(BiTree T)//中序
{
if (T != NULL)
{
PreOrder(T->lchild);
cout << T->data << " ";
PreOrder(T->rchild);
}
}
中序遍歷就是先訪問左子樹,在訪問根結(jié)點(diǎn),最后訪問右子樹,這里也寫成遞歸形式;先訪問當(dāng)前結(jié)點(diǎn)的左子樹的數(shù)據(jù),再對該結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行訪問,最后對右子樹進(jìn)行訪問。
后序遍歷
void PostOrder(BiTree T)//后序
{
if (T)
{
PreOrder(T->lchild);
PreOrder(T->rchild);
cout << T->data << " ";
}
}
后序遍歷就是先訪問左子樹,在訪問右子樹,最后訪問根結(jié)點(diǎn),這里也寫成遞歸形式;先訪問當(dāng)前結(jié)點(diǎn)的左子樹的數(shù)據(jù),再對右子樹進(jìn)行訪問,最后訪問根結(jié)點(diǎn)。
具體例題
參考上面的結(jié)構(gòu)體,設(shè)計一個函數(shù),要求能夠同時求出二叉樹中所有結(jié)點(diǎn)的的個數(shù)和二叉樹中數(shù)據(jù)為奇數(shù)的和;
我的思考:該函數(shù)傳入m和n兩個全局變量,使用引用傳遞;當(dāng)樹不為空時,m++,n等于n加該結(jié)點(diǎn)數(shù)據(jù)域的值,接下來進(jìn)行左右子樹的遞歸調(diào)用:
void countT(BiTree T, int &m, int &n)
{
if (T == NULL) return ;
if (T->data % 2 != 0) n += T->data;
m++;
countT(T->lchild, m, n);
countT(T->rchild, m, n);
}
從主函數(shù)中這樣調(diào)用:
int m = 0,n = 0;
BiTree T=NULL;
countT(T, m, n);
最后輸出m和n的值即可
效果截圖:

注意輸出的格式,必須是樹的形式,下面解析一下
輸入的格式
注意:輸入的格式必須是樹的先序遍歷形式,因為在這個程序中初始化二叉樹就是用的先序的方式

在這個二叉樹先序輸入數(shù)據(jù):3 4 6 0 8 0 0 0 11 13 0 0 0

全部源碼
粘貼到C++編譯器就能使用
#include<iostream>
using namespace std;
typedef struct Node
{
int data;
Node* lchild;
Node* rchild;
}BiNode,*BiTree;
BiTree createBiTree(BiTree &T)
{
int d;
cin >> d;
if (d == 0)
T = NULL;
else
{
T = (BiTree)malloc(sizeof(BiNode));
T->data = d;
T->lchild = createBiTree(T->lchild);
T->rchild = createBiTree(T->rchild);
}
return T;
}
void PreOrder(BiTree T)//先序
{
if (T)
{
cout << T->data<<" ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void InOrder(BiTree T)//中序
{
if (T)
{
InOrder(T->lchild);
cout << T->data << " ";
InOrder(T->rchild);
}
}
void PostOrder(BiTree T)//后序
{
if (T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
cout << T->data << " ";
}
}
void countT(BiTree T, int &m, int &n)
{
if (T == NULL) return ;
if (T->data % 2 != 0) n += T->data;
m++;
countT(T->lchild, m, n);
countT(T->rchild, m, n);
}
int main()
{
int m = 0,n = 0;
BiTree T=NULL;
cout << "輸入先序遍歷結(jié)點(diǎn),建立二叉樹" << endl;
T = createBiTree(T);
cout << "先序遍歷結(jié)果" << endl;
PreOrder(T);
cout << endl;
cout << "中序遍歷結(jié)果" << endl;
InOrder(T);
cout << endl;
cout << "后序遍歷結(jié)果" << endl;
PostOrder(T);
cout << endl;
countT(T, m, n);
cout << "結(jié)點(diǎn)個數(shù)為:" << m << endl;
cout << "數(shù)據(jù)為:" << n << endl;
}
總結(jié)
代碼不是很長,每一個功能都對應(yīng)一個函數(shù),希望大家可以迅速掌握二叉鏈的基本使用,加油!
如果覺得寫得好,記得點(diǎn)贊支持一下哦
到此這篇關(guān)于C++簡單又輕松建立鏈?zhǔn)蕉鏄淞鞒痰奈恼戮徒榻B到這了,更多相關(guān)C++鏈?zhǔn)蕉鏄鋬?nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
-
C++?Opencv實(shí)現(xiàn)錄制九宮格視頻
這篇文章主要為大家介紹了如何利用C++和OpenCV庫實(shí)現(xiàn)錄制九宮格視頻,文中的示例代碼講解詳細(xì),對我們學(xué)習(xí)OpenCV有一定幫助,感興趣的可以了解一下 2022-05-05
-
C++ 動態(tài)創(chuàng)建按鈕及 按鈕的消息響應(yīng)
這篇文章主要介紹了C++ 動態(tài)創(chuàng)建按鈕及 按鈕的消息響應(yīng)的相關(guān)資料,需要的朋友可以參考下 2015-06-06
-
關(guān)于C語言多線程pthread庫的相關(guān)函數(shù)說明
下面小編就為大家?guī)硪黄P(guān)于C語言多線程pthread庫的相關(guān)函數(shù)說明。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧 2017-05-05
-
用C語言實(shí)現(xiàn)圣誕樹(簡易版+進(jìn)階版)
大家好,本篇文章主要講的是用C語言實(shí)現(xiàn)圣誕樹(簡易版+進(jìn)階版),感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽 2021-12-12
最新評論
遞歸建立二叉樹
二叉樹的結(jié)構(gòu)體
typedef struct Node { int data; Node* lchild; Node* rchild; }BiNode,*BiTree;
二叉樹顧名思義最多只有兩個子結(jié)點(diǎn)和一個數(shù)據(jù)域,既然是鏈?zhǔn)侥敲醋咏Y(jié)點(diǎn)定義為結(jié)點(diǎn)指針類型,數(shù)據(jù)域就可以根據(jù)需要設(shè)置了,可以是整型也可以是字符型。
二叉樹初始化
BiTree createBiTree(BiTree &T) { int d; cin >> d; if (d == 0) T = NULL; else { T = (BiTree)malloc(sizeof(BiNode)); T->data = d; T->lchild = createBiTree(T->lchild); T->rchild = createBiTree(T->rchild); } return T; }
這個初始化函數(shù)的返回值為BiTree是一個結(jié)構(gòu)體指針類型,用來返回初始化后的 T 二叉樹;整型數(shù)據(jù)d是用來給二叉樹的結(jié)點(diǎn)賦值的,當(dāng)輸入0的時候,該結(jié)點(diǎn)為空結(jié)點(diǎn);當(dāng)結(jié)點(diǎn)的數(shù)據(jù)域不為零,給該結(jié)點(diǎn)動態(tài)分配內(nèi)存空間,并把d賦值給T->data;然后就是對左右子樹的遞歸初始化了。
先序遍歷
void PreOrder(BiTree T)//先序 { if (T) { cout << T->data<<" "; PreOrder(T->lchild); PreOrder(T->rchild); } }
先序遍歷就是先訪問根結(jié)點(diǎn),在訪問左子樹,最后訪問右子樹,這里也寫成遞歸形式;先訪問當(dāng)前結(jié)點(diǎn)的數(shù)據(jù),再對左右子樹進(jìn)行訪問。
中序遍歷
void InOrder(BiTree T)//中序 { if (T != NULL) { PreOrder(T->lchild); cout << T->data << " "; PreOrder(T->rchild); } }
中序遍歷就是先訪問左子樹,在訪問根結(jié)點(diǎn),最后訪問右子樹,這里也寫成遞歸形式;先訪問當(dāng)前結(jié)點(diǎn)的左子樹的數(shù)據(jù),再對該結(jié)點(diǎn)的數(shù)據(jù)進(jìn)行訪問,最后對右子樹進(jìn)行訪問。
后序遍歷
void PostOrder(BiTree T)//后序 { if (T) { PreOrder(T->lchild); PreOrder(T->rchild); cout << T->data << " "; } }
后序遍歷就是先訪問左子樹,在訪問右子樹,最后訪問根結(jié)點(diǎn),這里也寫成遞歸形式;先訪問當(dāng)前結(jié)點(diǎn)的左子樹的數(shù)據(jù),再對右子樹進(jìn)行訪問,最后訪問根結(jié)點(diǎn)。
具體例題
參考上面的結(jié)構(gòu)體,設(shè)計一個函數(shù),要求能夠同時求出二叉樹中所有結(jié)點(diǎn)的的個數(shù)和二叉樹中數(shù)據(jù)為奇數(shù)的和;
我的思考:該函數(shù)傳入m和n兩個全局變量,使用引用傳遞;當(dāng)樹不為空時,m++,n等于n加該結(jié)點(diǎn)數(shù)據(jù)域的值,接下來進(jìn)行左右子樹的遞歸調(diào)用:
void countT(BiTree T, int &m, int &n) { if (T == NULL) return ; if (T->data % 2 != 0) n += T->data; m++; countT(T->lchild, m, n); countT(T->rchild, m, n); }
從主函數(shù)中這樣調(diào)用:
int m = 0,n = 0;
BiTree T=NULL;
countT(T, m, n);
最后輸出m和n的值即可
效果截圖:
注意輸出的格式,必須是樹的形式,下面解析一下
輸入的格式
注意:輸入的格式必須是樹的先序遍歷形式,因為在這個程序中初始化二叉樹就是用的先序的方式
在這個二叉樹先序輸入數(shù)據(jù):3 4 6 0 8 0 0 0 11 13 0 0 0
全部源碼
粘貼到C++編譯器就能使用
#include<iostream> using namespace std; typedef struct Node { int data; Node* lchild; Node* rchild; }BiNode,*BiTree; BiTree createBiTree(BiTree &T) { int d; cin >> d; if (d == 0) T = NULL; else { T = (BiTree)malloc(sizeof(BiNode)); T->data = d; T->lchild = createBiTree(T->lchild); T->rchild = createBiTree(T->rchild); } return T; } void PreOrder(BiTree T)//先序 { if (T) { cout << T->data<<" "; PreOrder(T->lchild); PreOrder(T->rchild); } } void InOrder(BiTree T)//中序 { if (T) { InOrder(T->lchild); cout << T->data << " "; InOrder(T->rchild); } } void PostOrder(BiTree T)//后序 { if (T) { PostOrder(T->lchild); PostOrder(T->rchild); cout << T->data << " "; } } void countT(BiTree T, int &m, int &n) { if (T == NULL) return ; if (T->data % 2 != 0) n += T->data; m++; countT(T->lchild, m, n); countT(T->rchild, m, n); } int main() { int m = 0,n = 0; BiTree T=NULL; cout << "輸入先序遍歷結(jié)點(diǎn),建立二叉樹" << endl; T = createBiTree(T); cout << "先序遍歷結(jié)果" << endl; PreOrder(T); cout << endl; cout << "中序遍歷結(jié)果" << endl; InOrder(T); cout << endl; cout << "后序遍歷結(jié)果" << endl; PostOrder(T); cout << endl; countT(T, m, n); cout << "結(jié)點(diǎn)個數(shù)為:" << m << endl; cout << "數(shù)據(jù)為:" << n << endl; }
總結(jié)
代碼不是很長,每一個功能都對應(yīng)一個函數(shù),希望大家可以迅速掌握二叉鏈的基本使用,加油!
如果覺得寫得好,記得點(diǎn)贊支持一下哦
到此這篇關(guān)于C++簡單又輕松建立鏈?zhǔn)蕉鏄淞鞒痰奈恼戮徒榻B到這了,更多相關(guān)C++鏈?zhǔn)蕉鏄鋬?nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++?Opencv實(shí)現(xiàn)錄制九宮格視頻
這篇文章主要為大家介紹了如何利用C++和OpenCV庫實(shí)現(xiàn)錄制九宮格視頻,文中的示例代碼講解詳細(xì),對我們學(xué)習(xí)OpenCV有一定幫助,感興趣的可以了解一下2022-05-05C++ 動態(tài)創(chuàng)建按鈕及 按鈕的消息響應(yīng)
這篇文章主要介紹了C++ 動態(tài)創(chuàng)建按鈕及 按鈕的消息響應(yīng)的相關(guān)資料,需要的朋友可以參考下2015-06-06關(guān)于C語言多線程pthread庫的相關(guān)函數(shù)說明
下面小編就為大家?guī)硪黄P(guān)于C語言多線程pthread庫的相關(guān)函數(shù)說明。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2017-05-05用C語言實(shí)現(xiàn)圣誕樹(簡易版+進(jìn)階版)
大家好,本篇文章主要講的是用C語言實(shí)現(xiàn)圣誕樹(簡易版+進(jìn)階版),感興趣的同學(xué)趕快來看一看吧,對你有幫助的話記得收藏一下,方便下次瀏覽2021-12-12