基本述语

树的度(Degree of Tree)：树的度是树内各结点度的最大值。
叶子(Leaf)：度为0的结点称为叶子或终端结点。

基本性质

树中的结点数等于所有结点的度数之和加1。
度为m的树中第i层上至多有m(i-1)结点。
高度为h的m叉树至多有$\frac{m^h -1}{m-1}$个结点。
具有n个结点的m叉树的最小高度为$\log_m[(n(m-1))+1]$向上取整。

二叉树

二叉树与树一样具有递归性质，二叉树与树的区别主要有以下两点：

二叉树每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点);
二叉树的子树有左右之分，其次序不能任意颠倒。

二叉树的性质：

任何一棵二叉树T，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1

满二叉树

一棵高度为知且含有2 h -1个结点的二叉树称为满二叉树，即树中的每层都含有最多的结点，满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2。

可以对满二叉树按层序编号：约定编号从根结点（根结点编号为1）起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为i的结点，若有双亲，则其双亲为$\lfloor \frac i 2\rfloor $ , 若有左孩子，则左孩子为2i；若有右孩子，则右孩子为2i+1。

完全二叉树

高度为h、有n个结点的二叉树，当且仅当其每个结点都与高度为h的满二叉树中编号为 1-n的结点一一对应时，称为完全二叉树，（完全二叉树就是对应相同高度的满二叉树缺失最下层最右边的一些连续叶子结点）

具有n个结点的完全二叉树的深度为$\lfloor \log_2 n\rfloor +1$

性质5:如果对一棵有几个结点的完全二叉树的结点按层序编号，则对任一结点$i(1\le i\le n)$，有:
(1)如果i=1，则结点i是二又树的根，无双亲;如果i>1，则其双亲是$\lfloor \frac i 2\rfloor$
(2)如果2i>n，则结点i无左孩子;如果2in，则结点i无右孩子;如果2i+1<n则其右孩子是2i+1

几个特殊的二叉树

二叉排序树

左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字；左子树和右子树又各是一棵二叉排序树。

平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1。

存储结构

双亲表示法

//双亲表示法
#define MAXTREE SIZE 100#
typedef int TElemType;// 结点的结构
typedef struct {
 	TElemType data;
    int parent;
} PTNode;
// 树的结构
typedef struct {
	PTNode nodes[MAX_TREE_SIZE];    
    int r，n;//根的位置和结点数
} PTree;

找双亲容易，找孩子难。

孩子表示法：多重链表

每个结点有多个指针域，分别指向其子树的根

结点同构：结点的指针个数相等，为树的度D 结点不同构：
结点指针个数不等，为该结点的度d

孩子表示法：孩子链表

每个结点的孩子结点用单链表存储，再用含n个头指针的线性表指向每个孩子链表。

找孩子容易找双亲难

//孩子表示法：孩子链表
//定义孩子结点
typedef struct ChildNode {
    int childIndex; // 孩子节点在数组中的位置
    struct ChildNode* next;//下一个孩子节点的指针
} ChildNode;
//定义树的结点,里面的指针只指向第一个孩子节点
typedef struct TreeNode{
    char data; //存储的数据，此处设定为字符型
    struct ChildNode* firstChild; //第一个孩子结点的指针
}TreeNode;
//定义树
typedef struct{
    TreeNode nodes[MAX_TREE_SIZE];
    int r,n;//根的位置和结点数
}Tree;

孩子兄弟表示法

用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点

// 孩子兄弟表示法
typedef struct CSNode {
	char data;// 节点数据，可根据需要修改数据类型
    struct CSNode* firstChild; //第一个孩子节点的指针
    struct CSNode* nextSibling;//右侧兄弟节点的指针CSNode
}CSNode,*CSTree;

特点： 1. 操作容易 2. 破坏了树的层次

顺序存储实现

按完全二叉树的结点层次编号，依次存放二叉树中的数据元素.

➢结点间的父子关系蕴含在其存储位置中

