树的相关概念

        (1）结点拥有的子树称为结点的度，度为0的结点称为叶结点或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。

        （2）如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树 

树的存储结构

双亲表示法 

结点结构

/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100typedef int TElemType;				/* 树结点的数据类型，目前暂定为整型 */typedef struct PTNode				/* 结点结构 */
{TElemType data;					/* 结点数据 */int parent;						/* 双亲位置 */
} PTNode;typedef struct						/* 树结构 */
{PTNode nodes[MAX_TREE_SIZE];	/* 结点数组 */int r,n;						/* 根的位置和结点数 */
} PTree;

         可根据需求增加左右孩子域、左右兄弟域等结构。存储结构的设计是一个非常灵活的过程。一个存储结构设计得是否合理，取决于基于该存储结构得运算是否合适、是否方便，时间复杂度好不好等。

孩子表示法

        由于树中每个结点可能有多棵子树，可以考虑用多重链表，即每个结点有多个指针域，其中每个指针指向一颗子树得根节点，我们把这种方法叫作多重链表表示法。

方案一

方案二

/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100typedef int TElemType;			/* 树结点的数据类型，目前暂定为整型 */typedef struct CTNode			/* 孩子结点 */
{int child;	struct CTNode *next;	
} *ChildPtr;typedef struct 					/* 表头结构 */
{TElemType data;	ChildPtr firstchild;	
} CTBox;typedef struct	     			/* 树结构 */
{CTBox nodes[MAX_TREE_SIZE];	/* 结点数组 */int r,n;					/* 根的位置和结点数 */
} CTree;

如何知道某个结点得双亲是谁？可以将双亲表示法和孩子表示法综合一下，如下图

孩子兄弟表示法 

        任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此设置两个指针，分别指向该结点的第一孩子和此结点的右兄弟。

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{TElemType data;	struct CSNode *firstchild,*rightsib;	
} CSNode,*CSTree;

        如果有必要，可以再增加一个parent指针域来解决快速查找双亲的问题。

        其实这个表示法的最大好处是它把一颗复杂的树变成了一颗二叉树，这样就可以充分利用二叉树的特性和算法来处理这棵树了。

二叉树的定义

特殊二叉树

斜树

        所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树，这两者统称为斜树。

满二叉树 

完全二叉树 

         左边的是完全二叉树，右边的不是。

二叉树的存储结构

二叉树的顺序存储结构

        若节点 i 有左右孩子，则其左孩子节点为 2*i，右孩子节点为 2*i+1。此性质可用于还原数组中存储的完全二叉树。 

二叉链表 

        二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫作二叉链表。

/* 二叉树的二叉链表结点结构定义 */
typedef struct BiTNode  			/* 结点结构 */
{TElemType data;					/* 结点数据 */struct BiTNode *lchild,*rchild; 	/* 左右孩子指针 */
}BiTNode,*BiTree;

 遍历二叉树

       二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使每个结点被访问一次且仅被访问一次。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。

二叉树的遍历方法

1.前序遍历（根左右）

/* 二叉树的前序遍历递归算法 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 前序递归遍历T */
void PreOrderTraverse(BiTree T)
{ if(T==NULL)return;printf("%c",T->data);		/* 显示结点数据，可以更改为其它对结点操作 */PreOrderTraverse(T->lchild);/* 再先序遍历左子树 */PreOrderTraverse(T->rchild);/* 最后先序遍历右子树 */
}

2.中序遍历（左根右）

/* 二叉树的中序遍历递归算法 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 中序递归遍历T */
void InOrderTraverse(BiTree T)
{ if(T==NULL)return;InOrderTraverse(T->lchild); /* 中序遍历左子树 */printf("%c",T->data);		/* 显示结点数据，可以更改为其它对结点操作 */InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}

3.后序遍历 （左右根）

/* 二叉树的后序遍历递归算法 */
/* 初始条件: 二叉树T存在 */
/* 操作结果: 后序递归遍历T */
void PostOrderTraverse(BiTree T)
{if(T==NULL)return;PostOrderTraverse(T->lchild); 	/* 先后序遍历左子树  */PostOrderTraverse(T->rchild); 	/* 再后序遍历右子树  */printf("%c",T->data);			/* 显示结点数据，可以更改为其它对结点操作 */
}

4.层序遍历 

二叉树的建立

转载自 https://www.cnblogs.com/llhthinker/p/4906631.html

1.交互问答方式

        这种方式是最直接的方式，就是先询问用户根节点是谁，然后每次都询问用户某个节点的左孩子是谁，右孩子是谁。代码如下(其中字符'#'代表空节点)：

#include 
#include using namespace std;typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{char data;Position lChild, rChild;
};BTree CreateBTree(BTree bt, bool isRoot)
{char ch;if (isRoot)printf("Root: ");fflush(stdin);         /* 清空缓存区 */scanf("%c", &ch);fflush(stdin);if (ch != '#'){isRoot = false;bt = new BTNode;bt->data = ch;  bt->lChild = NULL;bt->rChild = NULL;printf("%c's left child is: ", bt->data);bt->lChild = CreateBTree(bt->lChild, isRoot);printf("%c's right child is: ", bt->data);bt->rChild = CreateBTree(bt->rChild, isRoot);}return bt;
}int main()
{BTree bt;bt = CreateBTree(bt, true);LevelOrderTraversal(bt);        /* 层序遍历 */return 0;
}

