Struct_chapter3_Tree

3.1 tree and the expression of tree

concept of tree
an excellent struct to expresses hierarchical relationship(层次关系)
more efficienct

Searching
0x01 static searching

notice : 哨兵(tag)
two probable status to exit :
1.find K in list(return index)
2.no K except the station of tag(return 0)
3.时间复杂度o(n) [n/2]
0x02 binary search(二分查找)
不可采用chain list [one-way]

status 1 find correct answer

status 2 no correct answer

realization and enlightenment

thought bubble : optimize

黄金分割查找？
在二分查找中，我们是取mid等于left和right的中间值，即用等分的方法进行查找。
那为什么一定要等分呐？能不能进行“黄金分割”？也就是mid=left+0.618(right-left),当然mid要取整数。如果这样查找，时间复杂性是多少？也许你还可以编程做个试验，比较一下二分法和“黄金分割”法的执行效率。

Tree

definition
Struct_chapter3_Tree

question : 有一个m棵树的集合（也叫森林）共有k条边，问这m颗树共有多少个结点？
answer : k+m (each line [k] connect a node and there are also m root-nodes)

Term and basic conception of tree
Struct_chapter3_Tree
express the tree

node结构统一
空间浪费小(n个node–>2n个指针域–>n-1条边(非空域)–>仅n+1个空域 )

森林及表示
树的集合称为森林。是否也可以使用“儿子-兄弟”表示法存储森林？如何实现？

一棵度为 m的树有n个节点。若每个节点直接用m个链指向相应的儿子，则表示这个树所需要的总空间是n*(m+1)n*m(链)+n(data) (假定每个链以及表示节点的数据域都是一个单位空间).。当采用儿子/兄弟（First Child/Next Sibling）表示法时，所需的总空间是 : 3n(2n+n)

3.2 binary tree and the storage structure

binary tree

Struct_chapter3_Tree

properties of binary tree

complete from textbook
property 2:等比数列求和公式(q=2) --> full binary tree

m叉树中各类结点数之间的关系
在二叉树中，我们知道叶结点总数n0与有两个儿子的结点n2总数之间的关系是：n0=n2+1.
那么类似关系是否可以推广到m叉树中？也就是，如果在m叉树中，叶结点总数是n0，有一个儿子的结点总数是n1，有2个儿子的结点总数是n2，有3个儿子的结点总数是n3，…。那么，ni之间存在什么关系？

answer :
通过边数的两种计算方式，将结点数联系到一起。
n0 + n1 + n2 + n3 - 1 = 0 * n0 + 1 * n1 + 2 * n2 + 3 * n3
化简：
n0 = n2 + 2 * n3 + 1
推广到m叉树：
n0 + n1 + n2 + … + nm - 1 = 0 * n0 + 1 * n1 + 2 * n2 + … + m * nm
化简得到：
n0 = 1 * n2 + 2 * n3 +…+ (m - 1) * nm

realization

Struct_chapter3_Tree

traverse the tree

1.base on stack

traverse with recursion
conclusion
each node has three chances to be viewed in the whole traverse-route,actually each method choose one of them.
traverse the tree without recursion

讨论3.4 如何用堆栈实现后序遍历的非递归程序
详见讨论区!necessary

2.base on queue
Struct_chapter3_Tree

讨论3.5 将层序遍历中的队列改为堆栈
如果将层序遍历中的队列改为堆栈，是否也是一种树的遍历？可以应用这种方法改造出一种前序、中序、后序的非递归遍历吗？

the application of traverse tree
1.base on preorder frame
Struct_chapter3_Tree
2.base on postoorder frame–>comparison requires the result of traverse to sub-trees–>postorder frame
3.

4.