linked-list - 二叉树遍历中序输出错误为什么?
问题描述
有人可以解释为什么我的输出错误以及如何解决吗?
例如:我将输入 ABCDE
输出给我 ABCDE
中序遍历:DBEAC
这是我的代码:
int main()
{
struct node *root = NULL;
int choice, n; // item
char item;
do
{
printf("\n1. Insert Node");
printf("\n2. Traverse in Inorder");
printf("\nEnter Choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:
root = NULL;
printf("\n\n Nodes : ");
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
printf("\nEnter data for node %d : ", i);
scanf(" %c",&item);
root = Create(root,item);
}
break;
case 2:
printf("\nBST Traversal in INORDER \n");
Inorder(root); break;
default:
printf("\n\nINVALID OPTION TRY AGAIN\n\n"); break;
}
} while(choice != 3);
}
struct node *Create(struct node *root, char item)
{
if(root == NULL)
{
root = (struct node *)malloc(sizeof(struct node));
root->left = root->right = NULL;
root->data = item;
return root;
}
else
{
if(item < root->data )
root->left = Create(root->left,item);
else if(item > root->data )
root->right = Create(root->right,item);
else
printf(" Duplicate Element !! Not Allowed !!!");
return(root);
}
}
void Inorder(struct node *root)
{
if( root != NULL)
{
Inorder(root->left);
printf(" %c ",root->data);
Inorder(root->right);
}
}
我仔细检查了遍历顺序的算法,但我的输出仍然错误我不明白为什么?我在这里错过了什么吗
解决方案
结果符合预期。中序遍历不应为您输入 ABCDE 生成 DBEAC
这就是树的构造方式。
首先用值 A 创建根
然后插入 B。当 B > A 时,它作为根的右孩子插入:
A
\
B
然后插入 B。当 C > A 时,它被插入到右子树中。我们再次发现 C > B,因此新节点将作为 B 的右子节点插入:
A
\
B
\
C
以同样的方式插入 D,然后插入 E,给出这棵树:
A
\
B
\
C
\
D
\
E
请注意,这棵树根本不平衡。当您按照词法顺序插入节点时,就会发生这种情况。如果您以更随机的顺序插入它们,我们希望树更平衡。
但实际上对于有序遍历并不重要。您实现的是二叉搜索树 (BST)。BST 的一个重要特性是它们的中序遍历总是以正确的顺序生成数据。因此,无论您输入字母 ABCD 和 E 的顺序如何,中序遍历都应始终输出以下序列:
A B C D E
这是对的。
推荐阅读
- android - SonarQube 中每个拉取请求的 Android 代码覆盖率
- c++ - 主文件在 stdafx.h 中看不到包含的标头
- python - ValueError:已经使用 dropna() 后无法将浮点 NaN 转换为整数
- angular - 跨度和强标签之间的角度间距
- ios - 领域迁移问题。如何更新应该在其中的数据
- javascript - Array.includes() 在数组中查找对象
- python - 使用 Django/Python 创建初学者应用程序:ModuleNotFoundError: No module named 'pages'
- javascript - react-native - 图像未在 Android 上呈现
- linux - Ubuntu 16.04 上的 ng 服务问题
- for-loop - 我的 for of 循环在 1 次迭代后一直停止