二叉树搜索叶子节点

smallcracker 2021-05-23 00:00:00
Categories： Tags：

结构

1
2
3
4
5
6
7
8
9
int n,tem;
int top;
struct Node{
	int num;
	int depth;
	Node *lchild=NULL;
	Node *rchild=NULL;
} *node[200010],*stack[200010];
Node p[200010];

初始化

1
2
3
4
5
6
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
    node[i]=&p[i];
}
build_tree();

建树

鉴于嵌入式设备的特点，主要使用循环的方法来进行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void build_tree()
{
	Node *cur_node=node[1];
	scanf("%d",&tem);
	node[1]->num=tem;
	node[1]->depth=1;
	if(n==1)
	{
		return ;
	}
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&tem);
		cur_node=node[1];
		do{
			if((tem<cur_node->num)&&(cur_node->lchild==NULL))
			{   
				node[i]->num=tem;
				node[i]->depth=cur_node->depth+1;
				cur_node->lchild=node[i];
				break;
			}
			if((tem>=cur_node->num)&&(cur_node->rchild==NULL))
			{
				node[i]->num=tem;
				node[i]->depth=cur_node->depth+1;
				cur_node->rchild=node[i];
				break;
			}
			if(tem<cur_node->num) cur_node=cur_node->lchild; 
			else cur_node=cur_node->rchild;
		}while(1);
	}
}

搜索叶子节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void dfs()
{
	stack[1]=node[1];
	top=1;
	Node *temp;
	while(top)
	{
		temp=stack[top--];
		bool isLeaf=true;
		if(temp->rchild!=NULL)
		{
			stack[++top]=temp->rchild;
			isLeaf=false;
		}
		if(temp->lchild!=NULL)
		{
			stack[++top]=temp->lchild;
			isLeaf=false;
		}
		if(isLeaf)
		{
			printf("%d %d\n",temp->num,temp->depth);
		}
	}
	return ;
}
UCOSII
版本控制学习