完全二叉树的顺序存储：
A2B1C34DE56FG7HIJKL89101112
ABCDEFGHIJKL
0 1 2 3 4 5 6 7 8 9 10 11 12
一般二叉树的顺序存储：
把一般的二叉树先补成完全二叉树，然后按照完全二叉树的顺序存储方式进行存储，而新补上去的结点只占位置，不存放结点数据。
ABCD(a) 右偏斜二叉树AABCD(b) 补全后的完全二叉树 DBC (c) 右偏斜二叉树的顺序存储示意图
二叉树的链式存储结构： 二叉链表：
二叉树的遍历：
顺着某一条搜索路径巡访二叉树中的节点，使得每个节点均被访问一次，而且仅被访问一次。
常见的遍历方式有：
递归遍历，层次遍历，非递归遍历 树的遍历常用方法：
先序遍历：先访问树的根节点，然后先序访问左子树，最后先序访问右子树 中序遍历：先中序遍历左子树，然后访问根节点，最后中序访问右子树 后序遍历：先后序遍历左子树，然后后序遍历右子树，最后访问根节点 按层次遍历：先访问第一次上的节点，然后依次遍历第二层。。。。。
先序遍历的递归算法： void PreOrder( BiTree bt) {
if (bt!=NULL){ /* 如果bt为空，结束*/
visit (bt->data); /*访问根结点*/
PreOrder( bt->lchild); /*先序遍历左子树（递归调用）*/ PreOrder (bt->rchild); /*先序遍历右子树（递归调用）*/ } }
中序遍历的递归算法： void InOrder( BiTree bt) {
if (bt!=NULL){ /* 如果bt为空，结束*/
InOrder( bt->lchild); /*中序遍历左子树（递归调用）*/ visit (bt->data); /*访问根结点*/
InOrder (bt->rchild); /* 中序遍历右子树（递归调用）*/
}
}
后序遍历的递归算法： void PostOrder( BiTree bt) {
if (bt!=NULL){ /* 如果bt为空，结束*/
PostOrder( bt->lchild); /*后序遍历左子树（递归调用）*/ PostOrder (bt->rchild); /* 后序遍历右子树（递归调用）*/ visit (bt->data); /*访问根结点*/ } }
中序遍历非递归算法： void NRInOrder(BiTree bt){
BiTree S[MAXNODE], p=bt; /*定义栈S*/ int top=-1; if (bt==NULL)
return; /*空二叉树，遍历结束*/ while(!(p==NULL && top==0)){ while(p!=NULL){
if( top S[top++]=p; /*当前指针p进栈*/ Else { printf(“栈溢出\\n”); return; } p=p->lchild; /*指标指向p的左孩子结点*/ } if(top==-1) return; /*栈空时结束*/ else { p=S[--top]; /*弹出栈顶元素*/ visit(p->data); /*访问结点的数据域*/ p=p->rchild; /*指向p的右孩子结点*/ } } } 线索二叉树： 节点结构： 规定：若节点有左孩子，则其lchild指示其左孩子，否则，令lchild域指示其前驱；若节点有右孩子，则其rchild指示其右孩子，否则，令rchild域指示其后继。 结构： lchildLTagdataRTagrchild typedef struct BiThrNode{ Datatype data; struct BiThrNode *lchild, *rchild; byte LTag, RTag; }BiThrNode, *BiThrTree; ?0 lchild 域指示结点的左孩子LTag=??1 lchild域指示结点的前驱?0 rchild域指示结点的右孩子RTag=??1 rchild域指示结点的后继 以下列结点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向前驱和后继的指针，叫做线索（Thread）。加上线索的二叉树叫做线索二叉树（Thread Binary Tree）。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。 二叉排序树： 二叉排序树的任意节点大于左孩子，小于右孩子 78543723456585828794 二叉平衡树： 二叉平衡树的每个节点的左右子树深度之差不超过1 哈夫曼树： 带权路径长度最短的树 树和森林： 树转化为二叉树： A对应BECFGD存储A∧∧BA∧∧BEC∧F∧D∧∧G∧解释C∧D∧∧E∧F∧G∧E∧F∧G∧解释存储BCEFGA∧∧BC∧D∧DA 二叉树转化为树： 加线：将结点和其左孩子结点的右孩子以及右孩子的右孩子加线相连 抹线：去掉结点和右孩子的连线 旋转：将加线、去线后的结果，进行旋转处理，就得到转换后的树