44
技術社區[雲棲]
求二叉樹第m層上的第K個結點的值
/*
2．給定以下二叉樹:
struct node_t
{
node_t *left, *right;
int value;
};
要求編寫函數 node_t* foo(node_t *node, unsigned int m, unsigned int k);
輸出以 node 為根的二叉樹第 m 層的第 k 個節點值.
(level, k 均從 0 開始計數)
注意：
.此樹不是完全二叉樹；
.所謂的第K個節點，是本層中從左到右的第K個節點
第三題 係統設計題
*/
#include <iostream>
using namespace std;
const int MAX_LENGTH = 100;
struct node_t
{
node_t *left;
node_t *right;
int value;
};
node_t *queue[100];
int level = 0; // 記錄第幾層
int count = 0; // 記錄第level層的第幾個結點
int top = -1;
int rear = -1;
bool IsQueueEmpty()
{
return top == rear;
}
void EnQueue(node_t *node)
{
queue[++rear] = node;
}
node_t* DeQueue()
{
return queue[++top];
}
void CreateBiTree(node_t **root)
{
char ch;
cin >> ch;
if (ch == '*')
{
*root = NULL;
return;
}
else
{
*root = new node_t;
(*root)->value = ch;
CreateBiTree(&(*root)->left);
CreateBiTree(&(*root)->right);
}
}
node_t* foo(node_t *node, unsigned int m, unsigned int k)
{
node_t *p = node;
int last = -1;
if (p != NULL)
{
EnQueue(p); // 入隊
while (!IsQueueEmpty())
{
last = rear;
while (top < last)
{
node_t *q = DeQueue();
count++; // 當前層的第X個結點
if (level == m && count == k)
{
cout << q->value << endl;
return q;
}
if (q->left != NULL)
{
EnQueue(q->left);
}
if (q->right != NULL)
{
EnQueue(q->right);
}
}
level++;
count = 0;
}
}
cout << "找不到符合的結點" << endl;
return NULL;
}
int main()
{
node_t *root;
CreateBiTree(&root);
cout << "樹建立完畢" << endl;
foo(root, 1, 1);
return 0;
}
最後更新：2017-04-03 15:21:51