数据结构（C语言版）---二叉树
1、二叉树：任意一个结点的子结点个数最多两个，且子结点的位置不可更改，二叉树的子树有左右之分。
1）分类：
（1）一般二叉树
（2）满二叉树：在不增加树的层数的前提下，无法再多添加一个结点的二叉树就是满二叉树。
（3）完全二叉树：如果只是删除了满二叉树最底层最右边的连续的若干个结点，这样形成的二叉树就是完全二叉树。
（4）二叉排序树：左子树上所有结点的关键字均小于根结点的关键字，右子树上的所有结点的关键字均大于根结点的关键字。
（5）平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1。
2）性质：
（1）在二叉树的第i层上至多有2i-1个结点（i>=1)。
（2）深度为k的二叉树至多有2k-1个结点(k>=1)。
（3）对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
（4）具有n个结点的完全二叉树的深度为log2n+1。
（5）如果对一棵有n个结点的完全二叉树（深度为log2n+1）的结点按层序编号（从第1层到第log2n+1层，每层从左到右），则对任一结点i(1<=i<=n)，有
如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲Parent(i)是结点i/2；
如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子LeftChild(i)是结点2i；
如果2i+1>n，则结点i无右孩子；否则其右孩子LRightChild(i)是结点2i+1。
3）二叉树和度为2的有序树的区别：
（1）度为2 的树至少有3个结点，而二叉树为空。
（2）度为2的有序树的孩子结点的左右次序是相对于另一个孩子结点而言的。
4）存储
（1）顺序存储【完全二叉树】：用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。
优点：查找某个节点的父节点和子节点速度很快（也包括判断有没有子节点）。
缺点：耗用内存空间。
（2）链式存储：用一个链表来存储二叉树，设置不同的指针域，二叉链表至少包含3个指针域：数据域、左指针域、右指针域。
5）遍历
（1）先序遍历
先访问根结点、再先序访问左子树、再先序访问右子树。
（2）中序遍历
先中序遍历左子树、再访问根结点、再中序遍历右子树。
（3）后序遍历
先后序遍历右子树、再后序遍历左子树、再访问根结点。
6）已知两种遍历序列求原始二叉树
通过先序和中序、中序和后序都可以还原出原始的二叉树，但是通过先序和后序无法还原出原始的二叉树。
2、线索链表
| lchild | ltag | data | rtag | rchild |
ltag=0,lchild域指示结点的左孩子；ltag=1,lchild域指示结点的前驱。
rtag=0,rchild域指示结点的右孩子；rtag=1,rchild域指示结点的后继。
1）线索：指向结点前驱和后继的指针。
2）线索二叉树：加上线索的二叉树。
3）线索化：对二叉树以某种次序遍历使其变成线索二叉树的过程。
3、二叉排序树（BST）（二叉查找树）
1）性质：左子树为空，则左子树上所有结点关键字值均小于根结点的关键字值。
右子树为空，则右子树上所有结点关键字值均大于根结点的关键字值。
左右子树本身也是一棵二叉排序树。
2）左子树结点值<根结点值<右子树结点值，进行中序遍历时，可以得到递增的有序序列。
3）二叉排序树的删除
（1）删除结点为叶结点，则直接删除。
（2）若结点只有一棵左子树或右子树，则让该结点的子树成为该结点父结点的子树。
（3）若结点有左右两棵子树，则令该结点的直接后继（直接前驱）替代该结点，删除直接后继（直接前驱）。
4）只有左（右）孩子的单支树的二叉排序树，平均查找长度为O(n)。
5）左、右子树的高度差的绝对值不超过1的二叉排序树，即平衡二叉树，平均查找长度为O(log2n)。
4、平衡二叉树(AVL)
1）平衡因子：左子树与右子树的高度差。平衡二叉树结点的平衡因子的值只可能是-1、0、1.
2）性质：左右子树都是平衡二叉树，且左右子树的高度差的绝对值不超过1
5、二叉树的基本操作
1）InitBiTree(&T)：构造空树
2）DestroyBiTree(&T)：销毁树
3）CreateBiTree(&T,definition)：按definition构造树
4）ClearBiTree(&T)：清空树
5）BiTreeEmpty(T)：判断树是否为空
6）BiTreeDepth(T)：返回树的深度
7）Root(T)：返回树的根
8）Value(T,cur_e)：返回结点cur_e的值
9）Assign(T,cur_e,value)：将结点cur_e赋值为value
10）Parent(T,cur_e)：若cur_e为非根节点，则返回双亲，否则函数值为空
11）LeftChild(T,cur_e)：若cur_e为非叶子结点，则返回左孩子，否则函数值为空
12）RightChild(T,cur_e)：若cur_e为非叶子结点，则返回右孩子，否则函数值为空
13）LeftSibling(T,cur_e)：若cur_e有左兄弟，则返回，否则函数值为空
14）RightSibling(T,cur_e)：若cur_e有右兄弟，则返回，否则函数值为空
15）InsertChild(&T,&p,i,e)：插入c为T中p所指结点的第i棵子树
16）DeleteChild(&T,&p,i)：删除T中p所指结点的第i棵子树
6、二叉树的顺序存储结构类型描述
#define Maxsize 100
typedef int SqBiTree[Maxsize];
7、在二叉树中查找结点i和结点j的最近公共祖先结点
int commancestor(SqBiTree T, int i, int j)
{
if (T[i] != ‘#’&&T[j] != ‘#’)
{
while (i!=j)
{
if (i > j)
{
i = i / 2;
}
else
{
j = j / 2;
}
}
return T[i];
}
}
8、二叉树的链式存储结构类型描述
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
9、此部分程序中涉及到栈和队列的部分在前面几篇中提到，在这里就不详细给出咯。
1）先序遍历
void preorder(BiTree T)
{
if (T != NULL)
{
visit(T);
preorder(T->lchild);
preorder(T->rchild);
}
}
2）中序遍历
void inorder(BiTree T)
{
if (T != NULL)
{
inorder(T->lchild);
visit(T);
inorder(T->rchild);
}
}
3）中序遍历利用栈
void inorder1(BiTree T)
{
Sqstack S;
initstack(S);
BiTree p = T;
while (p||!stackempty(S))
{
if (p)
{
push(S, p->data);
p = p->lchild;
}
else
{
pop(S, p->data);
visit(p);
p = p->rchild;
}
}
}
4）后序遍历
void postorder(BiTree T)
{
if (T != NULL)
{
postorder(T->lchild);
postorder(T->rchild);
visit(T);
}
}
5）后序遍历非递归
void postorder1(BiTree T)
{
Sqstack S;
BiTNode *r,*p;
//BiTree p;
initstack(S);
p = T;
r = NULL;
while (p||!stackempty(S))
{
if (p)
{
push(S, p->data);
p = p->lchild;
}
else
{
pop(S, p->data);
if (p->rchild&&p->rchild != r)
{
p = p->rchild;
push(S, p->data);
p = p->lchild;
}
else
{
pop(S, p->data);
visit(p);
r = p;
p = NULL;
}
}
}
}
6）层序遍历
void levelorder(BiTree T)
{
Sqstack S;
SqQueue Q;
initqueue(Q);
initstack(S);
if(T!=NULL)
{
enqueue(Q, T->data);
while (!queueempty(Q))
{
dequeue(Q,T->data);
push(S, T->data);
if (T->lchild != NULL)
{
enqueue(Q, T->lchild->data);
}
if (T->rchild != NULL)
{
enqueue(Q, T->rchild->data);
}
}
while (!stackempty(S))
{
pop(S, T->data);
visit1(T->data);
}
}
}
10、二叉排序树非递归算法
BiTNode *bstsearch(BiTree T, int key, BiTNode *&p)
{
p = NULL;
while (T!=NULL&&key!=T->data)
{
p = T;
if (key < T->data)
{
T = T->lchild;
}
else
{
T = T->rchild;
}
}
return T;
}
11、二叉排序树的插入
int bstinsert(BiTree &T, int k)
{
if (T == NULL)
{
T = (BiTree)malloc(sizeof(BiTNode));
T->data = k;
T->lchild = T->rchild = NULL;
return 1;
}
else if (k == T->data)
{
return 0;
}
else if (k < T->data)
{
return bstinsert(T->lchild, k);
}
else
{
return bstinsert(T->rchild, k);
}
}
12、二叉排序树的构造
void bstcreate(BiTree &T, int str[], int n)
{
T = NULL;
int i = 0;
while (i<n)
{
bstinsert(T, str[i]);
i++;
}
}
13、线索二叉树的存储结构
typedef struct ThreadNode {
int data;
struct ThreadNode *lchild, *rchild;
int ltag, rtag;
}ThreadNode,*ThreadTree;
void visit(ThreadTree T)
{
printf(“遍历树”);
return;
}
1）求中序线索二叉树中中序序列下的第一个结点
ThreadNode *firstnode(ThreadNode *p)
{
while (p->ltag==0)
{
p = p->lchild;
}
return p;
}
2）求中序线索二叉树中结点p在中序序列下的后继结点
ThreadNode *nextnode(ThreadNode *p)
{
if (p->rtag == 0)
{
return firstnode(p->rchild);
}
else
{
return p->rchild;
}
}
3）不含头结点的中序线索二叉树的中序遍历
void inorder(ThreadNode *p)
{
for (ThreadNode *t = firstnode(p); t != NULL; t = nextnode(p))
{
visit(p);
}
}
4）中序遍历对二叉树线索化的递归算法
void inthread(ThreadTree &t, ThreadTree &pre)
{
if (t != NULL)
{
inthread(t->lchild, pre);
if (t->lchild == NULL)
{
t->lchild = pre;
t->ltag = 1;
}
if (pre != NULL && pre->rchild == NULL)
{
pre->rchild = t;
pre->rtag = 1;
}
pre = t;
inthread(t->rchild, pre);
}
}
5）中序遍历建立中序线索二叉树
void createinthread(ThreadTree T)
{
ThreadTree pre = NULL;
if (T != NULL)
{
inthread(T, pre);
pre->rchild = NULL;
pre->rtag = 1;
}
}