C语言数据结构六:树。二叉树遍历。先序遍历,中序遍历,后序遍历。二叉树叶节点数,二叉树高度,二叉树拷贝;二叉树释放。
创始人
2024-06-03 11:07:15
0

(二叉)树中,一个节点,你也要把他看做成树。子树。一个节点都没有叫做空树。所以说:树具有递归性。

树是非线性结构,有一个直接前驱,但是可能有很多直接后继

树中,应用最多的还是二叉树。


二叉树的遍历

先(根)序遍历DLR,中(根)序遍历LDR,后(根)序遍历LRD。

无论哪种:首要顺序都是“先左后右”。

DLR先根序遍历:先序遍历,即先根再左再右。

LDR中根序遍历:中序遍历,即先左再根再右。

LRD后根序遍历:后序遍历,即先左再右再根。

说白了,就是说,你什么时候访问中间的根,如果先访问根,再左右,那么就是先序,把根放在中间,就是中序,如果先左后右最后跟,就是后序。

树是递归的,所以说上面的这个规则也是你递归的法则

每次递归到一棵子树,规则仍然如此。

先序遍历:第一棵树是A,然后到第二棵树,B子树,B为先,然后左右,AB,CDE,FGH。

中序遍历:先左后中。中序先看左边,左边是B子树,B子树也要按照中序来。左边没有所以就到了中间,所以先是B,然后右边又是一棵树,也要按照中序来,所以是BDCE,然后左边完事了,到中间,BDCE然后A,到右边了,右边也要按照中序排序。F没有左,所以直接F,F完事到右边了,右边是棵子树,先左H后G,所以:BDCE,A,FHG

后序遍历:先左再右再根。根树的话,先B,但是B是子树,所以也要按照先左再右最后根的顺序。所以B子树,先左,左为空,所以到右,右边C是子树,所以先DE然后DEC。然后再DECB。左边子树完成了,看右边,右边也是一颗子树,所以继续递归。F左空,右子树,是HGF,最后是根节点A。DECB,HGF,A。

永远牢记一点:树是递归的,树遍历的递归法法则是有三种顺序,这三种方法也是递归的规则。


现在开始编程实现:

首先是定义二叉树数据结构:二叉树结构体

二叉树有两个节点,左节点和右节点。我们分别用指针来代替。

因为它是递归的,所以也是node节点。结构体嵌套自身

struct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};

