Tree

Question 1

Complete Binary Tree ：第 i 层最多有多少个节点？

Answer 1

Question 2

Perfect Binary Tree : 高度为h的树会有多少个节点？

Answer 2

Question 3

如何定义 二叉树的节点？

Answer 3

Question 4

Basic Terminologies in Binary Tree :

Answer 4

Question 5

Binary Tree : Properties

Answer 5

Question 6

Binary Tree types : Full Binary Tree

Answer 6

Question 7

Binary Tree types : Complete Binary Tree

Answer 7

Question 8

Binary Tree types : Perfect Binary Tree

Answer 8

Question 9

Binary Tree types : Degenerate Binary Tree

Answer 9

Question 10

Binary Tree types : Balanced Binary Tree

Answer 10

Question 11

Binary Search Tree : define Tree structure

Answer 11

Question 12

Binary Search Tree : newNode

Answer 12

Question 13

Binary Search Tree : Insert

Answer 13

Question 14

Binary Search Tree :find_minimum

Answer 14

Question 15

Binary Search Tree : find _maximum

Answer 15

Question 16

Binary Search Tree : height

Answer 16

Question 17

Tree : Time Complexity && Space Complexity

Answer 17

Question 18

考试题：根据前序、中序遍历画出二叉树

Answer 18

Question 19

考试题：根据后序、中序遍历画出二叉树

Answer 19

Question 20

前序、中序、后序遍历：

Answer 20

Question 21

level_lraversal : how it works

Hint:
1.isempt
2.create queue & temp
3.enqueue(root)
4.while
{
temp = dequeue (queue)
…..
}
5.free

Answer 21

Question 22

level_Traversal : create 3 ADT

Hint: node,queue node, queue

Answer 22

Question 23

level_lraversal - create queue containing node : Isempty

Answer 23

Question 24

level_lraversal - create queue containing node : create queue

Answer 24

Question 25

level_lraversal - create queue containing node : enqueue

Answer 25

1. temp
2. Null: front = temp
3. ! Null: rear & temp

Question 26

level_Traversal - create queue containing node : dequeue

Answer 26

1. isempty
   2.temp (delete)
   3.data(return)
   4.front (move)
   5.free
   6.return

Question 27

后序遍历（Post order）:层看法失效的情况，但是右侧法依然可以

Answer 27

原因：最后一层的上方有两个父母

Question 28

Tree : Preorder Traversal

Answer 28

Question 29

Tree : Inorder Traversal

Answer 29

Question 30

Tree : Postorder Traversal

Answer 30

Question 31

Binary Search Tree : Is_binarysearch_tree (With no biggest and smallest datas)

Hint
1.exit condition
2.false condition
3.recursion

Answer 31

Question 32

Binary Search Tree : Is_binarysearch_tree (With biggest and smallest datas)

Hint:
1.exit condition
2.false condition
3.recursion

Answer 32

Question 33

Binary Search Tree : Delete

Hints:
Part 1 : exit condition
Part 2 : Recursion part
1.search (also plays a role in deleting nodes with 2 children)
2.delete nodes with no child or one child
3.delete nodes with 2 children:
1️⃣find the smallest node in the right sub tree
2️⃣delete (substitute the deleted node)
3️⃣link the rest subtree

Answer 33

Question 34

Binary Search Tree : Find_inorder_successor

Hint:
Part 1: exit condition
Part 2: recursion
1️⃣right child exist
reach deepest
2️⃣ right child doesn’t exist
1.root > data
accessor ,root
2.root < data
root
3.root = data
return

Answer 34

Question 35

二叉树的性质总结 ：

Answer 35

补充 “ 树的性质 ： 节点数 = 分支数 + 1 ”

Question 36

例题 ：树求叶子节点个数

Answer 36

hint ： 完全二叉树度为0的节点数 = 度为2的节点数加1

Question 37

例题 ：求树的高度

Answer 37

Question 38

例题 ：满__叉树第n层的节点数

Answer 38

Hint :深度从1开始

Question 39

例题 ：哈夫曼树的性质

Question 40

例题 ：树的性质 – 节点数 = 分支数 + 1

Question 41

树 ——> 二叉树 的转换方法 ：

Answer 41

Question 42

二叉树 ——> 树 的转换方法 ：

Answer 42

Question 43

森林 ——> 二叉树 的转换方法 ：

Answer 43

Question 44

二叉树 ——> 森林 的转换方法 ：

Answer 44

Question 45

例题 ：画线索二叉树

hint ： 没有左孩子，连前驱；没有右孩子，连后继。两个都没有，就都要连

Answer 45

Question 46

AVL Tree : right & left rotation

Answer 46

Question 47

AVL Tree : LL & RR & LR & RL

Answer 47

Question 48

Categories of Tree : how to distinguish them?

Answer 48

Question 49

What does depth and height mean?

;
What’s the difference between them?

Answer 49

depth : The number of edges in the path from root node to the selected node.

height : The number of edges in the longest path connecting the selected node to any leaf node .