数据结构二叉树C语言

1个回答

恬静又完满灬小白杨N

专业答主服务有保障

关注

展开全部

摘要二叉树是一种非常重要的数据结构。本文总结了二叉树的常见操作：二叉树的构建，查找，删除，二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历)，二叉搜索树的构造等。

1. 二叉树的构建

二叉树的基本构建方式为:添加一个节点，如果这是一棵空树，则将该节点作为根节点；否则按照从左到右、先左子树后右子树的顺序逐个添加节点。比如依次添加节点:1,6,10,2,7,11，则得到的二叉树为:

在这里，我们需要借助一个链表来保存节点，以实现二叉树的顺序插入，具体做法如下：

1.0 初始化一个用来保存二叉树节点的空链表；

1.1 插入一个节点，

①如果该树是一棵空树，则将该节点作为根节点，并且将该节点添加到链表中；

②如果该树不为空，取得链表第一个节点的值(注意不是链表的头节点)。如果该节点左子树为空，则将待插入节点添加到左子树，并且将左子树添加到链表；否则将待插入节点添加到右子树，将右子树添加到链表。此时，父节点的左右子树都不为空，将该父节点(即链表第一个节点)

弹出。

按照这样的顺序，我们就可以完成二叉树节点的顺序插入。

2. 二叉搜索树的构建

二叉搜索树是这样一棵树：对于任意一个节点，其左子树的值均小于父节点的值；右子树的值均大于父节点的值。从二叉树的根节点开始，对于其左右子树均按照这样的方式递归插入，即可以得到一棵二叉搜索树。二叉搜索树具有很好的性质，因为它的有序性，如果在二叉搜索树中查找一个元素可以按照类似二分查找的方式进行；对于二叉搜索树，如果采用中序遍历则可以得到按照值递增排列的节点。二叉搜索树的具体构建方式如下：

插入一个节点：

2.1如果当前节点本身值为空，则将插入节点直接作为当前节点；

2.2如果当前节点本身值不为空，

①比较插入节点的值与当前节点的值，如果插入节点值小于当前节点值，则将该节点递归插入左子树；

②比较插入节点的值与当前节点的值，如果插入节点值大于当前节点值，则将该节点递归插入右子树；

③ 如果插入节点的值等于当前节点的值，则直接返回(即二叉搜索树每个节点的值都是不同的)。

咨询记录 · 回答于2021-05-18

数据结构二叉树C语言

二叉树是一种非常重要的数据结构。本文总结了二叉树的常见操作：二叉树的构建，查找，删除，二叉树的遍历(包括前序遍历、中序遍历、后序遍历、层次遍历)，二叉搜索树的构造等。1. 二叉树的构建二叉树的基本构建方式为:添加一个节点，如果这是一棵空树，则将该节点作为根节点；否则按照从左到右、先左子树后右子树的顺序逐个添加节点。比如依次添加节点:1,6,10,2,7,11，则得到的二叉树为:在这里，我们需要借助一个链表来保存节点，以实现二叉树的顺序插入，具体做法如下：1.0 初始化一个用来保存二叉树节点的空链表；1.1 插入一个节点，①如果该树是一棵空树，则将该节点作为根节点，并且将该节点添加到链表中；②如果该树不为空，取得链表第一个节点的值(注意不是链表的头节点)。如果该节点左子树为空，则将待插入节点添加到左子树，并且将左子树添加到链表；否则将待插入节点添加到右子树，将右子树添加到链表。此时，父节点的左右子树都不为空，将该父节点(即链表第一个节点)弹出。按照这样的顺序，我们就可以完成二叉树节点的顺序插入。2. 二叉搜索树的构建二叉搜索树是这样一棵树：对于任意一个节点，其左子树的值均小于父节点的值；右子树的值均大于父节点的值。从二叉树的根节点开始，对于其左右子树均按照这样的方式递归插入，即可以得到一棵二叉搜索树。二叉搜索树具有很好的性质，因为它的有序性，如果在二叉搜索树中查找一个元素可以按照类似二分查找的方式进行；对于二叉搜索树，如果采用中序遍历则可以得到按照值递增排列的节点。二叉搜索树的具体构建方式如下：插入一个节点：2.1如果当前节点本身值为空，则将插入节点直接作为当前节点；2.2如果当前节点本身值不为空，①比较插入节点的值与当前节点的值，如果插入节点值小于当前节点值，则将该节点递归插入左子树；②比较插入节点的值与当前节点的值，如果插入节点值大于当前节点值，则将该节点递归插入右子树；③ 如果插入节点的值等于当前节点的值，则直接返回(即二叉搜索树每个节点的值都是不同的)。

