一，问题的提出

所谓线性，指的是任何元素至多有一个前驱或后驱元素。一般情况下，不管是用数组还是用链表实现，对线性表的大多数的操作总避免不了线性的时间复杂度，这是由于其逻辑结构是线性这一本质所决定的。

但是实际上，线性的逻辑结构并不能解决所有的事情，很多事情并不能沿着一条线走下去，也很少存在这么简单的事情，往往在一个层次上会有很多的元素，为了把这个关系网完整的表现出来，于是就有了树这样的一个结构。

拿这个图书分类的例子就可以很轻易的理解上面所说的话了。

二，树的特点

• 首先分类体系是层次化的。树是一种分层结构，越接近顶部的层越普遍，越接近底部的层越独特。

• 分类树的第二个特征：一个节点的子节点与另一个节点的子节点之间是隔离、独立的。

• 分类树的第三个特征：每一个节点都具有唯一性。

三，通过一些例子让大家更好的理解线性结构和非线性结构的本质特征

1，查找

严格的定义来讲：给定一个记录的集合R，根据某个给定的关键字K，从集合R中找出关键字与K相同的记录，这个过程称为查找。

查找可分为静态和动态两种情况考虑。

所谓静态查找，是指集合中的记录是固定的，不涉及对记录的插入和删除操作，而仅仅是按关键字查找记录。（例如查字典）

静态查找主要有两种方法，

1）顺序查找

顺序查找是一种最基本，直接的查找方法。它从线性表的一端开始，向另一端逐个去除数据元素的关键字，并与要找的关键字K进行比较，然后判断。

int SequentialSearch(List Tbl, ElementType K) {
  //在顺序存储的表Tbl中查找关键字为K的数据元素，使用“哨兵”
  int i;
  Tbl->Data[0] = k;//建立哨兵
  for (i = Tbl->Last; Tbl->Data[i] != k; i--);
  return i;//查找成功返回所在单元下标。不成功返回0
}

2）二分查找

上述算法由于它的逻辑结构是线性的，所以时间复杂度也是线性的，而当线性表中数据元素是按大小排列存放时，可以设计一种更高效率的新算法——二分查找

二分查找也称为折半查找，是针对线性表中数据的存放是有序的这一特性而采取的一种有效方法。

int BinarySearch(List Tbl, ElementType K) {
  //在表Tbl中查找关键字为k的数据元素
  int left, right, mid, NoFound = -1;
  left = 1;//左边界
  right = Tbl->Lengh;//右边界
  while (left <= right) {
    mid = (left + right) / 2;
    if (K < Tbl->Data[mid])
      right = mid - 1;
    else if (K > Tbl->Data[mid])
      left = mid + 1;
    else
      return mid;
  }
  return NoFound;//查找不成功返回-1.
}

二分查找的时间复杂度是o（logn）

对于动态查找而言，集合中的记录是动态变化的，还可能发生插入和删除。相比之下会复杂一些，就不做讲解了。

四，树

从上面我们知道，当数据具有有序性时，基于线性表的二分查找算法的时间复杂度会快很多，那我们思考，当数据不具有这些特性的时候，能否采用其他的方法，使得算法也具有较好的时间复杂度。

ASL（Average Search Length），即平均查找长度，其实也就是平均查找次数。

越大，时间性能越不好。

分层次组织在管理上具有更高的效率

1，树的定义：

n(n>=0)个结点构成的有限集合

当n=0时，称为空树。

对于任何一颗非空树：

1）树中有一个称为“根（Root）”的特殊结点，用r表示

2）其余结点可分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，称为原来树的“子树（Sub Tree）”

2，

由上述树的定义可以看出这是一种递归的定义形式。由于子树是不相交的，那么除了根节点外，树中每条边将某个结点与其父节点连起来。因此除了根节点外，每个结点有且仅有一个父节点。这隐含着一颗N个结点的树有N-1条边。

3，

m(m>=0)棵树的集合称为“森林”，对树中的每个结点而言，其子树的集合即为森林。因此，任何一棵树可以看作为一个二元组Tree=（Root，Forest）。

4，树的一些基本术语

1）结点的度（Degree）：

结点的子树个数

2）树的度：

树的所有结点中最大的度数

3）叶结点：（Leaf）

度为0的结点（也可以叫做端节点）

4）父结点（Parent）：

有子树的结点时其子树的根节点的父节点。

5）子结点（Child）：

与父节点相反

6）兄弟结点（Sibling）：

具有同一父结点的各结点彼此是兄弟结点

7）路径和路径长度：

从结点n1到nk的路径为一个结点序列。路径所包含边的个数为路径的长度。

8）祖先结点（Ancestor）：