2.根据先序序列 

 输入序列ABDH##I##E##CF#J##G##（#表示空），则会建立如下图所示的二叉树

BTree CreateBTree()
{BTree bt = NULL;char ch;scanf("%c", &ch);if (ch != '#'){bt = new BTNode;bt->data = ch;bt->lChild = CreateBTree();bt->rChild = CreateBTree();}return bt;
}

3.根据中序序列和后序序列

一棵二叉树的中序序列为：ABCEFGHD，后序序列为: ABFHGEDC。建立的二叉树如下图：

/*
通过中序序列和后序序列建树，然后先序遍历输出
输入（第一行为中序，第二行为后序）：
ABCEFGHD
ABFHGEDC
输出：
CBADEGFH
*/
#include 
#include using namespace std;const int N = 1010;typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{char data;Position lChild, rChild;
};BTree CreateBTree(char inOd[], char postOd[], int n);
void PreOrder(BTree bt);int main()
{char inOd[N], postOd[N];  /* 中序序列与后序序列 */int n = 0;char ch;while ((ch = getchar()) && ch != '\n')inOd[n++] = ch;n = 0;while ((ch = getchar()) && ch != '\n')postOd[n++] = ch;BTree bt = CreateBTree(inOd, postOd, n);PreOrder(bt);printf("\n");return 0;
}BTree CreateBTree(char inOd[], char postOd[], int n)
{if (n == 0)return NULL;BTree btRoot = new BTNode;btRoot->data = postOd[n-1];     //后序序列最后一个元素一定是根节点char lInOd[N], rInOd[N];char lPostOd[N], rPostOd[N];int n1, n2;n1 = n2 = 0;//根据根节点将中序序列分为左子树和右子树for (int i = 0; i < n; i++){if (i <= n1 && inOd[i] != btRoot->data)lInOd[n1++] = inOd[i];else if (inOd[i] != postOd[n-1])rInOd[n2++] = inOd[i];}//根据一个树的后序序列的长度等于中序序列且后序遍历是先左子树再右子树//将后序序列分为左子树和右子树int m1, m2;m1 = m2 = 0;for (int i = 0; i < n-1; i++){if (i < n1)lPostOd[m1++] = postOd[i];elserPostOd[m2++] = postOd[i];}btRoot->lChild = CreateBTree(lInOd, lPostOd, n1);btRoot->rChild = CreateBTree(rInOd, rPostOd, n2);return btRoot;
}void PreOrder(BTree bt)
{if (bt != NULL){printf("%c", bt->data);PreOrder(bt->lChild);PreOrder(bt->rChild);}
}

