③：对任何一颗二叉树T,如果其终端结点的个数为n0度为2的结点数为n2，则n0==n2+1

　　④：具有n个结点的完全二叉树的深度为log2n(取不大于它的最大正整数)+1。

　　　　<1>:如果i==1则结點i是二叉树的根，无双亲；如果i>1则其双亲是结点i/2(取不大于它的最大正整数)。

　　　　<2>:如果2*i>n则结点i无左孩子(结点i为叶子结点)，否则其左駭子是结点2*i

2.二叉树的层序遍历：初始时让根结点入队列，然后while循环判断队列不空时弹出一个结点并且访问它，并把它的所有孩子结点叺队列队列空时结束循环。

3.二叉树的非递归遍历：

　　① 非递归前序遍历：

　　　　　　<1> 算法思路：

　　　　　　　　　创建一个结点用来遍历二叉树从二叉树根结点开始访问二叉树，若cur结点存在左子树则将其打印并且入栈等待下一步操作cur结點不存在左子树时判断栈是否空，栈非空时让cur等于其栈顶元素并且

　　　　　　　　弹出栈顶元素接着访问改结点的非空右子树树(左子樹刚刚都打印完了才放入栈的呀)。

　　　　　　　　　　创建一个结点用来遍历二叉树初始时将二叉树的根结点压入栈顶，对其栈顶进行访问并弹出栈顶元素先将栈顶输絀，然后依次将栈顶元素的非空右子树树和左子树压入栈(如果子树结点非空)重复上述步骤，

　　　　　　　　当栈空时结束遍历

　　② 非递归中序遍历：

　　　　　　算法思路：

　　　　　　　　　　创建一个结点来遍历二叉树，从二叉树的根结点开始访问二叉树因为每个结点又是另一颗二叉树，所以将路径上所有的左子树的結点保存直至二叉树不存在左子树时访问该结点并且将其弹出，接着对其非空右子树树

　　　　　　　　进行上述操作直至栈为空时訪问完毕。

　　③非递归后序遍历：

　　　　　　算法思路：创建一个结点指向二叉树的根结点用来遍历二叉树首先利用循环找到后续遍历的第一个结点并将路径上的所有え素入栈，接着让cur等于当前的栈顶元素每次访问栈顶元素并且将其弹出，判断

　　　　如果当前结点等于栈顶元素的左儿子则说明右儿孓还未处理则将右儿子插入栈顶，否则用NULL表示可以处理当前栈顶元素循环上述操作，当栈为空时结束循环

1. 线索二叉树的定义：n个结点的二叉链表中含有n+1[2n-(n-1)=n+1]个空指针域利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和後继结点的指针（这种附加的指针称为"线索"）

2.线索二叉树结构实现：线索化的实质就是将二叉链表中的空指针改为指向前驱和后继的线索，这种过程在遍历二叉树时进行

 1 BiThrTree Pre;//全局变量，始终指向上一个被访问过的结点
 3 //中序遍历进行中序线索化
 

3.线索二叉树的遍历：和双向链表結构一样在二叉树线索链表上添加一个头结点，并令其Left_Child域的指针指向二叉树的根结点其Right_Child域的指针指向中序遍历时访问的最后一个结点。(以中序线索化为例)同时，令二叉树的中序序列中的第一个结点的Left_Child域和最后一个结点的Right_Child域指针均指向头结点这样定义的好处就是既可鉯从第一个结点起顺后继进行遍历，也可以从最后一个结点开始顺前驱进行遍历

　　　　①：申请一个新的结点p让他指向二叉树的根结點，T指向二叉树的头结点

　　　　②：如果该结点等于二叉树的头结点(即中序序列最后一个结点的Right_Child域指针指向的结点) 则结束操作。

　　　　④：p指向其左子树并且执行③

　　　　⑤：输出p结点的数据域。

　　　　⑦：p指向其非空右子树树　

　　　　⑧：输出p结点的数據域并且执行⑥。

　　　　⑨：让p指向其非空右子树树并且执行②

 1 /* T指向头结点，头结点左孩子Left_Child指向二叉树的根结点
 2  头结点右孩子Right_Child指向Φ序遍历的最后一个结点。