➢浪费空间，适于存满二叉树和完全二叉树

二叉链表

指针域用两个指针分别指向左右子结点。

找孩子容易找双亲难

在n个结点的二叉链表中，有 n+1 个空指针域

具有 n 个内部节点的二叉树：

• 有n−1 个内部指针，因为除了根节点，每个节点都有一个指针指向它。

• 有 2n 个指针总共从所有的内部节点出来，因为每个节点有2个指针。

• 这 2n 个指针分为两种：指向内部节点的和指向外部节点的。我们已经知道有 n−1 个指针指向内部节点，因此有 2n-(n-1)=n+1 个指针指向外部节点（即空指针域）。

// 定义二叉树的节点结构体
typedef struct Node {
	char data; // 节点的数据部分，可以根据需求修改数据类型
    struct Node* left;// 指向左孩子的指针
    struct Node* right;//指向右孩子的指针
} Node;

三叉链表

三个指针，分别指向左子结点、右子结点、双亲结点。

找孩子容易找双亲容易

// 定义二叉树的节点结构体
typedef struct TriNode {
	char data; // 节点的数据部分，可以根据需求修改数据类型
    struct TriNode* left;// 指向左孩子的指针
    struct TriNode* right;//指向右孩子的指针
    struct TriNode* parent;//指向父节点的指针
} TriNode;

二叉树 & 森林

森林转化为二叉树

对于森林中的每棵树，从根节点开始，如果某个节点有多个孩子，将最左侧的结点保留，右边的子树接到最左侧结点的右节点。
将树根相连，如果树根较多，往右下角接。

二叉树转化为森林

从根节点开始，一直找右节点，向右走，直到没有右结点。将这条向右的路线上，所有的的枝断开，得到各个独立的树。
对于各个子树的节点，从根节点开始，一直找右节点，向右走，直到没有右结点。将这条路上的右测侧的节点连到左侧节点的双亲。

右子树不为空的二叉树只能转换成森林

二叉树的遍历

先（根）序的遍历算法：先访问根结点，然后分别先序遍历左子树、右子树
中（根）序的遍历算法：先中序遍历左子树，然后访问根结点，最后中序遍历右子树
后（根）序的遍历算法：先后序遍历左、右子树，然后访问根结点层次遍历算法：从上到下、从左到右访问各结点

//先序遍历
void pre0rderTraversal(Node* root){
    if(root != NULL){
        printf("%c"，root->data);// 访问根节点	
        pre0rderTraversal(root->left);//递归遍历左子树
        pre0rderTraversal(root->right);//递归遍历右子树
    }
}

//中序遍历
void in0rderTraversal(Node* root){
    if(root!=NULL){
        in0rderTraversal(root->left);
        printf("%c"，root->data);// 访问根节点
        in0rderTraversal(root->right);
    }
}
//后序遍历
void post0rderTraversal(Node* root){
    if(root!=NULL){
        post0rderTraversal(root->left);        
        post0rderTraversal(root->right);
        printf("%c"，root->data);// 访问根节点
    }
}

层次遍历算法的非递归描述

利用队列实现二叉树的层次遍历非递归算法

将二叉树的根结点入队
队头元素出队并访问，将其非空左、右孩子入队（即以从左向右的顺序将下一层结点保存在队列中）
重复上一步直到队空为止

树的遍历常用方法是先根（序）遍历、后根（序）遍历和按层次遍历。

求树的深度算法（采用孩子—兄弟存储结构）

1.设depth为T的当前最大子树深度，初始为0；
2.若T=NULL，则返回0；
3.否则p=T->firstchild
4.p不为空，则求以p为根的子树深度d （递归）
- 若d>depth，则depth=d；p=p->nextsibling
5.返回depth+1

森林的遍历

森林的遍历分为先序遍历、中序遍历、后续遍历。

本质上就是对于其中每一棵树应用先序遍历、中序遍历、后续遍历。