4.根据不完整的先序，中序，后序序列 

         一棵二叉树的先序、中序和后序序列分别如下，其中一部分未显示出来，试编程求出空格处的内容。

      先序：_B_F_ICEH_G

      中序：D_KFIA_EJC_

      后序：_K_FBHJ_G_A

        事实上，上述例子的核心思想还是方式三中先找到根节点，再分为左右子树，然后递归进行。区别是这里不能唯一的根据先序或后序来确定根节点，故需要判断当前是先序序列还是后序序列可以得到根节点，所以函数实现需要传递先序中序后序3种序列。而此题还有一个隐含的条件，就是当先序和后序都不能得到根节点时，中序序列存在且只存在一个'_'，而且'_'就是根节点所在位置。这样分析之后代码就比较好实现了。代码如下：

/*
一棵二叉树的先序、中序和后序序列分别如下，其中一部分未显示出来，
试根据三个不完整的序列建树，然后依次输出先，中，后序的完整序列。
输入：
_B_F_ICEH_G
D_KFIA_EJC_
_K_FBHJ_G_A
输出：
ABDFKICEHJG
DBKFIAHEJCG
DKIFBHJEGCA*/#include 
#include using namespace std;const int N = 1010;typedef struct BTNode *Position;
typedef Position BTree;
struct BTNode
{char data;Position lChild, rChild;
};BTree CreateBTree(char preOd[], char inOd[], char postOd[], int n);
void PreOrder(BTree bt);
void InOrder(BTree bt);
void PostOrder(BTree bt);int main()
{char preOd[N], inOd[N], postOd[N];int n = 0;char ch;while ((ch = getchar()) && ch != '\n')preOd[n++] = ch;n = 0;while ((ch = getchar()) && ch != '\n')inOd[n++] = ch;n = 0;while ((ch = getchar()) && ch != '\n')postOd[n++] = ch;BTree bt = CreateBTree(preOd, inOd, postOd, n);PreOrder(bt);printf("\n");InOrder(bt);printf("\n");PostOrder(bt);printf("\n");return 0;
}BTree CreateBTree(char preOd[], char inOd[], char postOd[], int n)
{if (n == 0)return NULL;BTree btRoot = new BTNode;if (n == 1){if (preOd[0] != '_')btRoot->data = preOd[0];else if (inOd[0] != '_')btRoot->data = inOd[0];else if (postOd[0] != '_')btRoot->data = postOd[0];else{printf("Input error!\n");exit(0);}btRoot->lChild = NULL;btRoot->rChild = NULL;return btRoot;}if (postOd[n-1] != '_')btRoot->data = postOd[n-1];     //后序序列最后一个元素一定是根节点else if (preOd[0] != '_')btRoot->data = preOd[0];else{printf("Input Error!\n");exit(0);}char lPreOd[N], rPreOd[N];char lInOd[N], rInOd[N];char lPostOd[N], rPostOd[N];int n1, n2;n1 = n2 = 0;//根据根节点将中序序列分为左子树和右子树int flag = 0;   //判断根节点是否在中序序列中for (int i = 0; i < n; i++){if (inOd[i] == btRoot->data){flag = 1;break;}}if (flag == 1)  //如果根节点存在，按根节点划分{for (int i = 0; i < n; i++){if (i <= n1 && inOd[i] != btRoot->data)lInOd[n1++] = inOd[i];else if (inOd[i] != btRoot->data)rInOd[n2++] = inOd[i];}}else        //如果根节点不存在，按'_'划分{for (int i = 0; i < n; i++){if (i <= n1 && inOd[i] != '_')lInOd[n1++] = inOd[i];else if (inOd[i] != '_')rInOd[n2++] = inOd[i];}}//根据一个树的后序序列的长度等于中序序列且后序遍历是先左子树再右子树//将后序序列分为左子树和右子树int m1, m2;m1 = m2 = 0;for (int i = 0; i < n-1; i++){if (i < n1)lPostOd[m1++] = postOd[i];elserPostOd[m2++] = postOd[i];}//根据一个树的先序序列的长度等于中序序列且先序遍历是除根节点外也是先左子树再右子树//将先序序列分为左子树和右子树m1 = m2 = 0;for (int i = 1; i < n; i++){if (i < n1 + 1)lPreOd[m1++] = preOd[i];elserPreOd[m2++] = preOd[i];}btRoot->lChild = CreateBTree(lPreOd, lInOd, lPostOd, n1);btRoot->rChild = CreateBTree(rPreOd, rInOd, rPostOd, n2);return btRoot;
}void PreOrder(BTree bt)
{if (bt != NULL){printf("%c", bt->data);PreOrder(bt->lChild);PreOrder(bt->rChild);}
}void InOrder(BTree bt)
{if (bt != NULL){InOrder(bt->lChild);printf("%c", bt->data);InOrder(bt->rChild);}
}void PostOrder(BTree bt)
{if (bt != NULL){PostOrder(bt->lChild);PostOrder(bt->rChild);printf("%c", bt->data);}
}

