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;
}

相关内容

热门资讯

oppo安卓11.1系统新功能... 你知道吗?最近OPPO手机又来了一次大升级,安卓11.1系统的新功能简直让人眼前一亮!今天,就让我带...
win10系统和安卓系统的,全... 你有没有发现,现在手机和电脑的操作系统真是五花八门,让人挑花了眼?今天,咱们就来聊聊两个超级热门的系...
安卓怎么设置重力系统,安卓重力... 你有没有发现,有时候手机屏幕上的图标会自动旋转,就像有看不见的小手在帮你翻书一样?这就是安卓手机的重...
图片管家推荐安卓系统,图片管家... 手机里的图片是不是越来越多,乱糟糟的找不到?别急,今天就来给你安利一款超好用的安卓系统图片管家——它...
安卓2.3系统宣传片,无限可能 你有没有注意到,手机的世界里,有时候一个小小的系统更新就能掀起一阵热潮呢?今天,就让我带你穿越回那个...
有关安卓和苹果系统提问,全面对... 你有没有想过,为什么你的手机里装的是安卓系统,而你的朋友用的是苹果?是不是好奇这两个系统有什么不同?...
安卓系统清理排行榜,助你手机焕... 手机里的安卓系统是不是越来越慢了?别急,今天就来给你揭秘一下安卓系统清理排行榜,让你手机瞬间恢复活力...
安卓系统app自动启动不了,安... 手机里的安卓系统APP突然不自动启动了,这可真是让人头疼啊!你是不是也遇到了这种情况?别急,今天就来...
ios系统和安卓系统哪个才是未... 说到手机操作系统,你是不是也和我一样,对iOS系统和安卓系统哪个才是未来充满了好奇呢?毕竟,这两个系...
最丝滑的安卓系统,最丝滑安卓系... 你有没有想过,手机系统就像是我们生活中的调味品,有时候平淡无奇,有时候却让人回味无穷。今天,就让我带...
笔记本安卓系统下载,下载与使用... 你有没有想过,你的安卓笔记本也能拥有一个全新的操作系统呢?没错,就是那种可以让你在笔记本上畅游安卓世...
老年人安卓手机系统,畅享智能生... 你有没有发现,身边越来越多的老年人开始玩起了智能手机呢?这不,最近我注意到,他们中很多人选择了安卓手...
安卓手机系统大改造,重塑未来 你有没有发现,最近你的安卓手机好像变得不一样了?没错,安卓手机系统正在经历一场大改造,就像换上了新装...
能安装安卓应用的系统,探索无限... 你有没有想过,为什么你的手机可以安装那么多好玩的应用,而电脑就只能用那些固定的软件呢?其实,现在有一...
安卓系统备份备忘录,轻松备份与... 你有没有想过,那些藏在安卓手机里的备忘录,它们就像是你生活中的小秘密,随时准备着为你提供帮助?今天,...
欧沃手机安卓系统,畅享智能生活... 你有没有发现,最近手机市场又掀起了一股热潮?没错,就是欧沃手机!这款手机凭借其出色的性能和亲民的价格...
安卓4.4系统tv软件,探索安... 亲爱的读者们,你是否曾为家里的电视屏幕增添一些智能的魔力而烦恼?别担心,今天我要给你带来一个超级实用...
安卓系统的研究人物,安卓系统发... 你知道吗?在科技飞速发展的今天,安卓系统可是占据了智能手机市场的大半壁江山。而在这片广阔的天地里,有...
山寨苹果刷会安卓系统,安卓系统... 你知道吗?在科技圈里,总有一些让人眼前一亮的小秘密。今天,我要给你揭秘一个关于山寨苹果刷安卓系统的神...
安卓系统新用户登录,畅享智能生... 你刚刚入手了一台全新的安卓手机,是不是有点小激动呢?别急,别急,让我来给你详细介绍一下安卓系统新用户...