1. 二叉树是树吗?它的定义为什么是递归的? 2. 三种根序遍历主要思路是什么? 3 先序遍历二叉树的递归算法怎样理解???????????(严蔚...
\u6309\u7167\u4e8c\u53c9\u6811\u7684\u9012\u5f52\u5b9a\u4e49,\u5bf9\u4e8c\u53c9\u6811\u904d\u5386\u7684\u5e38\u7528\u7b97\u6cd5\u6709\u54ea\u4e09\u79cd?/*1 \u3001\u524d\u5e8f\u904d\u5386\u4e8c\u53c9\u6811\u7684\u9012\u5f52\u7b97\u6cd5 */
void preorder(bintree t)
{
if (t) {
printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
/*2 \u3001\u4e2d\u5e8f\u904d\u5386\u4e8c\u53c9\u6811\u7684\u9012\u5f52\u7b97\u6cd5 */
void inorder(bintree t)
{
if (t) {
inorder(t->lchild);
printf("%c",t->data);
inorder(t->rchild);
}
}
/*3 \u3001\u540e\u5e8f\u904d\u5386\u4e8c\u53c9\u6811\u7684\u9012\u5f52\u7b97\u6cd5 */
void postorder(bintree t)
{
if (t) {
postorder(t->lchild);
postorder(t->rchild);
printf("%c",t->data);
}
}
\u5148\u5e8f\u8c03\u7528\u7684\u65f6\u5019\uff0c\u9012\u5f52\u51fd\u6570\uff0c\u5148\u5e8f\u51fd\u6570\u4f1a\u4e00\u76f4\u9012\u5f52\uff0c\u76f4\u5230t->next\u4e3a\u7a7a\uff0c\u5373t\u4e3a\u53f6\u8282\u70b9\uff0c\u9700\u8981\u6ce8\u610f\u7684\u662f\u5f53t->next \u4e3a\u7a7a\u65f6\uff0c\u51fd\u6570\u7684\u5b9e\u53c2\u6ca1\u6709\u4f20\u8fc7\u53bb\uff0c\u6240\u4ee5t\u6307\u5411\u53f6\u7ed3\u70b9\u7684\u7236\u8282\u70b9\uff0c\u66f4\u8981\u6ce8\u610f\u7684\u662f\uff0c\u5148\u5e8f\u8c03\u7528\u7684\u9012\u5f52\u51fd\u6570\u8fd8\u6ca1\u6267\u884c\u5b8c\uff0c\u5728\u5148\u5e8f\u8c03\u7528\u7684\u6700\u91cc\u5c42\uff0c\u8981\u6267\u884c\u8fd9\u4e2a\u51fd\u6570\u7684\u6700\u540e\u4e00\u4e2a\u8bed\u53e5\uff0c\u5373\u5148\u5e8f\u8bbf\u95ee\u53f3\u5b50\u6811\u3002
\u5728\u4e86\u89e3\u9012\u5f52\u51fd\u6570\u65f6\uff0c\u8981\u6ce8\u610f\u51fd\u6570\u662f\u4e00\u5c42\u4e00\u5c42\u6267\u884c\u7684\uff0c\u628a\u6ca1\u6709\u8c03\u7528\u7684\u51fd\u6570\u770b\u4f5c\u54e6\u662f\u7b2c\u4e00\u5c42\uff0c\u7b2c\u4e00\u6b21\u8c03\u7528\u7684\u65f6\u5019\uff0c\uff0c\u52bf\u5fc5\u4f1a\u7b2c\u4e8c\u6b21\u9047\u5230\u8c03\u7528\u51fd\u6570\uff0c\u53d8\u6210\u7b2c\u4e8c\u5c42\uff0c\uff0c\uff0c\uff0c
二叉树(Binary tree)是一种算法结构,是树形结构的一种。因为存储结构及其算法都较为简单,好理解,所以应用比较广泛。二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。
递归是算法的一种,它是指一种通过重复将问题分解为同类的子问题而解决问题的方法。而二叉树从算法定义上看,或者是实际编程,3种遍历方式,都符合递归算法的特征。
二叉树递归遍历分为先序遍历、中序遍历和后序遍历。
先序遍历为:根节点+左子树+右子树
中序遍历为:左子树+根节点+右子树
后序遍历为:左子树+右子树+根节点
(你只要记住根节点在哪里就是什么遍历,且都是先左再右)
举个例子,如二叉树:
请点击输入图片描述
这棵树的先序遍历为:1 2 3 4 5
中序遍历为:2 1 4 3 5
后序遍历为:2 4 5 4 1
扩展阅读:完全三叉树 ... 二叉树长什么样子 ... 采伐树木 法律 规定 ... 二叉树变森林的图解 ... 最优二叉树唯一吗 ... 二叉树的遍历流程图 ... 二叉树的4种遍历方法图解 ... 二叉树各个名词的定义 ... 树之歌11种树的图片 ...