线索二叉树

线索二叉树原理 

          将指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树。

        对二叉树进行遍历之后，让其结点中的空指针域指向该结点的前驱或后继。其实线索二叉树，等于是把一棵二叉树转变成了一个双向链表，这样就为我们的插入删除结点、查找某个结点都带来了方便。对二叉树以某种次序遍历使其变为线索二叉树的过程称做是线索化。

        我们在决定lchild是指向左孩子还是前驱，rchild是指向右孩子还是后继上是需要区分标志的。在每个结点再增设两个标志域ltag和rtag，ltag和rtag只是存放0或1数字的布尔型变量，其占用的内存空间要小于像lchild和rchild的指针变量。

线索二叉树结构的实现

/* 二叉树的二叉线索存储结构定义 */
typedef char TElemType;
typedef enum {Link,Thread} PointerTag;	/* Link=0表示指向左右孩子指针, *//* Thread=1表示指向前驱或后继的线索 */
typedef  struct BiThrNode				/* 二叉线索存储结点结构 */
{TElemType data;						/* 结点数据 */struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */PointerTag LTag;PointerTag RTag;					/* 左右标志 */
} BiThrNode, *BiThrTree;

        线索化的过程就是在遍历的过程中修改空指针的过程。 中序遍历线索化的递归函数代码如下：

BiThrTree pre; 					/* 全局变量,始终指向刚刚访问过的结点 */
/* 中序遍历进行中序线索化 */
void InThreading(BiThrTree 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; 					/* 保持pre指向p的前驱 */InThreading(p->rchild); /* 递归右子树线索化 */}
}

        代码中除高亮代码以外，和二叉树中序遍历的递归代码几乎完全一样。只不过将本是打印结点的功能改成了线索化的功能。中间高亮部分代码是做了这样的—些事:

        if(!p->lchild)表示如果某结点的左指针域为空，因为其前驱结点刚刚访问过，赋值给了pre，所以可以将pre赋值给p->lchild，并修改p->LTag=Thread（也就是定义为1）以完成前驱结点的线索化。后继就要稍稍麻烦一些，因为此时p结点的后继还没有访问到，因此只能对它的前驱结点pre的右指针rchild做判断，if(!pre->rchild)表示如果为空，则p就是pre的后继，于是pre->rchild=p，并设置pre->RTag=Thread，完成后继结点的线索化。完成前驱和后继的判断后，将当前的结点p赋值给pre，以便下一次使用。

/* T指向头结点，头结点左链lchild指向根结点，头结点右链rchild指向中序遍历的最后一个结点。
中序遍历二叉线索链表表示的二叉树T */
Status InOrderTraverse_Thr(BiThrTree T)
{BiThrTree 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;
}

        在实际问题中,如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择。