人的一生犹如负重致远，不可急躁。 以不自由为常事，则不觉不足。 心生欲望时，应回顾贫困之日。 心怀宽恕，视怒如敌，则能无视长久。 只知胜而不知敗，必害其身。 责人不如责己，不及胜于过之。
分类： IT职场
2017-03-14 13:37:14
二叉树
1 简介
树形结构是一类重要的非线性数据结构，其中以树和二叉树最为常用。每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。
2 特性
1、非空二叉树的第n层上至多有2^(n-1)个元素。
2、深度为h的二叉树至多有2^h-1个结点。
3、满二叉树：
所有叶子节点都在同一层次，且非叶子结点的度数为2。
在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。
4、完全二叉树：
除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。
对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。
如下图：
3 数据存储结构
二叉树的链式存储结构是一类重要的数据结构。
代码如下：
//二叉树结点
typedef struct BiTreeNode{
//数据
char data;
//左右孩子指针
struct BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;
4 二叉树遍历
遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。
1、前序遍历：根->左->右
2、中序遍历：左->根->右
3、后序遍历：左->右->根
访问函数代码：
void Visit(BiTree T){
if(T->data != '#'){
printf("%c ",T->data);
}
}
4.1 递归遍历
访问函数代码如下：
//先序遍历
void PreOrder(BiTree T){
if(T != NULL){
//访问根节点
Visit(T);
//访问左子结点
PreOrder(T->lchild);
//访问右子结点
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree T){
if(T != NULL){
//访问左子结点
InOrder(T->lchild);
//访问根节点
Visit(T);
//访问右子结点
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(BiTree T){
if(T != NULL){
//访问左子结点
PostOrder(T->lchild);
//访问右子结点
PostOrder(T->rchild);
//访问根节点
Visit(T);
}
}
4.2 非递归遍历
4.2.1 先序遍历
访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
代码如下：
void PreOrder(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
//栈不空或者p不空时循环
while(p || !stack.empty()){
if(p != NULL){
//存入栈中
stack.push(p);
//访问根节点
Visit(p);
//遍历左子树
p = p->lchild;
}
else{
//退栈
p = stack.top();
stack.pop();
//访问右子树
p = p->rchild;
}
}
}
4.2.2 中序遍历
中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
void InOrder (BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
//栈不空或者p不空时循环
while(p || !stack.empty()){
if(p != NULL){
//存入栈中
stack.push(p);
//遍历左子树
p = p->lchild;
}
else{
//退栈，访问根节点
p = stack.top();
Visit(p);
stack.pop();
//访问右子树
p = p->rchild;
}
}
}
4.2.3 后序遍历
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
//后序遍历(非递归)
typedef struct BiTreeNodeLast{
BiTree biTree;
char tag;
} BiTreeNodeLast,*BiTreeLast;
void LastOrder(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
BiTreePost BT;
//栈不空或者p不空时循环
while(p != NULL || !stack.empty()){
//遍历左子树
while(p != NULL){
BT = (BiTreeLast)malloc(sizeof(BiTreeNodeLast));
BT->biTree = p;
//访问过左子树
BT->tag = 'L';
stack.push(BT);
p = p->lchild;
}
//左右子树访问完毕访问根节点
while(!stack.empty() && (stack.top())->tag == 'R'){
BT = stack.top();
//退栈
stack.pop();
BT->biTree;
Visit(BT->biTree);
}
//遍历右子树
if(!stack.empty()){
BT = stack.top();
//访问过右子树
BT->tag = 'R';
p = BT->biTree;
p = p->rchild;
}
}
}
4.3 层次遍历
按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。
代码如下：
void LevelOrder(BiTree T){
BiTree p = T;
//队列
queue queue;
//根节点入队
queue.push(p);
//队列不空循环
while(!queue.empty()){
//对头元素出队
p = queue.front();
//访问p指向的结点
Visit(p);
//退出队列
queue.pop();
//左子树不空，将左子树入队
if(p->lchild != NULL){
queue.push(p->lchild);
}
//右子树不空，将右子树入队
if(p->rchild != NULL){
queue.push(p->rchild);
}
}
}
4.4 树高度
int HeightTree(BiTree t){
int h,left,right;
if(!t){
return 0;
}
left = HeightTree(t->lchild);
right = HeightTree(t->rchild);
h = (left>right?left:right)+1;
return h;
}
