【数据结构】遍历二叉树
- 遍历二叉树的算法描述（递归定义）
先序遍历
若二叉树为空，则空操作；
否则
（1）访问根节点
（2）先序遍历左子树
（3）先序遍历右子树
中序遍历
若二叉树为空，则空操作；
否则
（1）中序遍历左子树
（2）访问根节点
（3）中序遍历右子树
后序遍历
若二叉树为空，则空操作；
否则
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根节点
- 根据遍历序列确定二叉树
- 若二叉树中各结点的值均不同，则二叉树的先序、中序、后序序列都是唯一的
- 由二叉树的先序序列和中序序列，或由后序序列和中序序列可以唯一确定一棵二叉树
由先序序列和中序序列确定二叉树：
先序序列先访问的是根节点，由此确定二叉树的根节点和左右子树，然后重复此过程可递归的找到所有的左右子树和根节点
由后序序列和中序序列确定二叉树：
后续遍历最后访问的是根节点，其余同理
- 遍历算法实现
递归实现
先序遍历
Status PreOrderTraverse(BiTree T){if(t==NULL)return OK;else{printf("%d", T->data);//访问根节点PreOrderTraverse(T->lchild);//递归遍历左子树PreOrderTraverse(T->rchild);//递归遍历右子树}
}
中序遍历
Status InOrderTraverse(BiTree T){if(t==NULL)return OK;else{InOrderTraverse(T->lchild);//递归遍历左子树printf("%d", T->data);//访问根节点InOrderTraverse(T->rchild);//递归遍历右子树}
}
后序遍历
Status PostOrderTraverse(BiTree T){if(t==NULL)return OK;else{PostOrderTraverse(T->lchild);//递归遍历左子树PostOrderTraverse(T->rchild);//递归遍历右子树printf("%d", T->data);//访问根节点}
}
非递归实现
Status InOderTravese(BiTree T){BiTree p,q;InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}else{Pop(S,q);printf("%c", q->data);p=q->rchild;}}return OK;
}
- 二叉树的层次遍历
对于一棵二叉树，从根节点开始，按从上到下，从左到右的顺序访问每个结点
设计思路：使用一个队列
1.将根节点进队
2.队不为空时，出队结点p，访问它
1.若它右左孩子，将左孩子进队
2.若它有右孩子，将右孩子进队
使用循环队列
typedef struct{BTNode data[MaxSize];int front,rear; //队头和队尾指针
}SqQueue;//循环队列
void LevelOrder(BTNode *b){BTNode *p;SqQueue *qu;InitQueue(qu); //初始化队列enQueue(qu, b); //根节点进队while(!QueueEmpty(qu)){deQueue(qu, p); //出队结点pprintf("%c", p->data); //访问结点pif(p->lchild!=NULL) //左孩子不为空则进队enQueue(qu, p->lchild);if(p->rchild!=NULL) //右孩子不为空则进队enQueue(qu, p->rchild);}
}
- 二叉树的建立
按先序遍历序列建立二叉树的二叉链表
// 构造二叉树（前序遍历，'#'表示空节点）
Status CreateBiTree(BiTree &T){cin>>ch;if(ch=="#")T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch; //生成根节点CreateBiTree(T->lchild); //构造左子树CreateBiTree(T->rchild); //构造右子树}return OK;
}
- 复制二叉树
算法描述
如果是空树，递归结束；
否则，申请新结点空间，复制根节点
递归复制左子树
递归复制右子树
int Copy(BiTree T, BiTree &NewT){if(T==NULL){ //如果是空树，返回0NewT = NULL;return 0;}else{NewT=new BiTree;NewT->data=T->data;Copy(T->lchild, NewT->lchild);Copy(T->rchild, NewT->rchild);}
}
- 计算二叉树的深度
算法思路
如果是空树，则深度为0
否则，递归计算左子树的深度m，递归计算右子树的深度n，二叉树深度为max(m,n)+1
int Depth(BiTree T){if(T==NULL)return 0;else{m=Depth(T->lchild);n=Depth(T->rchild);return m>n?m+1:n+1;}
}
- 计算二叉树结点总数
算法描述
如果是空树，则结点个数为0
否则，结点个数为左子树的结点个数+右子树的结点个数再＋1
int NodeCount(BiTree T){if(T==NULL)return 0;elsereturn NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}
- 计算叶子结点数
算法描述
如果是空树，则叶子结点个数为0
否则，叶子结点个数为左子树的叶子结点个数+右子树的叶子结点个数
int LeafCount(BiTree T){if(T==NULL)return 0;if(T->lchild==NULL&&T->rchild==NULL)return 1;elsereturn LeafCount(T->lchild)+LeafCount(T->rchild);
}