对树来说,拿到根节点,相当于拿到整个树。所以遍历时,只要输入根节点即可。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#includestruct BiNode
{char ch;struct BiNode *lchild;struct BiNode *rchild;
};//二叉树递归遍历
void recursion(struct BiNode *root)
{if (NULL == root){return;}//递归遍历左子树recursion(root->lchild);//递归遍历右子树recursion(root->rchild);printf("%c ", root->ch);}void test()
{struct BiNode nodeA = { 'A', NULL, NULL };struct BiNode nodeB = { 'B', NULL, NULL };struct BiNode nodeC = { 'C', NULL, NULL };struct BiNode nodeD = { 'D', NULL, NULL };struct BiNode nodeE = { 'E', NULL, NULL };struct BiNode nodeF = { 'F', NULL, NULL };struct BiNode nodeG = { 'G', NULL, NULL };struct BiNode nodeH = { 'H', NULL, NULL };nodeA.lchild = &nodeB;nodeA.rchild = &nodeF;nodeB.rchild = &nodeC;nodeC.lchild = &nodeD;nodeC.rchild = &nodeE;nodeF.rchild = &nodeG;nodeG.lchild = &nodeH;recursion(&nodeA);}int main(){test();system("pause");return EXIT_SUCCESS;
}

递归的输出条件是什么呢?

二叉树的递归结束标识是左右递归子树为空。即可。

上面是后序遍历。我们把它改为中序。

//二叉树递归遍历
void recursion(struct BiNode *root)
{if (NULL == root){return;}//递归遍历左子树recursion(root->lchild);// 中序遍历printf("%c ", root->ch);//递归遍历右子树recursion(root->rchild);}

先序如下:

//二叉树递归遍历
void recursion(struct BiNode *root)
{if (NULL == root){return;}// 先序遍历printf("%c ", root->ch);	//递归遍历左子树recursion(root->lchild);//递归遍历右子树recursion(root->rchild);}

计算叶节点数

遍历需求如上完成。

涉及二叉树有时还需要输出叶节点数。

叶节点,就是左右节点都为空即可。上面我已经可以遍历了,所以,每一次遍历节点都看看其左右节点情况即可。如果为空则输出即可。

int num = 0;
void cuculateLeafNum(struct BiNode *root)
{if (NULL == root){return;}if (root->lchild == NULL && root->rchild == NULL){num++;}cuculateLeafNum(root->lchild);cuculateLeafNum(root->rchild);
}

还是输入根节点。相当于输入了整个树,然后逐级递归即可。

有一个问题,我们在实际编程中,很少使用全局变量num,因为就为一个功能,而引入一个全局变量看起来并不划算。所以为此,为此,我们采用指针的形式。

void cuculateLeafNum(struct BiNode *root,int *p)
{if (NULL == root){return;}if (root->lchild == NULL && root->rchild == NULL){(*p)++;}cuculateLeafNum(root->lchild, p);cuculateLeafNum(root->rchild, p);
}

在实际C语言编程中,尽量少使用全局变量。



求二叉树高度

 我们求A的高度,只要求出B子树,和F子树的高度加上1即可,也就是递归的话,我们把所有子树的高度加上1即是当前子树的高度。递归,就是一级级子树去计算高度,直到当前子树高度为1则终止。最后高度等于=MAX(左子树高度,右子树高度) + 1。

int getTreeHeight(struct BiNode *root)
{if (NULL == root){return 0;}//求树的左子树高度int lheight = getTreeHeight(root->lchild);//求树的右子树高度int rheight = getTreeHeight(root->rchild);int height = lheight > rheight ? lheight + 1 : rheight + 1;return height;
}

 递归终止条件为子树为空。

最后三目运算符输出高度。

int height = lheight > rheight ? lheight + 1 : rheight + 1;


二叉树的拷贝

拷贝肯定也是一个递归的过程;就是把所有层级的子树左右节点输出挂到新的根节点下面。

//先拷贝左子树
struct BiNode *lchild = copyBiTree(root->lchild);
//拷贝右子树
struct BiNode *rchild = copyBiTree(root->rchild);

因为最后需要输出一份新的二叉树,所以我们需要建立一个新的二叉树根节点。

struct BiNode *newnode = malloc(sizeof(struct BiNode));

先获取左右,然后挂到根节点下。最后返回根节点。

struct BiNode *copyBiTree(struct BiNode *root)
{if (NULL == root){return NULL;}//先拷贝左子树struct BiNode *lchild = copyBiTree(root->lchild);//拷贝右子树struct BiNode *rchild = copyBiTree(root->rchild);struct BiNode *newnode = malloc(sizeof(struct BiNode));newnode->lchild = lchild;newnode->rchild = rchild;newnode->ch = root->ch;return newnode;
}

查看二叉树

void showBiTree(struct BiNode *root)
{if (NULL == root){return;}printf("%c ",root->ch);showBiTree(root->lchild);showBiTree(root->rchild);
}

二叉树的内存释放

释放也是先左右子节点,然后根节点,因为如果先释放根节点,左右就找不到了,造成内存泄漏。

void freeSpace(struct BiNode *root)
{if (NULL == root){return;}//释放左子数内存freeSpace(root->lchild);//释放右子树freeSpace(root->rchild);printf("%c 被释放!\n", root->ch);free(root);
}

测试代码 

void test()
{struct BiNode nodeA = { 'A', NULL, NULL };struct BiNode nodeB = { 'B', NULL, NULL };struct BiNode nodeC = { 'C', NULL, NULL };struct BiNode nodeD = { 'D', NULL, NULL };struct BiNode nodeE = { 'E', NULL, NULL };struct BiNode nodeF = { 'F', NULL, NULL };struct BiNode nodeG = { 'G', NULL, NULL };struct BiNode nodeH = { 'H', NULL, NULL };nodeA.lchild = &nodeB;nodeA.rchild = &nodeF;nodeB.rchild = &nodeC;nodeC.lchild = &nodeD;nodeC.rchild = &nodeE;nodeF.rchild = &nodeG;nodeG.lchild = &nodeH;//1. 求二叉树的叶子节点数目int num = 0;cuculateLeafNum(&nodeA, &num);printf("叶子节点数目:%d\n", num);//2. 求二叉树的高度int height = getTreeHeight(&nodeA);printf("树的高度:%d\n",height);//3. 拷贝二叉树struct BiNode *root = copyBiTree(&nodeA);showBiTree(root);printf("\n");showBiTree(&nodeA);freeSpace(root);
}int main(){test();system("pause");return EXIT_SUCCESS;
}

相关内容

热门资讯

安卓系统写脚本软件下载,基于安... 你有没有想过,你的安卓手机或者平板电脑,除了用来刷剧、玩游戏,还能变成一个强大的工作助手呢?没错,就...
安卓系统有哪些机型好,探索顶级... 你有没有想过,安卓系统里的手机型号那么多,哪一款才是最适合你的呢?别急,今天我就来给你好好盘点看看安...
安卓系统之间如何互传,安卓设备... 你是不是也和我一样,手机里存了那么多好东西,却苦于不能和好友分享呢?别急,今天就来教你怎么用安卓系统...
安卓系统启动修改工具,安卓系统... 你有没有想过,你的安卓手机启动速度竟然可以像火箭一样快?没错,这就是今天我要跟你分享的神秘工具——安...
安卓系统版本号历史,从初生到繁... 你有没有发现,每次打开手机,那系统版本号总是一闪而过,好像在悄悄告诉你:“我可是有故事的哦!”今天,...
小米改安卓系统软件,安卓系统软... 你知道吗?最近小米手机界可是掀起了一阵小小的风波呢!那就是小米对安卓系统软件的一次大改版。这可不是什...
安卓系统控制流量app,安卓系... 你有没有发现,手机里的流量就像小河里的水,不知不觉就流光了?别急,今天就来给你揭秘一款神奇的安卓系统...
hl2240安卓系统,功能解析... 你有没有发现,最近你的手机系统更新换代的速度简直就像坐上了火箭呢?今天,就让我带你来一探究竟,看看这...
iqoo刷原生安卓系统,还原纯... 最近手机圈里可是热闹非凡呢!一款名为iqoo的新品手机,凭借其强大的性能和独特的刷机功能,吸引了无数...
安卓系统我的读书入口,我的读书... 亲爱的手机控们,你是否也有这样的体验:每天手机不离手,却总是找不到心仪的读书应用?别急,今天我要给你...
搭载安卓9系统的手机,新一代智... 你有没有发现,最近市面上新出的手机,好像都开始搭载安卓9系统了呢?这可真是让人眼前一亮啊!今天,就让...
电脑模拟安卓系统win7系统,... 你有没有想过,如果电脑也能像手机一样,随时随地都能玩各种游戏、看视频呢?想象你坐在电脑前,屏幕上突然...
华为系统如何退回安卓,轻松实现... 你有没有想过,手机系统就像是我们生活中的衣服,有时候穿久了,就想换一件新的。比如,你之前用了华为的系...
安卓系统定制防沉迷手机,安卓手... 你有没有发现,现在的手机越来越智能,但随之而来的是沉迷于手机的问题也越来越严重,尤其是对青少年来说。...
安卓系统手机顶部符号,功能解析... 你有没有注意到,每次拿起安卓系统手机,顶部那一排小小的符号总是默默守护着你的屏幕?它们就像是一群小精...
美团餐饮系统安卓版,尽享美食新... 你有没有发现,最近点外卖的时候,手机上那个美团餐饮系统安卓版真是越来越方便了!今天,就让我带你来好好...
新生活cms安卓系统进货系统,... 你知道吗?最近市面上出现了一个超级酷的新玩意儿——新生活CMS安卓系统进货系统!这可是个让商家们眼睛...
安卓系统ai文章生成,探索安卓... 你知道吗?现在手机界的风云变幻,安卓系统可是当之无愧的王者!而且,最近听说安卓系统里还悄悄加入了AI...
推荐安卓车载导航系统,安卓平台... 你有没有想过,开车的时候,如果没有导航系统,那可真是像在茫茫大海中航行,没有指南针的感觉呢?别急,今...
安卓系统的地图怎样下载,下载与... 你有没有发现,现在不管去哪里,手机地图都成了我们的好帮手?尤其是安卓系统的地图,功能强大,用起来超级...