2021-08-14 19:42

用非递归算法来数树的节点(求看看，请了！！)

#include "stdio.h"
#include<stdlib.h>
typedef struct Ttree
{int data;
struct Ttreelchild;
struct Ttree
rchild;
}tree;

typedef struct stack
{tree *data[100];
int top;
}stack;

tree*create(tree *T)
{T->data=1;
tree n1=NULL;
tree n2=NULL;
n1=(tree
)malloc(sizeof(tree));
n2=(tree
)malloc(sizeof(tree));

n1->data=2;
n2->data=3;
T->lchild=n1;
T->rchild=n2;
tree n3=NULL;
n3=(tree
)malloc(sizeof(tree));

n3->data=4;
n1->lchild=n3;
tree n4=NULL;
n4=(tree
)malloc(sizeof(tree));

n4->data=5;
n1->rchild=n4;
tree n5=NULL;
n5=(tree
)malloc(sizeof(tree));

n5->data=6;
n2->lchild=n5;
tree n6=NULL;
n6=(tree
)malloc(sizeof(tree));

n6->data=7;
n2->rchild=n6;
tree n7=NULL;
n7=(tree
)malloc(sizeof(tree));

n7->data=8;
n6->lchild=n7;
tree n8=NULL;
n8=(tree
)malloc(sizeof(tree));

n8->data=9;
n2->rchild=n8;
return T;
}

void initstack(stack *L)
{L->top=-1;
}

tree*count(tree *T,stack *L)
{tree *a[100];
int h,i;
h=0;
i=0;
tree p=NULL;
p=(tree
)malloc(sizeof(tree));
p=T;
L->top++;
L->data[L->top]=p;
while(L->top!=-1)
{
while(p->lchild!=NULL)
{L->top++;
L->data[L->top]=p->lchild;
p=p->lchild;
}
while(p!=T&&L->top!=-1)
{if(p->lchild==NULL)
{ if(p->lchild==NULL)
{
a[i++]=L->data[L->top];
L->top--;
h++;}
else {
L->top++;
L->data[L->top]=p->lchild;
p=p->lchild;
}}
if(L->top!=-1)
{if(p->rchild==NULL&&L->top!=-1)
{
p=L->data[L->top];
a[i++]=L->data[L->top];
L->top--;
h++;
}
else {p=p->rchild;
L->top++;
L->data[L->top]=p;
while(p->lchild!=NULL)
{L->top++;
L->data[L->top]=p->lchild;
p=p->lchild;
}
}
}

}

p=p->rchild;
L->top++;
L->data[L->top]=p;
}
T->data=h;
return T;
}

int main()
{int h;
stack L;
tree T;
T=(tree
)malloc(sizeof(tree));

T=create(T);

initstack(&L);
T=count(T,&L);
printf("输出二叉树结点的个数：%d",T->data);
return 0;
}

• 写回答
• 好问题 提建议
• 追加酬金
• 关注问题
• 邀请回答

1条回答默认 最新

• 你这个有点乱，这是我写的你可以参考一下，进行中序遍历后输出节点个数：

``````#include <stdio.h>
int cnt=0;
typedef struct node{ //树的结点
int data;
struct node* left;
struct node* right;
} Node;

typedef struct { //树根
Node* root;
} Tree;

void insert(Tree* tree, int value)//创建树
{
Node* node=(Node*)malloc(sizeof(Node));//创建一个节点
node->data = value;
node->left = NULL;
node->right = NULL;
if (tree->root == NULL)//判断树是不是空树
{
tree->root = node;
}
else {//不是空树
Node* temp = tree->root;//从树根开始
while (temp != NULL)
{

if (value < temp->data)//小于就进左儿子
{
if (temp->left == NULL)
{
temp->left = node;
return;
}
else {//继续判断
temp = temp->left;
}
}
else {//否则进右儿子

if (temp->right == NULL)
{
temp->right = node;
return;
}
else {//继续判断
temp = temp->right;
}
}
}
}
return;
}

void inorder(Node* node)//树的中序遍历
{
if (node != NULL)
{
inorder(node->left);
printf("%d ",node->data);
cnt++;
inorder(node->right);
}
}

int main()
{
Tree tree;
tree.root = NULL;//创建一个空树
int n;
scanf("%d",&n);
for (int i = 0; i < n; i++)//输入n个数并创建这个树
{
int temp;
scanf("%d",&temp);
insert(&tree, temp);
}
printf("中序遍历的结果是：");

inorder(tree.root);//中序遍历
printf("\n一共有%d个节点",cnt);
getchar(); getchar();
return 0;
}
``````

评论
解决 无用
打赏 举报