2021/3/16 求二叉樹中值為x的結點的層号

【練習時間】2021/3/16

【題目名稱】 求二叉樹中值為x的結點的層号

【問題描述】

以二叉連結清單為存儲結構，編寫算法求二叉樹中值為x的結點的層号。

【輸入形式】兩行，第一行是擴充二叉樹的前序周遊序列，第二行是待查詢結點x

【輸出形式】值為x的結點所在層号。根結點所在層記為第1層。

【樣例輸入】

AB#D##C##

D

【樣例輸出】

3

【思路分析】

我們首先會考慮到如果一個節點是某一個節點的左子樹或右子樹上的節點，那麼這個節點的層數應該是上一個節點層數+1；但是當我們編譯實作的時候發現，根節點的左右子樹的層數連接配接在一起，正常情況下應該是，左子樹周遊完成後，轉移到根節點的右子樹的時候層數計數器歸零。是以我們重新修改代碼。

首先構造左右子樹，并記錄根節點的值，作為全局變量。

struct BiNode
{
	char data;
	BiNode *lchild;
	BiNode *rchild;
};
BiNode *Creat()
{
	BiNode *bt;
	char ch;
	cin>>ch;
	if(ch=='#')return NULL;
	else{
		bt=new BiNode;
		bt->data=ch;
		if(root=='0')root=ch;
		bt->lchild=Creat();
		bt->rchild=Creat();
	}
	return bt;
}
           

接下來我們采用中序周遊的方法，将layer設定為全局變量，每向左子樹周遊一次，layer++,同樣的，向右子樹周遊一次，layer++，但是，如果周遊的節點回到了根節點，那麼layer重置為1；直到最終找到目标。

void MidOrder(BiNode *bt,char a)
{
	if(bt==NULL)
	{
		layer--;
		return;
	}
	else{
		if(bt->data==a)
		{
			cout<<layer;
			return;
		}
		layer++;
		MidOrder(bt->lchild,a);
		if(bt->data==root)layer=1;
		layer++;
		MidOrder(bt->rchild,a);
		
	}
}
           

【源代碼】

#include <iostream>
using namespace std;
int layer=1;
char root='0';
struct BiNode
{
	char data;
	BiNode *lchild;
	BiNode *rchild;
};
BiNode *Creat()
{
	BiNode *bt;
	char ch;
	cin>>ch;
	if(ch=='#')return NULL;
	else{
		bt=new BiNode;
		bt->data=ch;
		if(root=='0')root=ch;
		bt->lchild=Creat();
		bt->rchild=Creat();
	}
	return bt;
}

void MidOrder(BiNode *bt,char a)
{
	if(bt==NULL)
	{
		layer--;
		return;
	}
	else{
		if(bt->data==a)
		{
			cout<<layer;
			return;
		}
		layer++;
		MidOrder(bt->lchild,a);
		if(bt->data==root)layer=1;
		layer++;
		MidOrder(bt->rchild,a);
		
	}
}
int main()
{
	BiNode *bt=Creat();
	char a;
	cin>>a;
	MidOrder(bt,a);
	return 0;
}