Wx::

二叉树

任一棵树的子树数最多为 2,即最多有 2 个分支


二叉链表存储结构

#define MAXSIZE 100

typedef char TElemType; // 树中元素暂为字符型

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;

性质

  • 第 i 层上至多有 2i-1 个节点(i≥1)

  • 深度为 k 的二叉树至多有 2k-1 个节点(k≥1)

  • 若其终端节点(无子树节点)数为 n0 ,度为 2 的节点数为 n2 ,则 n0 = n2 + 1

  • 具有 n 个节点的完全二叉树的深度为 ⌊log2n⌋ + 1

  • 对有 n 个节点的完全二叉树(深度为 ⌊log2n⌋ + 1 )的节点按层序编号,则对任意节点 i 有:

    • 若 i = 1,则 i 是二叉树的根,若 i > 1,则其双亲是节点 ⌊i/2⌋
    • 若 2i > n,则 i 无左孩子
    • 若 2i+1 > n,则无右孩子

相关算法

算法 6.1 - 二叉树的先序递归遍历

如果节点 T 存在,则访问 T 的数据,之后对 T 的左子树按此方式遍历,再对右子树遍历,知道该节点不存在时,直接返回

完整代码见 数据结构实验 - 6

Status PreOrderTraverse(BiTree T, Status (*visit)(TElemType)) {
    // 先序遍历
    if (T) {
    	if (visit(T->data) == OK) {
    	    if (PreOrderTraverse(T->lchild, visit)) {
    	    	if (PreOrderTraverse(T->rchild, visit)) {
    	    	    return OK;
    	    	}
    	    }
    	}
    	return ERROR;
    }
    else {
    	return OK;
    }
}

算法 6.2 - 二叉树的中序遍历

代码:-brev-

Status InOrderTraverse(BiTree T, Status(*visit)(TElemType)) {
    // 中序遍历
    if (T) {
    	if (InOrderTraverse(T->lchild, visit)) {
    	    if (visit(T->data)) {
    	    	if (InOrderTraverse(T->rchild, visit)) {
    	    	    return OK;
    	    	}
    	    }
    	    return ERROR;
    	}
    }
    else {
    	return OK;
    }
}

over


算法 6.3 - 二叉树的后序遍历

代码:-brev-

Status PostOrderTraverse(BiTree T, Status(*visit)(TElemType)) {
    // 后序遍历
    if (T) {
    	if (PostOrderTraverse(T->lchild, visit)) {
    	    if (PostOrderTraverse(T->rchild, visit)) {
    	    	if (visit(T->data)) {
    	    	    return OK;
    	    	}
    	    	return ERROR;
    	    }
    	}
    }
    else {
    	return OK;
    }
}

over


算法 6.4 - 二叉树的中序非递归遍历

模拟递归中栈的方式,将经过但未 visit 的节点先存入栈,再按序执行之后内容

用到了栈的相关应用,完整代码见 数据结构实验 - 7

Status InOrderTraverse(BiTree T, Status(*visit)(TElemType)) {
    SqStack S;
    SElemType e;
    InitStack(&S);
    if (T) {
    	Push(&S, T);
    	while (!StackEmpty(&S)) {
    	    while (GetTop(&S, &e) && e) {
    	    	Push(&S, e->lchild);
    	    }
    	    Pop(&S, &e);
    	    if (!StackEmpty(&S)) {
    	    	Pop(&S, &e);
    	    	if (!visit(e->data)) {
    	    	    return ERROR;
    	    	}
    	    	Push(&S, e->rchild);
    	    }
    	}
    }
    return OK;
}

算法 6.5 - 二叉树的先序遍历

原理和上述中序非递归遍历相同

代码:-brev-

Status PreOrderTraverse(BiTree T, Status(*visit)(TElemType)) {
    // 先序(原理和中序相似):
    SqStack S;
    SElemType e;
    InitStack(&S);
    if (T) {
    	Push(&S, T);
    	while (!StackEmpty(&S)) {
    	    while (GetTop(&S, &e) && e) {
    	    	if (!visit(e->data)) {
    	    	    return ERROR;
    	    	}
    	    	Push(&S, e->lchild);
    	    }
    	    Pop(&S, &e);
    	    if (!StackEmpty(&S)) {
    	    	Pop(&S, &e);
    	    	Push(&S, e->rchild);
    	    }
    	}
    }
    return OK;
}

over


算法 6.6 - 二叉树的后序遍历

代码:-brev-

Status PostOrderTraverse(BiTree T, Status(*visit)(TElemType)) {
    // 后序:
    SqStack S;
    SElemType p, r;
    Status i = 1;
    InitStack(&S);

    if (T) {
    	Push(&S, T);
    	while (!StackEmpty(&S)) {
    	    while (GetTop(&S, &p) && p) {
    	        Push(&S, p->lchild);
    	    }
    	    Pop(&S, &p);

    	    while ((i = GetTop(&S, &r)) && r->rchild == p) {
    	    	if (!visit(r->data)) {
    	    		return ERROR;
    	    	}
    	    	Pop(&S, &p);
    	    }
    	    if (i) {
    	    	Push(&S, r->rchild);
    	    }
    	}
    }
    return OK;
}

over


算法 6.7 - 二叉树的层序遍历

代码:-brev-

Status LevelOrderTraverse(BiTree T, Status(*visit)(TElemType)) {
    // 层序:
    SqQueue Q;
    QElemType e; // 临时接收出队的元素
    InitQueue(&Q);

    if (T) {
    	EnQueue(&Q, T);
    	while (!QueueEmpty(&Q)) {
    	    DeQueue(&Q, &e);
    	    if (!visit(e->data)) {
    	    	return ERROR;
    	    }
    	    if (e->lchild) EnQueue(&Q, e->lchild);
    	    if (e->rchild) EnQueue(&Q, e->rchild);
    	}
    	return OK;
    }
    else {
    	// 该二叉树为空
    	return ERROR;
    }
}

over


算法 6.8 - 二叉树的创建

以在命令行中运行并输入字符来创建为例

代码:-brev-

Status CreateBiTree(BiTree *T) {
    // 创建二叉树,先序输入各节点值,输入 “空格” 表示该节点不存在

    char ch = ' ';
    printf("\n请输入节点值:");
    scanf("%c", &ch);
    getchar(); // 吸收回车
    if (ch != ' ') {
    	*T = (BiTNode *)malloc(sizeof(BiTNode));
    	(*T)->data = ch;
    	CreateBiTree(&((*T)->lchild));
    	CreateBiTree(&((*T)->rchild));
    }
    else {
    	*T = NULL;
    }
    return OK;
}

over


算法 6.9 - Huffman 树编码

包括:

  • 由文本字符串获取每个字符权值
  • 由权值表进行 Huffman 编码
  • 对原始文本进行编码(包含压缩和非压缩)
  • 对 Huffman 码串进行解码为原始文本(包含压缩和非压缩解码);

完整代码见 数据结构实验 - 8


树和森林

向二叉树的转换

  • 树向二叉树转换:

    • 以树中节点的第一个子树作为二叉树中该节点的左孩子,树中节点的其他子树作为二叉树中该节点的左孩子的右子树、右子树的右子树、右子树的右子树...
    • :同等级兄弟向右依次连接,父子级(双亲和第一棵子树)向左依次连接
  • 森林向二叉树转换:

    • 将除第一棵树外的树根节点看做第一棵树根节点的兄弟,同上述转换方法进行转换即可

更多相关

330

评论(0

评论 取消
验证码:
搜索