樹的相關筆試面試題

1. 樹的創建

已知一個先序遍歷數的結果用數組表示, 其中空節點用 null_node 表示, 要求創建出這棵樹. 同樣采用遞歸的思想, 先定義一個指針, 指向數組中的第一個元素, 然后給數組的第一個結點創建相應的結點, 然后指針后移, 遞歸創建根節點的左子樹, 遞歸創建根節點的右子樹, 最后返回這個新結點就可以了

TreeNode* TreeCreate(TreeNodeType array[], int size, TreeNodeType null_node)
{if(array == NULL){return NULL;//非法輸入}if(size == 0){return NULL;//非法輸入}if(array[0] == null_node){return NULL;//空樹}int index = 0;return _TreeCreate(array, size, &index, null_node);
}TreeNode* TreeClone(TreeNode* root)
{if(root == NULL){return NULL;//空樹}TreeNode* new_root;TreeInit(&new_root);new_root = CreateTreeNode(root -> data);if(new_root == NULL){return NULL;}//遞歸創建左子樹new_root -> lchild = TreeClone(new_root -> lchild);//遞歸創建右子樹new_root -> rchild = TreeClone(new_root -> rchild);return new_root;
}

2. 克隆一棵樹

克隆一棵樹也采用遞歸的思想, 先創建一個根節點, 然后遞歸創建根節點的左子樹, 再遞歸創建根節點的右子樹

TreeNode* TreeClone(TreeNode* root)
{if(root == NULL){return NULL;//空樹}TreeNode* new_root;TreeInit(&new_root);new_root = CreateTreeNode(root -> data);if(new_root == NULL){return NULL;}//遞歸創建左子樹new_root -> lchild = TreeClone(new_root -> lchild);//遞歸創建右子樹new_root -> rchild = TreeClone(new_root -> rchild);return new_root;
}

3. 求二叉樹的葉子結點數

求二叉樹的所有結點數即就是求二叉樹的左子樹上的結點數加上二叉樹的右子樹上的結點數, 然后左右字數的結點數相加即就是二叉樹的所有葉子結點數

int TreeLeafSize(TreeNode* root)
{if(root == NULL){return 0;}if(root -> lchild == NULL && root -> rchild == NULL){return 1;}return TreeLeafSize(root -> lchild) + TreeLeafSize(root -> rchild);
}

4. 求二叉樹的節點數

求二叉樹的節點數即就是先判斷二叉樹是不是只有一個結點, 如果不是, 就遞歸求解出二叉樹的左子樹的結點數, 再遞歸求解二叉樹的有子樹的結點數, 最后根節點的左右子樹之和加1就是二叉樹的結點總數

int TreeSize(TreeNode* root)
{if(root == NULL){return 0;}return TreeSize(root -> lchild) + TreeSize(root -> rchild) + 1;
}

5. 求二叉樹的高度

如果只有一個根節點, 則二叉樹的高度為 1, 否則二叉樹的高度就是根節點的左子樹和右子樹的高度的最大值加 1

int TreeHeight(TreeNode* root)
{if(root == NULL){return 0;}if(root -> lchild == NULL && root -> rchild == NULL){return 1;}int Lhight = TreeHeight(root -> lchild);int Rhight = TreeHeight(root -> rchild);return 1 + (Lhight > Rhight ? Lhight : Rhight);
}

6. 求某個節點的父節點

如果已知結點和根節點相等, 則直接返回根節點, 否則就遞歸的在根節點的左子樹中找, 如果沒有找的就在根節點的右子樹中遞歸的找

TreeNode* Parent(TreeNode* root, TreeNode* node)
{if(root == NULL || node == NULL){return NULL;}if(root -> lchild == node || root -> rchild == node){return root;}TreeNode* Lparent = Parent(root -> lchild, node);if(Lparent != NULL){return Lparent;}TreeNode* Rparent = Parent(root -> rchild, node);return Rparent;
}

7. 銷毀一個二叉樹

先遞歸銷毀二叉樹的左子樹, 再遞歸銷毀二叉樹的右子樹, 最后銷毀根節點

void TreeDestroy(TreeNode** root)
{if(root == NULL){return;}if(*root == NULL){return;//空樹}TreeDestroy(&(*root) -> lchild);TreeDestroy(&(*root) -> rchild);free(*root);*root = NULL;
}

8. 在二叉樹中找出給定指的結點

比較根節點的 data 和 to_find 是否相等, 相等就返回根節點, 不相等遞歸的和根節點的左子樹的 data 比較, 最后和根節點的右子樹的data比較

TreeNode* TreeFind(TreeNode* root, TreeNodeType to_find)
{if(root == NULL){return NULL;//空樹}if(root -> data == to_find){return root;}TreeNode* l_node = TreeFind(root -> lchild, to_find);if(l_node != NULL){return l_node;}TreeNode* r_node = TreeFind(root -> rchild, to_find);return r_node;
}

9. 非遞歸先序遍歷

先定義一個棧, 將根節點入棧, 取棧頂元素到 cur 中, 同時訪問當前結點, 將當前結點出棧, 如果當前結點的右子樹不為空, 就將當前結點的右子樹入棧, 如果當前結點的左子樹不為空, 入棧當前結點的左子樹, 循環取棧頂元素, 直到棧為空.

void TreePreOrderByLoop(TreeNode* root)
{if(root ==NULL){return;}SeqStack stack;SeqStackInit(&stack);SeqStackPush(&stack, root);SeqStackType cur;while(SeqStackGetFront(&stack, &cur)){printf("%c ", cur -> data);SeqStackPop(&stack);if(cur -> rchild != NULL){SeqStackPush(&stack, cur -> rchild);}if(cur -> lchild != NULL){SeqStackPush(&stack, cur -> lchild);}}
}

10. 非遞歸中序遍歷

先定義一個指針指向該節點, 如果當前結點不為空, 入棧當前結點, 同時讓當前結點一直往左走, 直到當前結點為空. 取棧頂結點, 訪問當前結點, 出棧. 讓當前結點指向它的右子樹

void TreeInOrderByLoop(TreeNode* root)
{if(root == NULL){return;}SeqStack stack;SeqStackInit(&stack);TreeNode* cur = root;while(1){while(cur != NULL){SeqStackPush(&stack, cur);cur = cur -> lchild;}int ret = SeqStackGetFront(&stack, &cur);if(ret == 0){return;}printf("%c ", cur -> data);SeqStackPop(&stack);cur = cur -> rchild;}
}

11. 非遞歸后序遍歷

定義一個指針prev初始化為 NULL來表示訪問的上一個結點, 同時定義一個指針 cur 指向該節點, 再定義一個指針 top 表示棧頂結點. 將 cur 入棧, 讓當前結點向左走, 直到當前結點為空, 此時取棧頂元素, 如果當前結點 cur -> rchild 和訪問的上一個結點相等, 則訪問當前結點, 同時將prev的值賦為訪問結點的值, 然后讓 cur 等于 cur -> rchild, 一直循環, 直到取棧頂元素失敗

void TreePostByLoop(TreeNode* root)
{if(root == NULL){return;//空樹}TreeNode* prev = NULL;TreeNode* cur = root;SeqStackType top;SeqStack stack;SeqStackInit(&stack);while(1){while(cur != NULL){SeqStackPush(&stack, cur);cur = cur -> lchild;}int ret = SeqStackGetFront(&stack, &top);if(ret == 0){return;}if(top -> rchild == NULL || top -> rchild == prev){printf("%c ", top -> data);prev = top;SeqStackPop(&stack);}else{cur = top -> rchild;}}
}

12. 樹的鏡像

(1)非遞歸版本

定義一個指針 cur 指向根節點, 定義一個隊列, 將 cur 入隊列, 取隊首元素, 將當前隊首元素左右字數進行交換, 出隊列, 如果cur -> lchild != NULL, 就將 cur -> lchild 入隊列, 如果 cur -> rchild != NULL, cur -> rchild 入隊列, 循環上述過程, 直到取棧頂元素失敗退出循環就說明當前樹已經逆置

void TreeMirrorByLoop(TreeNode* root)
{if(root == NULL){return;}SeqQue q;SeqQueInit(&q);SeqQueType top = root;SeqQuePush(&q, root);int ret = 0;while(SeqQueGetFront(&q, &top)){TreeNodeSwap(&(top -> lchild), &(top -> rchild));SeqQuePop(&q);if(top -> lchild != NULL){SeqQuePush(&q, top -> lchild);}if(top -> rchild != NULL){SeqQuePush(&q, top -> rchild);}}printf("\n");
}

(2)非遞歸版本求樹的鏡像

如果當前樹是空樹則直接返回, 如果當前樹只有一個根節點, 就直接返回, 否則就逆置當前結點的左子樹, 逆置當前結點的右子樹

void TreeMirror(TreeNode* root)
{if(root == NULL){return;//空樹}if(root -> rchild == NULL && root -> rchild == NULL){return;}TreeMirror(root -> rchild);TreeMirror(root -> lchild);
}

13. 判斷二叉樹是否為完全二叉樹

分為兩個階段, 第一階段判斷當前結點是否具有左右子樹, 如果具有左右字數, 就將當前結點左右子樹入隊列, 如果當前結點只有右子樹, 沒有左子樹, 一定不是右子樹, 如果當前結點只有左子樹沒有右子樹, 進入階段2, 如果當前結點左右子樹都沒有, 進入第二階段, 第二階段就是當前結點的后面結點都沒有子樹, 一直循環, 如果循環結束, 并且滿足上述條件, 則說明這個樹是完全二叉樹, 否則不是

int IsComPletTree(TreeNode* root)
{if(root == NULL){return;}TreeNode* cur = root;int start_step_two = 0;SeqQue q;SeqQueInit(&q);SeqQuePush(&q, cur);while(SeqQueGetFront(&q, &cur)){if(start_step_two == 0){if(cur -> rchild != NULL && cur -> lchild != NULL){SeqQuePush(&q, cur -> rchild);SeqQuePush(&q, cur -> lchild);}if(cur -> lchild == NULL && cur -> rchild != NULL){return 0;}if(cur -> lchild != NULL && cur -> rchild == NULL){start_step_two = 1;}if(cur -> lchild == NULL && cur -> rchild == NULL){start_step_two = 1;}}else{if(cur -> lchild == NULL && cur -> rchild == NULL){;}else{return 0;}}}return 1;
}