Предисловие
На прошлой неделе я отправил свое резюме на должность инженера по разработке. На этой неделе интервьюер Tencent дал мне видеоинтервью. Во время интервью он спросил о бинарном дереве. Вопросы, связанные с алгоритмом бинарного дерева, появляются в интервью очень и очень много раз, поэтому я также подготовился к интервью. Сегодня я подробно расскажу об этом с вопросами интервьюбинарное дерево, в сочетании с примерами для анализа метода создания и процесса обхода структуры хранения двоичного дерева.
вопросы интервью
Интервьюер: Посмотрите свое резюме и напишите о знакомстве со структурами данных, расскажите о способе обхода бинарного дерева?
Я: (для меня это не сложно)
обход предварительного заказа
Сначала посетите корневой узел, затем по очереди посетите левый и правый дочерние узлы.
рекурсивный алгоритм
void PreOrder1(BTREE bt) //递归先根遍历
{
if (bt)
{
if (bt->data != '#')
{
printf(" %c", bt->data);//结点不空 ，打印结点值
}
PreOrder1(bt->lchild);//依次访问左右节点
PreOrder1(bt->rchild);
}
}
нерекурсивный алгоритм
void PreOrder2(BTREE p)//非递归先根遍历 ,先访问根节点，后依次访问左孩子和右孩子
{
int top = -1;
node *Q[N];
while (p != NULL || top != -1)
{
while (p != NULL)
{
if (p->data != '#')
{
printf(" %c", p->data);
}
Q[++top] = p;
p = p->lchild;
}
if (top != -1)
{
p = Q[top--];
p = p->rchild;
}
}
}
Неупорядоченный обход
Сначала посетите левый дочерний элемент, затем посетите корневой узел и правый дочерний узел по очереди.
рекурсивный алгоритм
void InOrder1(BTREE bt)//递归中序遍历
{
if (bt)
{
InOrder1(bt->lchild);//先访问左节点
if (bt->data != '#')
{
printf(" %c", bt->data);//结点不空 ，打印结点值
}
InOrder1(bt->rchild);//先访问右节点
}
}
нерекурсивный алгоритм
void InOrder2(BTREE p)//非递归中序遍历，先访问左孩子，然后访问根节点，后访问右孩子
{
int top = -1;
node *Q[N];
while (p != NULL || top != -1)
{
while (p != NULL)
{
Q[++top] = p;
p = p->lchild;
}
if (top != -1)
{
p = Q[top--];
if (p->data != '#')
{
printf(" %c",p->data);
}
p = p->rchild;
}
}
}
пост-порядковый обход
Сначала посетите левый дочерний элемент, затем по очереди посетите правый дочерний элемент и корневой узел.
рекурсивный алгоритм
void PostOrder1(BTREE bt)//后序遍历
{
if (bt)
{
PostOrder1(bt->lchild);//先访问左，右孩子节点
PostOrder1(bt->rchild);
if (bt->data != '#')
{
printf(" %c", bt->data);//后访问根节点
}
}
}
нерекурсивный алгоритм
void PostOrder2(BTREE p)//非递归后序遍历 ，先访问左孩子，然后访问右孩子，后访问根节点
{
int top = -1;
node *Q[N];
int flag[N] = { 0 };
while (p != NULL || top != -1)
{
while (p != NULL)
{
top++;
Q[top] = p;
flag[top] = 1;
p = p->lchild;
}
while (top != -1 && flag[top] == 2)
{
if (Q[top]->data != '#')
{
printf(" %c", Q[top]->data);
top--;
}
}
if (top != -1)
{
flag[top] = 2;
p = Q[top]->rchild;
}
}
}
Интервьюер: Вы очень хорошо ответили, есть ли другой способ пройти?
Я:……
После нескольких секунд тишины я (мне это несложно): там тоже уровень обхода порядка
обход по уровням
Начните с корня и спускайтесь вниз, проходя слева направо для каждого слоя.
//层序遍历
void Sequense(BTREE bt)//建立栈，依次将根节点，左孩子，右孩子压栈 ，并打印栈顶元素
{
node *Q[N];
node *p;
int front = 0, top = 0;
if (bt != NULL)
{
Q[++top] = bt;//将根节点压栈
while (front < top) //遍历栈
{
p = Q[++front];
if (p->data != '#')
{
printf(" %c", p->data);//打印栈顶元素
}
if (p->lchild)
{
Q[++top] = p->lchild;//将左孩子压栈
}
if (p->rchild)
{
Q[++top] = p->rchild;//将右孩子压栈
}
}
}
}
Краткое описание алгоритма обхода
Интервьюер: Как определить, является ли это полным бинарным деревом?
Я: (для меня это не сложно)
Полное бинарное дерево суждения
-
Обход бинарного дерева слой за слоем, обход всех узлов слева направо от каждого слоя
-
Если у текущего узла есть правый дочерний элемент, но нет левого дочернего элемента, то это не полное двоичное дерево.
-
Если у текущего узла есть левый дочерний элемент, но нет правого дочернего элемента, то все узлы после него должны быть листовыми узлами, в противном случае это не полное двоичное дерево.
-
Если у текущего узла есть левый и правый дочерние элементы, продолжайте обход
int Compnode(BTREE G)//判断是否是完全二叉树
{
node *D[N], *p; //建立一个队列D[N]
int front = 0, last = 0; //front是队头指针,last是队尾指针
int tree_signal = 1;//tree_signal是判断是否为完全二叉树的标志
int odd_signal = 1;//odd_signal是判断是否存在无左孩子的节点的标志
if (G != NULL)
{
last++;
D[last] = G; //将根节点压入队尾
while (front != last)
{
front++;
p = D[front];
if (p->lchild == NULL ||(p->lchild)->data == '#') //*p节点没有左孩子
{
odd_signal = 0;
if (p->rchild != NULL && (p->rchild)->data != '#') //没有左孩子但有右孩子，不是完全二叉树
tree_signal = 0;
}
else //*p节点有左子树
{
if (odd_signal == 1) //目前不存在无左孩子的节点
{
last++; //左孩子进队
D[last] = p->lchild;
if (p->rchild == NULL || (p->rchild)->data == '#') //*p有左孩子但没有右孩子
{
odd_signal = 0;
}
else
{
last++; //右孩子进队
D[last] = p->rchild;
}
}
else //目前存在有左孩子的节点，不是完全二叉树
{
tree_signal = 0;
}
}
}
}
else
{
tree_signal = 0;//假设空树不是完全二叉树
}
return tree_signal;
}
Суммировать
Давайте играть, давайте играть, давайте играть, не смейтесь над интервью.
Хотя обход бинарного дерева прост, существуют различные методы обхода, а такжерекурсивный алгоритма такженерекурсивный алгоритмточки. Однажды спросил,Все должны отвечать развернуто, не теряться, отвечать по существу. Вопросы, связанные с алгоритмом бинарного дерева, очень часто появляются на собеседованиях.Перед собеседованием каждый должен заложить прочную основу для структур данных, таких как бинарные деревья.