二叉查找树和二叉搜索树_完全二叉树和满二叉树图解

理解二叉树和线索二叉树 　　1.什么是二叉树？ 　　      二叉树是每个节点最多有两个子树的结构。通常子树被称作“左子树”和“右子树”，左子树和右子树同时也是二叉树，二叉树的子树有左右之分，并且次序不能任意颠倒，二叉树是递归定义的，所以一般二叉树的相关题目也都可以使用递归的思想来解决，当然也有一些可以使用非递归的思想解决，我下面列出的一些算法有些采用了递归，有些是非递归的。 　　2.什么是二叉排序树？ 　　二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件： 　　1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值； 　　2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值 　　3）左、右子树也分别为二叉排序树 　　4）没有键值相等的节点（？可能是因为不好处理键值相等的节点到底是左节点还是右节点吧） 　　概念就介绍这么多，都是来自网上，下面主要看算法和具体实现代码。 　　创建二叉排序树 　　1.定义一个节点类，使节点与二叉树操作分离 　　class Node { int value;//节点 Node leftChild;//左子树 Node rightChild;//右子树 Node(int value) { this.value = value; } public void display() { System.out.print(this.value + ” “); } @Override public String toString() { // TODO Auto-generated method stub return String.valueOf(value); } } 　　2.需要实现的二叉树操作 　　class BinaryTree { private Node root = null; BinaryTree(int value) { root = new Node(value); root.leftChild = null; root.rightChild = null; } public Node findKey(int value) {}; //查找 public String insert(int value) {}; //插入 public void inOrderTraverse() {}; //中序遍历递归操作 public void inOrderByStack() {}; //中序遍历非递归操作 public void preOrderTraverse() {}; //前序遍历 public void preOrderByStack() {}; //前序遍历非递归操作 public void postOrderTraverse() {}; //后序遍历 public void postOrderByStack() {}; //后序遍历非递归操作 public int getMinValue() {}; //得到最小(大)值 public boolean delete(int value) {}; //删除 } 　　  　　一、线索二叉树的原理 　　    通过考察各种二叉链表，不管儿叉树的形态如何，空链域的个数总是多过非空链域的个数。准确的说，n各结点的二叉链表共有2n个链域，非空链域为n-1个，但其中的空链域却有n+1个。如下图所示。 　　
　　   因此，提出了一种方法，利用原来的空链域存放指针，指向树中其他结点。这种指针称为线索。 　　    记ptr指向二叉链表中的一个结点，以下是建立线索的规则： 　　    （1）如果ptr->lchild为空，则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱； 　　    （2）如果ptr->rchild为空，则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继； 　　    显然，在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继，需要一个区分标志的。因此，我们在每个结点再增设两个标志域ltag和rtag，注意ltag和rtag只是区分0或1数字的布尔型变量，其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。 　　
　　    其中： 　　    （1）ltag为0时指向该结点的左孩子，为1时指向该结点的前驱； 　　    （2）rtag为0时指向该结点的右孩子，为1时指向该结点的后继； 　　    （3）因此对于上图的二叉链表图可以修改为下图的养子。 　　
　　  　　  　　二、线索二叉树结构实现 　　    二叉线索树存储结构定义如下： 　　/* 二叉树的二叉线索存储结构定义*/ typedef enum{Link, Thread}PointerTag; //Link = 0表示指向左右孩子指针；Thread = 1表示指向前驱或后继的线索 typedef struct BitNode { char data; //结点数据 struct BitNode *lchild, *rchild; //左右孩子指针 PointerTag Ltag; //左右标志 PointerTag rtal; }BitNode, *BiTree; 　　线索化的实质就是将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继信息只有在遍历该二叉树时才能得到，所以，线索化的过程就是在遍历的过程中修改空指针的过程，一般中序遍历线索化最常用。 　　    中序遍历线索化的递归函数代码如下： 　　BiTree pre; //全局变量，始终指向刚刚访问过的结点 //中序遍历进行中序线索化 void InThreading(BiTree p) { if(p) { InThreading(p->lchild); //递归左子树线索化 //=== if(!p->lchild) //没有左孩子 { p->ltag = Thread; //前驱线索 p->lchild = pre; //左孩子指针指向前驱 } if(!pre->rchild) //没有右孩子 { pre->rtag = Thread; //后继线索 pre->rchild = p; //前驱右孩子指针指向后继(当前结点p) } pre = p; //=== InThreading(p->rchild); //递归右子树线索化 } } 　　中间部分代码做了这样的事情： 　　  　　因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild = p，并且设置pre->rtag = Thread，完成后继结点的线索化。如图： 　　
　　  　　    if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值了pre，所以可以将pre赋值给p->lchild，并修改p->ltag = Thread（也就是定义为1）以完成前驱结点的线索化。 　　
　　  　　     　　    完成前驱和后继的判断后，不要忘记当前结点p赋值给pre，以便于下一次使用。 　　     　　    有了线索二叉树后，对它进行遍历时，其实就等于操作一个双向链表结构。 　　
　　    和双向链表结点一样，在二叉树链表上添加一个头结点，如下图所示，并令其lchild域的指针指向二叉树的根结点（图中第一步），其rchild域的指针指向中序遍历访问时的最后一个结点（图中第二步）。反之，令二叉树的中序序列中第一个结点中，lchild域指针和最后一个结点的rchild域指针均指向头结点（图中第三和第四步）。这样的好处是：我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。 　　
　　 遍历代码如下所示。 　　//t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。 //中序遍历二叉线索树表示二叉树t int InOrderThraverse_Thr(BiTree t) { BiTree p; p = t->lchild; //p指向根结点 while(p != t) //空树或遍历结束时p == t { while(p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点 { p = p->lchild; } printf(“%c “, p->data); //显示结点数据，可以更改为其他对结点的操作 while(p->rtag == Thread && p->rchild != t) { p = p->rchild; printf(“%c “, p->data); } p = p->rchild; //p进入其右子树 } return OK; } 　　说明： 　　    （1）代码中，p = t->lchild；意思就是上图中的第一步，让p指向根结点开始遍历； 　　    （2）while(p != t)其实意思就是循环直到图中的第四步出现，此时意味着p指向了头结点，于是与t相等（t是指向头结点的指针），结束循环，否则一直循环下去进行遍历操作； 　　    （3）while(p-ltag == Link)这个循环，就是由A->B->D->H，此时H结点的ltag不是link（就是不等于0），所以结束此循环； 　　    （4）然后就是打印H； 　　    （5）while(p->rtag == Thread && p->rchild != t)，由于结点H的rtag = Thread（就是等于1），且不是指向头结点。因此打印H的后继D，之后因为D的rtag是Link，因此退出循环； 　　    （6）p=p->rchild；意味着p指向了结点D的右孩子I； 　　    （7）…..，就这样不断的循环遍历，直到打印出HDIBJEAFCG，结束遍历操作。 　　    从这段代码可以看出，它等于是一个链表的扫描，所以时间复杂度为O(n)。 　　    由于充分利用了空指针域的空间（等于节省了空间），又保证了创建时的一次遍历就可以终生受用后继的信息（意味着节省了时间）。所以在实际问题中，如果所用的二叉树需要经过遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。 　　typedef enum{Link, Thread} PointerTag; //link = 0表示指向左右孩子指针 //Thread = 1表示指向前驱或后继的线索 typedef struct BitNode { char data; //结点数据 struct BitNode *lchild; //左右孩子指针 struct BitNode *rchild; PointerTag ltag; //左右标志 PointerTag rtag; }BitNode, *BiTree; BiTree pre; //全局变量，始终指向刚刚访问过的结点 //前序创建二叉树 void CreateTree(BiTree *t) { char ch; scanf(“%c”, &ch); if(ch == ‘#’) { *t = NULL; } else { (*t) = (BiTree)malloc(sizeof(BitNode)); if((*t) == NULL) { return; } (*t)->data = ch; CreateTree(&((*t)->lchild)); CreateTree(&((*t)->rchild)); } } //t指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。 //中序遍历二叉线索树表示的二叉树t int InOrderThraverse_Thr(BiTree t) { BiTree p; p = t->lchild; //p指向根结点 while(p != t) { while(p->ltag == Link) //当ltag = 0时循环到中序序列的第一个结点 { p = p->lchild; } printf(“%c “, p->data); //显示结点数据，可以更改为其他对结点的操作 while(p->rtag == Thread && p->rchild != t) { p = p->rchild; printf(“%c “, p->data); } p = p->rchild; //p进入其右子树 } return OK; } //中序遍历进行中序线索化 void InThreading(BiTree p) { if(p) { InThreading(p->lchild); //递归左子树线索化 if(!p->lchild) //没有左孩子 { p->ltag = Thread; //前驱线索 p->lchild = pre; //左孩子指针指向前驱,这里是第3步 } if(!pre->rchild) //没有右孩子 { pre->rtag = Thread; //后继线索 pre->rchild = p; //前驱右孩子指针指向后继(当前结点p) } pre = p; InThreading(p->rchild); //递归右子树线索化 } } //建立头结点，中序线索二叉树 int InOrderThread_Head(BiTree *h, BiTree t) { (*h) = (BiTree)malloc(sizeof(BitNode)); if((*h) == NULL) { return ERROR; } (*h)->rchild = *h; (*h)->rtag = Link; if(!t) //如果为NULL { (*h)->lchild = *h; (*h)->ltag = Link; } else { pre = *h; (*h)->lchild = t; //第一步 (*h)->ltag = Link; InThreading(t); //找到最后一个结点 pre->rchild = *h; //第四步 pre->rtag = Thread; (*h)->rchild = pre; //第二步 } } int main(int argc, char argv) { BiTree t; BiTree temp; printf(“请输入前序二叉树的内容: 　　”); CreateTree(&t); //建立二叉树 InOrderThread_Head(&temp, t); //加入头结点，并线索化 printf(“输出中序二叉树的内容: 　　”); InOrderThraverse_Thr(temp); printf(” 　　”); return 0; }