树	森林	二叉树
先根遍历	先序遍历	先序遍历
后根遍历	后续遍历	后续遍历

由遍历序列确定二叉树

◆ 给定先序、中序遍历序列可唯一确定二叉树。

◆ 给定后序、中序遍历序列可唯一确定二叉树。

◆ 给定层次、中序遍历序列可唯一确定二叉树。

先确定根节点，然后将序列划分，对于每一个子树也确定根节点

线索二叉树

试做如下规定：若结点有左子树，则其Ichild域指示其左孩子，否则令Ichild域指示其前驱; 若结点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其后继。为了避免混淆，尚需改变结点结构，增加两个标志域。

leftTag=0表示指示结点的左儿子，=1表示指示结点的前驱结点

rightTag=0指示结点的右儿子,=1指示结点的后继结点

typedef int TElemType;
typedef enum{
    Link,Thread;
}PointerTag;

typedef struct BiThrNode{
    TElemType data;
    struct BiThrNode *lchild,*rchild;
    PointerTag LTag,Rtag;
}BiThrNode,*BithrTree;

二叉树的线索化是将二叉链表中的空指针改为指向前驱或后继的线索。而前驱或后继的信息只有在遍历时才能得到，因此线索化的实质就是遍历一次二叉树。

以中序线索二叉树的建立为例。附设指针pre指向刚刚访问过的结点，指针p指向正在访问的结点，即pre指向p的前驱。在中序遍历的过程中，检查p的左指针是否为空，若为空就将它指向pre；检查pre的右指针是否为空，若为空就将它指向p。

中序遍历的特点：在中序遍历中，对于任何一个节点，其前驱是其左子树的最右下角的节点，其后继是其右子树的最左下角的节点。

中序序列构造线索二叉树

算法步骤

1）如果p非空，左子树递归线索化。
2）如果p的左孩子为空，则给p加上左线索，将其LTag置为1,让p的左孩子指针指向pre （前驱）；否则将p的LTag置为0。
3）如果pre的右孩子为空，则给pre加上右线索，将其RTag置为1,让pre的右孩子指针指向p （后继）；否则将pre的RTag置为0。
4）将pre指向刚访问过的结点p,即pre = p。
5）右子树递归线索化。

// 中序遍历并线索化
void inOrderThreading(BiThrTree node){
	if(node){
		in0rderThreading(node->lchild);// 如果当前节点的左子树为空，设置lchild为前驱
        if(!node->lchild){
			node->LTag = Thread;
            node->lchild = pre;
        }
// 如果前一个节点的右子树为空，设置rchild为当前节点
// pre为NULL时，说明当前节点是第一个被访问的节点，没有前驱
      	if(pre && !pre->rchild){
            pre->RTag = Thread;
            pre->rchild =node;
        }
		pre = node;
		inOrderThreading( node:node->rchild);
    }
}

遍历中序二叉树

◆线索链表的遍历算法——遍历中序二叉树： 1.指针p指向根结点。 2.P为非空树或遍历未结束时，循环执行以下操作： 1）沿左孩子向下，到达最左下结点p，它是中序的第一个结点； 2）访问p；沿右线索反复查找当前结点*p的后继结点并访问后继结点，直至右线索为0或者遍历结束； 3）转向p的右子树。

◆ 中序线索化链表的第一个结点：左子树上处于“最左下”（没有左子树）的结点。

◆ 中序线索化链表中结点的后继：若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。

void InOrderTraverse(BiThrTree T){
    BiThrTree p=T;
    // 找到最左侧的节点，这是中序遍历的起点
    while(p&& p->LTag == Link){
        p = p->lchild;
    }

	while(p){
		printf("%d"，p->data);
		// 如果右指针是线索，直接指向后继节点
        if(p->RTag == Thread){
            p= p->rchild;
        }
        else{//否则，找到右子树的最左侧节点
            p= p->rchild;
            while(p && p->LTag == Link){
                p= p->lchild;
            }
        }
    }
	printf("\n");
}