[如何创建二叉排序树]创建二叉排序树的时间复杂度!

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树、二叉堆、和哈夫曼树。

二叉树的遍历是指依照某种顺序逐一访问二叉树的所有结点。这里的“访问”可以是输出结点中的数据，也可以是对结点进行某种处理或操作。遍历操作本着“不重不漏”的原则，即每个结点只能访问一次，且全部结点都能访问到。

为什么需要二叉树遍历呢？线性数组或链表可以单向从头到尾遍历或反向遍历。二叉树是非线性数据结构，通过遍历可以将二叉树中的结点访问一次且仅一次，从而得到访问结点的顺序序列。从这个意义上说，遍历操作就是将二叉树中结点按一定规律线性化的操作，目的在于将非线性化结构变成线性化的访问序列。

二叉树遍历有深度优先遍历和广度优先遍历二种思想。

1 深度优先的递归遍历

从二叉树的定义可知，一棵二叉树宏观上由三部分组成：根结点、根结点的左子树和根结点的右子树。因此只要完整地遍历了这三部分，就等于遍历了整棵二叉树。二叉树的根结点可以通过指针直接访问到根结点的数据。但是如何遍历根结点的左子树和右子树呢？其实可以把根结点的左子树和右子树看作两棵独立的二叉树，以同样的方式来遍历左子树和右子树显然这是一种递归形式的遍历。

二叉树通常有3种遍历方法（先左后右）：

先序(根)遍历（DLR，根左右）

中序(根)遍历（LDR，左根右）

后序(根)遍历（LRD，左右根）

其中D表示根节点、L表示左子树，R表示右子树。因为二叉树结构本身就是一种递归的结构，所以这3种遍历方式也都是递归形式定义的。先序遍历DLR表示D→L→R，如下：

void PreOrderTraverse(BiTreee T){

if(T){ //如果二叉树为空，递归遍历结束

visit(T); //访问根节点，可以是输出或其它处理

PreOrderTraverse(T->lchild); //先序遍历T的左子树

PreOrderTraverse(T->rchild); //先序遍历T的右子树

}

}

其它两种遍历只是visit(T);语句放置的位置不一样。所以三种递归遍历算法的搜索路线相同，只是访问各节点的时间不同。

具体线路为： 从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。(逆时钟方向，整体上是从左子树到右子树，从内到外)

（三种递归相同的搜索路线，类似于斐波那契的递归算法。是一种函数的递归调用，是一个调用栈对函数和参数在栈中的压入与弹出形成的路线，相关内容请参考：C｜深入了解函数调用与递归调用（递推、回归））

任一节点都有三次访问的机会，如下图所示：

作为根节点被调用（在上图中用箭头↙或↘表示）；

从左子树返回（如果是叶结点，则是从空左子树返回，用箭头↗表示）；

从右子树返回（如果是叶结点，则是从空右子树返回，用箭头↖表示）；

对于先序遍历来说，剪头第一次经过的结点（递归调用第一时间访问根节点），就是遍历的序列，以后再次经历就不算进去了。

对于中序遍历来说，剪头第二次经过的结点（左子树返回后访问根节点），就是遍历的序列，之前的和以后的再次经历就不算进序列里去了。

对于后序遍历来说，剪头第三次经过的结点（右子树返回后访问根节点），就是遍历的序列，之前经历的就不算进去了。

2 二叉树前序遍历的非递归实现

二叉树的遍历可以通过递归调用实现，也可以用非递归来实现。当用非递归来实现时，需要使用一个栈来辅助，用来记录尚待遍历的结点，以备以后访问。

二叉树的非递归前序遍历：对二叉树各结点的访问顺序是沿其左链一路访问下来，在访问结点的同时将其入栈，直到左链为空。然后结点出栈，对于每个出栈结点，即表示该结点和其左子树已被访问结束，应该访问该结点的右子树。具体步骤如下：

2.1 当前指针指向根结点；

2.2 打印当前结点，当前指针指向其右子树并进栈，重复操作，直到左子树为NULL；

2.3 依次退栈，将当前指针指向右子树；

2.4 苦栈非空或当前指针非NULL，执行2.2，否则结束。

总的思路就是从根结点开始，左子树遍历，并把左子结点推入栈中，然后出栈操作，同时遍历右子树。遍历的顺序上非递归遍历的顺序路线相同。通过双重循环实现。

