第五章学习了二叉树: 每个结点至多只有两颗子树, 且子树有左右之分.
二叉树的遍历: 几乎所有操作建立在遍历的基础上, 利用递归完成二叉树前 (根) 序, 中 (根) 序, 后 (根) 序遍历.
- void PreOrderTraverse(BiTree T)
- {
- If( T )// 若二叉树非空
- {
- cout<<T->data;// 访问根结点
- PreOrderTraverse( T->lchild );// 先序遍历左子树
- PreOrderTraverse( T->rchild );// 先序遍历左子树
- }
- View Code// 先序
- void InOrderTraverse(BiTree T)
- {
- If( T )// 若二叉树非空
- {
- InOrderTraverse( T->lchild );// 中序遍历左子树
- cout<<T->data;// 访问根结点
- InOrderTraverse( T->rchild );// 中序遍历左子树
- }
- View Code// 中序
- void PostOrderTraverse(BiTree T)
- {
- If(T)// 若二叉树非空
- {
- PostOrderTraverse( T->lchild );// 后序遍历左子树
- PostOrderTraverse( T->rchild );// 后序遍历左子树
- cout<<T->data;// 访问根结点
- }
- View Code// 后序
/*typedef struct{
char name;
int lch;
int rch;
}node;*/ 二叉树的定义
- void levelOrderTraverse(node t[], int x)
- {// 层次遍历 t[x]为根结点的树 t
- int tmp;
- queue<int> q;
- q.push(x); // 根结点所在下标入栈
- while(!q.empty()){
- tmp = q.front();
- q.pop();
- if(tmp!=-1){
- cout << t[tmp].name << " ";
- q.push(t[tmp].lch);
- q.push(t[tmp].rch);
- }
- }
- }
- View Code// 利用队列层次遍历
其次我们了解了建立哈夫曼树原理, 为之后的算法打基础.
树的遍历还需要熟悉, 并且要针对不同问题进行改进. 打代码能力, 逻辑思维能力继续加强.
第五章小结
来源: http://www.bubuko.com/infodetail-3046912.html