tree[i] != -1是什么意思

在算法或数据结构中，tree[i] != -1 表示节点 i 存在父节点。通常情况下，tree 数组表示一棵树的结构，tree[i] 表示节点 i 的父节点。如果 tree[i] 的值为 -1，则表示节点 i 没有父节点，即它是树的根节点。因此，当 tree[i] != -1 时，节点 i 存在父节点。

相关问题

#include<stdio.h> #include<stdlib.h> int a[31], b[31]; typedef struct treeNode* tree; struct treeNode { int data; tree left, right; }; tree creat() { tree p = (tree)malloc(sizeof(tree)); p->left = p->right = NULL; return p; } tree find(int z1, int x1, int x2)//寻找根节点 { int i; tree head = creat(); head->data = a[z1]; for (i = x1; i <= x2; i++) { if (a[z1] == b[i]) { if(i!=x1) //有左支树 head->left=find(z1-(x2-i)-1,x1,i-1); if(i!=x2) //有右支树 head->right=find(z1-1,i+1,x2); } } return head; } void PreOrder(tree head) { if (head) { printf(" %d", head->data); PreOrder(head->left); PreOrder(head->right); } } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &a[i]); } for (int i = 0; i < n; i++) { scanf("%d", &b[i]); } tree head = find(n - 1, 0, n - 1); printf("Preorder:"); PreOrder(head); return 0; }

这是一段 C 语言的代码，实现了根据二叉树的前序遍历序列和中序遍历序列构建二叉树，并输出二叉树的前序遍历序列。

具体实现方法是，先根据前序遍历序列的第一个节点确定根节点，然后在中序遍历序列中找到根节点的位置，将中序遍历序列分为左子树和右子树，再分别递归处理左子树和右子树，构建整个二叉树。

需要注意的是，这个程序假设输入的前序遍历序列和中序遍历序列是合法的，并且不包含重复的节点。

#include<stdio.h> typedef struct node{ int data; struct node *lchild,*rchild; }Tree; Tree* CreatTree(int in[],int post[],int n) { if(n==0) return NULL; int i; Tree *tree=(Tree*)malloc(sizeof(Tree)); tree->data=post[n-1]; for(i=0;i<n;i++) if(post[n-1]==in[i]) break; tree->lchild=CreatTree(in,post,i); tree->rchild=CreatTree(in+i+1,post+i,n-i-1); return tree; } void CountTree(Tree* tree) { if(tree!=NULL) { printf(" %d",tree->data); CountTree(tree->lchild); CountTree(tree->rchild); } } int main() { int n,i,j; int post[100001],in[100001]; scanf("%d",&n); for(i=0;i<n;i++) scanf("%d",&post[i]); for(i=0;i<n;i++) scanf("%d",&in[i]); Tree* tree=CreatTree(in,post,n); printf("Preorder:"); CountTree(tree); }

这是一段 C 语言代码，实现了根据中序遍历和后序遍历构建二叉树，并输出先序遍历结果。具体来说，代码中定义了一个结构体 `Tree`，表示二叉树的节点，包含节点的值 `data`，以及左右子树的指针 `lchild` 和 `rchild`。函数 `CreatTree` 是根据中序遍历数组 `in[]` 和后序遍历数组 `post[]` 构建二叉树的函数，通过递归实现。函数 `CountTree` 是输出二叉树先序遍历结果的函数，同样也是通过递归实现。在 `main` 函数中，先读入节点个数 `n`，以及中序遍历和后序遍历数组，然后调用 `CreatTree` 函数构建二叉树，并调用 `CountTree` 函数输出先序遍历结果。