3 编程实例

编程实现二叉树的创建和先序、中序、后序遍历及深度优先的非递归遍历：

代码：

运行结果：

需要注意的是，在CreatBiTree(BiTree *T)中，因为BiTree本身就是链表指针，所以*T中的T是一个指向指针的指针，T为指向BiTree类型的指针类型，也就是指向指针的指针，*T实质上是一个指针变量。故修改*T就修改了实参（根指针）本身 。

以上三种递归遍历的方法，如果将访问的语句去掉，也三种结构的语法相同，所以说，他们的路径是相同的，只是对根结点的访问时机不同。

深度优先的递归或非递归实现，都是从左往右，从外往内，遍历路线的顺序相同。递归在于编程语言使用了调用栈，非递归在于编程人员自己使用了一个辅助栈。

附源码：

#include ";

#define MAX 20

typedef struct BiTNode{

char data;/*结点的数据域*/

struct BiTNode *lchild , *rchild;/*指向左孩子和右孩子*/

} BiTNode , *BiTree;

void CreatBiTree(BiTree *T){/*按先序序列创建一棵二叉树*/

char c;

scanf("%c",&c);

if(c == ' ') *T = NULL;

else{

*T = (BiTNode * )malloc(sizeof(BiTNode));/*创建根结点*/

(*T)->data = c;/*向根结点中输入数据*/

CreatBiTree(&((*T)->lchild));/*递归地创建左子树*/

CreatBiTree(&((*T)->rchild));/*递归地创建右子树*/

}

}

void PreOrderTraverse(BiTree T ){/*先序遍历二叉树*/

if(T){/*递归结束条件，T为空*/

printf("%3c",T->data);/*访问根结点,将根结点内容输出*/

PreOrderTraverse(T->lchild);/*先序遍历T的左子树*/

PreOrderTraverse(T->rchild);/*先序遍历T的右子数*/

}

}

void InOrderTraverse(BiTree T){/*中序遍历二叉树*/

if(T){/*如果二叉树为空，递归遍历结束*/

InOrderTraverse(T->lchild);/*中序遍历T的左子树*/

printf("%3c",T->data);/*访问根结点*/

InOrderTraverse(T->rchild);/*中序遍历T的右子数*/

}

}

void PosOrderTraverse(BiTree T){/*后序遍历二叉树*/

if(T){/*如果二叉树为空，递归遍历结束*/

PosOrderTraverse(T->lchild);/*后序遍历T的左子树*/

PosOrderTraverse(T->rchild);/*后序遍历T的右子数*/

printf("%3c",T->data);/*访问根结点*/

}

}

void PreOrder_NR(BiTree T)//深度优先非递归前序遍历

{

BiTree Ptr;

BiTree Stack[MAX];//栈定义

int top=0;//栈顶指针

Ptr = T;

do

{

while(Ptr!=NULL)//树结点非空，遍历其左子树

{

printf("%3c",Ptr->data);//操作结点

Stack[top]=Ptr;//树结点进栈

top++;

Ptr=Ptr->lchild;//查看左子树

}

if(top>0)//栈非空，出栈

{

top--;

Ptr=Stack[top];

Ptr=Ptr->rchild;//取栈顶点结点右子树

}

} while(top>0 || Ptr!=NULL);

}

main()

{

BiTree T = NULL;/*最开始T指向空*/

printf("需要创建和遍历的二叉树：\n");

printf(" A\n");

printf(" / \\\n");

printf(" B E\n");

printf(" / \\ \\\n");

printf(" C D F\n");

printf("Input some characters to create a binary tree\n");

printf("（按先序序列建立）\n");

printf("例如，ABC##D##E#F##↙，#表示空格,↙表示回车\n");

CreatBiTree(&T);/*创建二叉树*/

printf("The squence of preorder traversaling(先序遍历) binary tree\n");

PreOrderTraverse(T);/*先序遍历二叉树*/

printf("\nThe squence of inorder traversaling(中序遍历) binary tree\n");

InOrderTraverse(T);/*中序遍历二叉树*/

printf("\nThe squence of posorder traversaling(后序遍历) binary tree\n");

PosOrderTraverse(T);/*后序遍历二叉树*/

printf("\n深度优先非递归前序遍历二叉树\n");

PreOrder_NR(T);

getchar(); getchar();

}

－End－