009-树的遍历和创建、二叉线索树、霍夫曼树
本帖最后由 moc 于 2018-9-30 21:32 编辑1、树的遍历
二叉树有根、左子树、右子树构成，定义为D、L、R。
DLR组合可以定义6种遍历方案：LDR 、LRD 、DLR、DRL 、RDL 、RLD .
一般限定先左后右：于是有三种遍历方案：
DLR=>先(根)序遍历
LDR=>中(根)序遍历
LRD=>后(根)序遍历
先序遍历：ABCDEFGH
中序遍历：BDCEAFHG
后序遍历：DECBHGFA
由于树本身就是一种递归结构，所以采用递归方式遍历树最合适；
先序遍历：
void preOrder(BiTNode *root)
{
if (root == NULL)
{
return;
}
// 遍历根
printf("%d", root->data);
// 遍历左子树
preOrder(root->lchild);
// 遍历右子树
preOrder(root->rchild);
}
中序遍历：
void inOrder(BiTNode *root)
{
if (root == NULL)
{
return;
}
// 遍历左子树
inOrder(root->lchild);
// 遍历根
printf("%d", root->data);
// 遍历右子树
inOrder(root->rchild);
}
后序遍历：
void postOrder(BiTNode *root)
{
if (root == NULL)
{
return;
}
// 遍历左子树
postOrder(root->lchild);
// 遍历右子树
postOrder(root->rchild);
// 遍历根
printf("%d", root->data);
}
分析： 上面三种遍历方法，如果将printf()语句去掉，三种算法完全相同，所以这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。
树的非递归中序遍历：
利用栈实现中序遍历的先走到的后访问，后走到的先访问。
算法步骤：
步骤1： 如果结点有左子树，该结点入栈；
如果结点没有右子树，访问该结点；
步骤2： 如果结点有右子树，重复步骤1；
如果结点没有右子树（结点访问完毕），根据栈顶指示回退，访问栈顶元素，并访问右子树，重复步骤1
如果栈为空，表示遍历结束。
注意： 入栈的结点其本身和其右子树没有被访问。
// 借助于栈结构
BiTNode* goLeft(BiTNode* t, stack<BiTNode*> &s)
{
if (!t)
{
return NULL;
}
while (t->lchild != NULL)
{
s.push(t);
t = t->lchild;
}
return t;
}
void inOrder2(BiTNode* tree)
{
stack<BiTNode*> st;
BiTNode *tmp;
if (tree == NULL)
{
return;
}
tmp = goLeft(tree, st);
while (tmp)
{
printf("%d ", tmp->data);
if (tmp->rchild != NULL)
{
tmp = goLeft(tmp->rchild, st);
}
else if (tmp->rchild == NULL && !st.empty())
{
tmp = st.top();
st.pop();
}
else
{
tmp = NULL;
}
}
}
2、二叉树的创建
1. #法
// #号法按照给定的先序序列创建二叉树
BiTNode* CreatBiTree()
{
BiTNode *node = NULL;
char h;
scanf("%c", &h);
if (h == '#')
{
return NULL;
}
else
{
node = (BiTNode*)malloc(sizeof(BiTNode));
if (node == NULL)
{
return NULL;
}
node->data = h;
node->lchild = CreatBiTree(); // 递归创建左子树
node->rchild = CreatBiTree(); // 递归创建右子树
return node;
}
}
2. 先序+中序 中序+后序
通过先序遍历和中序遍历结构创建二叉树，也可以通过中序遍历和后序遍历结构创建二叉树。
但是不能通过先序和后序遍历创建二叉树。
3、二叉线索树
普通二叉树只能找到结点的左右孩子信息，而该结点的直接前驱和直接后继只能在遍历过程中获得；若可以将遍历后对应的有关前驱和后继预存起来就可以“顺藤摸瓜”而遍历树。
实质：把二叉树按照中序遍历的结果存在链表里面。
待续...
4、霍夫曼树
树的帯权路径长度，组建一个网络，耗费最小WPL(帯权路劲长度)。
霍夫曼树的建立：
1. 给定 n 个数值（v1, v2, v3, ..., vn）;
2. 根据这 n个数值构造二叉树集合 F = (T1, T2, T3 ... Tn),其中 Ti 的数据域为 vi ,左右子树为空；
3. 在 F 中选择两颗根结点最小的树作为左右子树构造一颗新的二叉树，这颗新的二叉树的根结点中的值为左右子树根结点值的和；
4. 在 F 中删除这两颗子树，并将构造的新的二叉树加入 F 中；
5. 重复 3 和 4 步骤，直到只剩下最后一棵树为止，这棵树就是霍夫曼树。
结论： 霍夫曼树是一种特殊的二叉树；
霍夫曼树应用于信息编码和数据压缩领域；
霍夫曼树是现代压缩算法的基础。
页:
[1]