3.二叉搜索树的查找二叉搜索树的查找类似于二分查找。具体步骤如下：3.1 从根节点开始，比较查找值与当前节点值的大小：① 如果当前节点值为空，则说明无法查找到该值，直接返回；②如果当前节点值等于查找值，则查找成功；③如果查找值小于当前节点的值，则递归查找左子树；④如果查找值大于当前节点的值，则递归查找右子树。4. 二叉搜索树的删除二叉搜索树的删除与查找基本类似，不同之处在于如果查找到了待删除的节点，则将该节点直接删除之后，还要进行如下操作保证删除节点之后的二叉树仍是一棵二叉搜索树：①如果该删除节点没有左右子树，则直接删除该节点；②如果该删除节点只有左子树(右子树)，则将删除节点的父节点直接指向其左子树(右子树);③如果该删除节点既有左子树又有右子树，则有下面的三种处理方法：4.3.1：找到按照中序遍历该删除节点的直接前驱节点，将该节点转移到删除节点，然后删除这个前驱节点；4.3.2：找到按照中序遍历该删除节点的直接后续节点，将该节点转移到删除节点，然后删除这个后序节点；4.3.3：找到按照中序遍历该删除节点的直接前驱节点，将删除节点的左子树接到父节点上，将删除节点的右子树接到该前序节点的右子树上，然后删除节点。5. 二叉树的前序遍历由于二叉树是递归定义的，所以二叉树的遍历一般也是采用递归的形式。前序遍历即采用先访问根节点，再访问左子树，最后访问右子树的顺序。前序遍历也是按照类似的方式递归遍历，具体操作如下：① 如果当前节点值为空，返回；②如果当前节点值不为空，打印当前节点值；递归遍历左子树；递归遍历右子树。6. 二叉树的中序遍历①如果当前节点值为空，返回；②递归遍历左子树；打印当前节点的值；递归遍历右子树。7. 二叉树的后序遍历①如果当前节点值为空，返回；②递归遍历左子树；递归遍历右子树；打印当前节点的值。8. 二叉树的层次遍历二叉树的层次遍历，即从根节点开始，逐层按照从左到右的顺序遍历。层次遍历比前中后序遍历要麻烦一点，它需要借助一个额外的链表来保存节点进行遍历。具体做法如下：①初始化一个用来保存二叉树节点的空链表；②如果这是一棵空二叉树，直接返回；否则将根节点添加到链表；③while(当链表不为空时) 弹出链表第一个二叉树节点，打印该二叉树节点的值；如果该二叉树节点的

您好有代码吗

右子树不为空，则将该右子树添加到链表；以上就是关于二叉树的基本操作，下面是C语言具体实现的代码，谨供参考

您能看到我问题的具体内容吗

没有

由先序序列和中序序列以及由中序序列和后序

序列构造一棵二叉树的功能(二叉树中的每个结点值为单个字符),要求以括号表示和凹入

表示法输出该二叉树,并用先序遍历序列“ABDEHJKLMNCFGI”和中序遍历序列

“DBJHLKMNEAFCGI”以及由中序遍历序列“DBJ HLKMNEAFCGI”和后序遍历序列

DJLNMKHEBFIGCA”进行验证

你好，这方面我本来不太懂，因为点快点着单了，所以是尽可能的找些对你有用的资料。

好吧

已赞过

评论收起