沿着树根到某一结点路径上的所有结点都是这个结点的祖先结点。

9）子孙结点：

某一结点的子树中的所有结点时这个结点的子孙

10）结点的层次：

规定根结点在1层，其他任一结点的层数是其父节点的层数加一

11）树的深度：

树中所有结点中最大层次是这棵树的深度

五，二叉树

如果我们尝试去将上面的树表达出来，结果大致如下图所示，我们发现，如果按图表示的话，每个结点的结构不同，就算按照每个结点3个指针域来算，一共就需要3（n-1）个指针域。会造成很大的空间浪费。

所以，我们推出了另一种表示方法：

儿子-兄弟表示法

如图所示，每个结点只有两个指针域，一个指向它的第一个儿子，另一个指向下一个兄弟结点。

这样就在最大程度上减少了空间浪费。

如果我们将其顺时针再旋转45度，就形成了类似树的形状，这时就称作二叉树。

它的度是2，每个结点都最多有两个子结点。

1，二叉树的定义：

一个有穷的结点集合

这个集合可以为空，若不为空。

则它是由根结点和称为其左子树Tl和右子树Tr的两个不相交的二叉树组成。

与树的一般定义不同，除了每个结点至多有两颗子树外，子结点是有左右顺序之分的。例如下图中，按一般树的定义来说，他们就是同一颗树。但是按二叉树的概念来讲，它们是不同的两个树。

2，特殊二叉树

1）斜二叉树

实际上就相当于是一个链表了

2）完美二叉树/满二叉树

每个结点都有两个儿子，除了最底下的叶结点。

3）完全二叉树

右边可以缺，左边不能缺

3，二叉树的几个重要性质

1）一个二叉树第i层的最大结点数为：2^i-1,i>=1

2）深度为k的二叉树有最大结点总数为：(2^k)-1，k>=1

3）对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，n1是度为1的非叶结点个数，那么两者满足关系n0 = n2 + 1

设n为总结点数，

n=n0+n1+n2

n=0*n1+1*n1+2*n2+1

所以推出上式。

4）具有n个结点的完全二叉树的深度为（log2n）+1

4，二叉树的存储结构

在计算机内存中存储二叉树时，除了存储它的每个结点数据外，结点之间的逻辑关系（父子关系）也要得到体现。

1）顺序存储结构

通常情况下，顺序存储结构用于完全二叉树的存储。

具体实现是从树的根结点开始，从上层至下层，每层从左到右，依次给结点编号并将数据放到一个数组的对应单元中。

i/2取整大于等于1时，【i/2】是其父节点，当 i/2取整等于0时，表明该节点是树的根结点，无父节点、

2）二叉树的链表存储

虽然完全二叉树的顺序存储具有存储空间利用率高，计算简单的双重优点，但它并不适合于一般的二叉树。如上图所示，浪费了大量的空间。

另外，二叉树的顺序存储避免不了顺序存储的固有缺点即不易实现增加，删除操作。因此，二叉树的顺序存储方式适用于一定的条件，对于不需要修改的完全二叉树是一种较好的选择。

实际上，二叉树最常用的表示方法就是用链表表示，每个结点由数据和左右指针三个数据成员组成。

typedef struct TreeNode* Position;
typedef Position BinTree;
struct TreeNode {
  ElementType Data;//结点数据
  BinTree Left;//左子树
  BinTree Right;//右子树
};

虽然图中连线是没有指向的，但是连线之间仍然是有向的，其方向隐含从上而下，即上方叫做前驱结点，下方叫做后继结点。

5，二叉树的操作

判断二叉树是否为空是比较简单的事。主要我们介绍的就是遍历和创建二叉树的操作。

1）二叉树的遍历

树的遍历是指访问树的每个结点，且每个结点仅被访问一次。访问是一个抽象的概念，实际上可以是戳结点数据的各种处理。二叉树的遍历可按二叉树的构成以及访问结点顺序分为四种方式即，先序遍历，中序遍历，后序遍历，层序遍历。

中序遍历：

遍历过程为:

1）中序遍历其左子树;

2）访问根结点;

3）中序遍历其右子树。

void InOrderTraversal(BinTree BT) {
  if (BT) {
    InOrderTraversal(BT->Left);
    printf("%d", BT->Data);
    InOrderTraversal(BT->Right);
  }
}

先序遍历：

遍历过程为:

①访问根结点;

②先序遍历其左子树;

③先序遍历其右子树。

void PreOrderTraversal ( BinTree BT )
{
    if(BT){
        printf ("号d”，BT- >Data)；
        PreOrderTraversal ( BT->Left )；
        PreOrderTraversal ( BT->Right )；
    }
}

后序遍历：

遍历过程为:

①后序遍历其左子树;

②后序遍历其右子树;

③访问根结点。

void Pos tOrderTraversal ( BinTree BT ){
    if(BT){
        Pos tOrderTraversal ( BT-> >Left )；
        Pos tOrderTraversal( BT- >Right)；
        printf ("%d"，BT->Data)；
    }
}

上述三种方式都是递归实现，但是，并非所有程序设计语言都支持递归。另一方面，递归程序虽然简洁，但程序执行效率不高。因此，我们继续研究如何用非递归解决这个问题。

我们首先来分析：

先序、中序和后序遍历过程:遍历过程中经过结点的路线一样，只是访问各结点的时机不同。都是从根结点a开始的。

注意到,这一路线正是从根结点开始沿左子树深人下去，当深人到最左端，无法再深人下去时，则返回刚才深人时遇到的结点，再逐一进人其右子树，进行如此的深人和返回，直到最后从根结点的右子树返回到根结点为止。先序遍历是在深人时遇到结点就访问,中序遍历是在从左子树返回时遇到结点访问，后序遍历是在从右子树返回时遇到结点访问。在这一过程中，返回结点的顺序与进人结点的顺序相反，即后进人先返回,正好符合堆栈结构后进先出的特点。因此，可以借助于堆栈来实现这一遍历路线。其过程如下。在沿左子树深人时，进入一个结点就将其压人堆栈。若是先序遍历，则在人栈之前访问之;当沿左分支深人不下去时，则返回，即从堆栈中弹出前面压人的结点;若为中序遍历，则此时访问该结点，然后从该结点的右子树继续深人;若为后序遍历，则将此结点二次入栈，然后从该结点的右子树继续深人，与前面类同，仍为进入一个结点人栈一个结点，深人不下去再返回，直到第二次从栈里弹出该结点，才访问之。

后序遍历需要将结点二次入栈，所以情况相对复杂，我们这里主要就以中序遍历为例：

1）遇到一个结点，就把它压栈，并去遍历它的左子树;

2）当左子树遍历结束后，从栈顶弹出这个结点并访问它;

3）然后按其右指针再去中序遍历该结点的右子树。

void InOrderTraversal( BinTree BT )
{     BinTree T=BT ;
    Stack s = CreatStack( MaxSize ) ; /*创建并初始化堆栈s*/
    while( T | | ! IsEmpty(S) ) {
        while(T){ /*- 直向左并将沿途结点压入堆栈*/
            Push(S,T) ;
            T = T->Left;
    }
        if (! IsEmpty(S)) {
            T = Pop(S); /*结点弹出堆栈*/
            printf("%5d"，T->Data); /* (访问)打印结点*/
            T = T->Right; /*转向右子树*/
        }
    }
}

前序？后序？

void postOrderTraversal(BinTree BT)
{
    BinTree T = BT;
    Stack S = CreatStack(maxsize);
    BinTree Temp = NULL;//temp保存上次弹出的元素，用于和当前弹出的节点的右节点进行比较
    while(T || !isEmpty(S)){
        while(T){
            Push(S, T);
            T = T->left;
        }
        if(!isEmpty()){
            T = pop(S);//本次弹出的结果
            if(T->right == NULL || T->right == Temp){// 没有右节点或者右节点已经弹出，此时便可以访问根（本）节点
                print(T->data);
                Temp = T;
                T = NULL;
            }else{
                Push(S, T);//本节点有右节点且右节点尚未弹出
                T = T->right;
            }
        }
    }
}

层序遍历：

除了先序、中序和后序三种基本的二叉树遍历方法外有时还用到二叉树的层序遍历。层序遍历是按树的层次，从第1层的根结点开始向下逐层访问每个结点，对某一层中的结点是按从左到右的顺序访问。因此，在进行层序遍历时，完成某一层结占的访问后，再按它们的访问次序依次访问各结点的左右孩子,这样一层一层进行下去，先遇到的结点先访问，这与队列的操作过程是吻合的。具体的算法实现可以设置一-个队列结构，遍历从根结点开始，首先将根结点指针入队，然后开始执行下面三个操作:

①从队列中取出一个元素;

②访问该元素所指结点;

③若该元素所指结点的左、右孩子结点非空，则将其左、右孩子的指针顺序人队。

不断执行这三步操作，直到队列为空，再无元素可取，二叉树的层序遍历就完成了。

void LevelOrderTraversal ( BinTree BT ){
    Queue Q;
    BinTree T ;
    if ( !BT ) return; /*若是空树则直接返回*/
    Q = CreatQueue( MaxSize ) ; /*创建并初始化队列0*/
    AddQ(Q，BT);
    while(!IsEmptyQ(Q)){
        T = DeleteQ( ) ;
        printf (“号d\n"，T->Data) ; /*访问取出队列的结点*/
        if ( T->Left )
            AddQ(Q，T->Left ) ;
        if ( T->Right )
             AddQ( Q，T->Right ) ;
    }
}

[例1]遍历二叉树的应用:输出二叉树中的叶子结点。

在二叉树的遍历算法中增加检测结点的“左右子树是否都为空”。

void PreOrderPrintLeaves( BinTree BT )
{
    if(BT){
        if ( !BT-Left && !BT->Right )
            printf ("%d", BT->Data ) ;
        PreOrderPrintLeaves ( BT-> Left ) ;
        PreOrderPrintLeaves ( BT->Right ) ;
    }
}

[例2]求二叉树的高度

int Pos tOrderGetHeight( BinTree BT )
{
    int HL，HR，MaxH ;
    if(BT){
        HL = Pos torderGetHeight (BT->Left) ; /*求左子树的深度*/
        HR = PostOrderGe tHeight (BT->Right) ; /*求右子树的深度*/
        MaxH = (HL > HR) ? HL : HR; /*取左右子树较大的深度*/
        return ( MaxH + 1 ) ; /*返回树的深度*/
    }
    else
        return 0; /*空树深度为0 */
}

[例3]二元运算表达式及其遍历

表达式是由一系列符号和运算数组成的。我们所熟知的四则运算是二元运算，前面我们讲过表达式的不同表达形式。由于每个运算符完成两个运算数的算术运算，因此用二叉树表示表达式是合适的。

即树的叶结点是运算数，根节点是运算符。

[例4]由两种遍历序列确定二叉树

2）上面讲完了二叉树的遍历，现在讲一讲二叉树的创建。

由于树是非线性结构，创建一颗二叉树必须首先确定树中结点的输入顺序，常有的方法是先序创建和层序创建两种。

层序创建所用的结点输人序列是按树的从上至下从左到右的顺序形成的，各层的空结点输人数值0。在构造二叉树过程中,需要.个队列暂 时存储各结点地址,其创建过程如下。

(1)输人第一个数据:

●若为0,表示是此树为空,将空指针赋给根指针，树构造完毕;

●若不为0，动态分配一个结点单元，并存人数据，同时将该结点地址放人队列。

(2)若队列不为空，从队列中取出一个结点地址,并建立该结点的左右孩子:

●从输人序列中读人下一数据;

若读人的数据为0,将出队结点的左孩子指针置空;否则，分配一个结点单元,存入所读数

值，并将其置为出队结点的左孩子，同时将此孩子地址入队;

●接着再从输人序列中读人下一个数据;

若读人的数据为0，将出队结点的右孩子指针置空;否则,分配一个结点,存入所读数值,并

将其置为出队结点的右孩子，同时将此孩子地址人队。

(3)重复第(2)步过程，直到队列为空，再无结点出队，构造过程到此结束。

/*假设结点数据是整数*/
typedef int ElementType；
/*用0表示没有结点*/
#define NoInfo 0
BinTree creatBinTree()
{
    ElementType Data;
    BinTree BT,T;
    Queue Q=CreatQueue();
        /*创建空队列*/
    /*建立第1个结点,即根结点*/
    scanf( "%d"，&Data) ;
    if( Data ! =NoInfo) {
    /*分配根结点单元，并将结点地址入队* /
    BT=( BinTree)malloc( sizeof( struct TNode) ) ;
    BT->Data=Data;
    BT->Left = BT->Right = NULL;
    AddQ(Q，BT);
    }
    else return NULL;
/*若第1个数据就是0,返回空树*/
    while(! IsEmpty(Q)){
        T=DeleteQ(Q); /*从队列中取出一结点地址:* /
        scanf("gd"，&Data); /* 读人T的左孩子* /
        if(Data ==NoInfo) T->Left = NULL:
        else ( /* 分配新结点,作为出队结点左孩子;新结点人队*/D0
            T->Left=( BinTree)malloc(sizeof(struct TNode));人储月电a
            T->Left->Data = Data;
            T->Left->Left =T->Left ->Right = NULL;
            AdaQ(Q，T->Left) ;
        }
        scanf( "%d",&Data); /* 读入T的右孩子* /
        if( Data ==NoInfo) T->Right = NULL;
        else { /*分配新结点,作为出队结点右孩子;新结点人队* /湖出0 (6)
            T->Right=( BinTree)malloc( sizeof(struct TNode)) ;
            T->Right->Data=Data;
            T->Right->Left =T->Right->Right =NULL;
            AddQ(Q，T->Right);
        }
    }/*结束while */ 
    return BT;
}

已经写的有点多了，今天就写到这里吧，等我后面的视频出来吧。