C语言二叉树及遍历
二叉树的定义
合,该集合或者为空,或者是由一个根结点加
上两棵分别称为左子树和右子树的、互不相交
的二叉树组成。
特殊二叉树
证明:假设二叉树中度1的结点有 n1个且总结点为 n个,则:
n = n0 + n1 + n2
假设二叉树中连接父结点与子结点间的边为e条,则:
e = n1 + 2n2 = n – 1
所以:
n0=n2+1。
证明:假设这 n 个结点组成的完全二叉树高度为 k ,则:
2k-1-1 < n ≤ 2k-1
因为 n 为整数,所以:
2k-1 ≤ n < 2k
取对数:
k-1 ≤ log2n < k
因为k为整数,所以:
k= log2n + 1
• 如果如果 i = 1 ,则结点i是二叉树的根
• 如果如果 i > 1 ,则其双亲结点为 i/2
• 如果如果 2i <= n ,则结点 i 的左孩子为2i
• 如果如果 2i > n ,则结点 i无左孩子
• 如果如果 2i+1 <= n ,则结点 i 的右孩子为 2i+1
• 如果如果 2i+1 > n ,则结点 i无右孩子
首先,我们看看前序、中序、后序遍历的特性:
前序遍历:
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树
中序遍历:
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
后序遍历:
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点
一、已知前序、中序遍历,求后序遍历
例:
前序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
画树求法:
第一步,根据前序遍历的特点,我们知道根结点为G
第二步,观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树,G右侧的HMZ必然是root的右子树。
第三步,观察左子树ADEF,左子树的中的根节点必然是大树的root的leftchild。在前序遍历中,大树的root的leftchild位于root之后,所以左子树的根节点为D。
第四步,同样的道理,root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中,一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树,并且遍历的左子树的第一个节点就是左子树的根节点。同理,遍历的右子树的第一个节点就是右子树的根节点。
第五步,观察发现,上面的过程是递归的。先找到当前树的根节点,然后划分为左子树,右子树,然后进入左子树重复上面的过程,然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下:
1 确定根,确定左子树,确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
那么,我们可以画出这个二叉树的形状:
那么,根据后序的遍历规则,我们可以知道,后序遍历顺序为:AEFDHZMG
#ifndef __BTREE_H__
#define __BTREE_H__
#define BLEFT 0 // 表示插入二叉树的左边
#define BRIGHT 1 // 表示插入二叉树的右边
#define TRUE 1
#define FALSE 0
typedef char BTreeData;
// 二叉树的结点
typedef struct _btreeNode
{
BTreeData data;
struct _btreeNode *lchild; // 指向左孩子结点的指针
struct _btreeNode *rchild; // 指向右孩子结点的指针
}BTreeNode;
// 二叉树
typedef struct _btree
{
BTreeNode *root; // 指向二叉树的根节点
int count; // 记录二叉树结点的个数
}BTree;
typedef void (*Print_BTree)(BTreeNode*);
// 创建一棵二叉树
BTree *Create_BTree();
// pos 走的路径 值类似 110(左右右) 011 (右右左)
// count 代表走的步数
// flag 代表被替换的结点应该插入在新节点的位置,如果是BLEFT 表示插在左边,BRIGHT表示插在右边
int Btree_Insert(BTree *tree, BTreeData data, int pos, int count, int flag);
void Display (BTree* tree, Print_BTree pfunc);
int Delete (BTree *tree, int pos, int count);
int BTree_Height (BTree *);
int BTree_Degree (BTree *);
int BTree_Clear (BTree *);
int BTree_Destroy (BTree **);
// 前序遍历
void pre_order (BTreeNode *node);
void mid_order (BTreeNode *node);
void last_order (BTreeNode *node);
#endif // __BTREE_H__
#include "BTree.h"
#include <stdlib.h>
#include <stdio.h>
BTree *Create_BTree()
{
BTree *btree = (BTree*)malloc(sizeof(BTree)/sizeof(char));
if (btree == NULL)
return NULL;
btree->count = 0;
btree->root = NULL;
return btree;
}
int Btree_Insert(BTree *tree, BTreeData data, int pos, int count, int flag)
{
if (tree == NULL || (flag != BLEFT && flag != BRIGHT))
return FALSE;
BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode)/sizeof(char));
if (node == NULL)
return FALSE;
node->data = data;
node->lchild = NULL;
node->rchild = NULL;
// 找插入的位置
BTreeNode *parent = NULL;
BTreeNode *current = tree->root; // current 一开始指向根节点,根节点的父节点是空
int way; // 保存当前走的位置
while (count > 0 && current != NULL)
{
way = pos & 1; // 取出当前走的方向
pos = pos >> 1; // 移去走过的路线
// 因为当前位置就是走完以后的位置的父节点
parent = current;
if (way == BLEFT) // 往左走
current = current->lchild;
else
current = current->rchild;
count--;
}
// 把被替换掉的结点插入到新节点下面
if (flag == BLEFT)
node->lchild = current;
else
node->rchild = current;
// 把新节点插入到二叉树中,way保存了应该插入在父节点的左边还是右边
if (parent != NULL)
{
if (way == BLEFT)
parent->lchild = node;
else
parent->rchild = node;
}
else
{
tree->root = node; // 替换根节点
}
tree->count ++;
return TRUE;
}
void r_display(BTreeNode* node, Print_BTree pfunc,int gap)
{
int i;
if (node == NULL)
{
for (i = 0; i < gap; i++)
{
printf ("-");
}
printf ("\n");
return;
}
for (i = 0; i < gap; i++)
{
printf ("-");
}
// 打印结点
// printf ("%c\n", node->data);
pfunc (node);
if (node->lchild != NULL || node->rchild != NULL)
{
// 打印左孩子
r_display (node->lchild, pfunc, gap+4);
// 打印右孩子
r_display (node->rchild, pfunc, gap+4);
}
}
void Display (BTree* tree, Print_BTree pfunc)
{
if (tree == NULL)
return;
r_display(tree->root, pfunc, 0);
}
void r_delete (BTree *tree, BTreeNode* node)
{
if (node == NULL || tree == NULL)
return ;
// 先删除左孩子
r_delete (tree, node->lchild);
// 删除右孩子
r_delete (tree, node->rchild);
free (node);
tree->count --;
}
int Delete (BTree *tree, int pos, int count)
{
if (tree == NULL)
return FALSE;
// 找结点
BTreeNode* parent = NULL;
BTreeNode* current = tree->root;
int way;
while (count > 0 && current != NULL)
{
way = pos & 1;
pos = pos >> 1;
parent = current;
if (way == BLEFT)
current = current->lchild;
else
current = current->rchild;
count --;
}
if (parent != NULL)
{
if (way == BLEFT)
parent->lchild = NULL;
else
parent->rchild = NULL;
}
else
{
tree->root = NULL;
}
// 释放结点
r_delete (tree, current);
return TRUE;
}
int r_height (BTreeNode *node)
{
if (node == NULL)
return 0;
int lh = r_height (node->lchild);
int rh = r_height (node->rchild);
return (lh > rh ? lh+1 : rh+1);
}
int BTree_Height (BTree *tree)
{
if (tree == NULL)
return FALSE;
int ret = r_height(tree->root);
return ret;
}
int r_degree (BTreeNode * node)
{
if (node == NULL)
return 0;
int degree = 0;
if (node->lchild != NULL)
degree++;
if (node->rchild != NULL)
degree++;
if (degree == 1)
{
int ld = r_degree (node->lchild);
if (ld == 2)
return 2;
int rd = r_degree (node->rchild);
if (rd == 2)
return 2;
}
return degree;
}
int BTree_Degree (BTree *tree)
{
if (tree == NULL)
return FALSE;
int ret = r_degree(tree->root);
return ret;
}
int BTree_Clear (BTree *tree)
{
if (tree == NULL)
return FALSE;
Delete (tree, 0, 0); // 删除根节点
tree->root = NULL;
return TRUE;
}
int BTree_Destroy (BTree **tree)
{
if (tree == NULL)
return FALSE;
BTree_Clear(*tree);
free (*tree);
*tree = NULL;
return TRUE;
}
void pre_order (BTreeNode *node)
{
if (node == NULL)
return;
printf ("%4c", node->data);
pre_order (node->lchild);
pre_order (node->rchild);
}
void mid_order (BTreeNode *node)
{
if (node == NULL)
return;
mid_order (node->lchild);
printf ("%4c", node->data);
mid_order (node->rchild);
}
void last_order (BTreeNode *node)
{
if (node == NULL)
return;
last_order (node->lchild);
last_order (node->rchild);
printf ("%4c", node->data);
}
#include "BTree.h"
#include <stdio.h>
void printA(BTreeNode *node)
{
printf ("%c\n", node->data);
}
int main()
{
BTree *btree = Create_BTree();
if (btree == NULL)
{
printf ("创建失败\n");
}
else
{
printf ("创建成功\n");
}
Btree_Insert(btree, 'A', 0, 0, 0);
Btree_Insert(btree, 'B', 0, 1, 0);
Btree_Insert(btree, 'C', 1, 1, 0);
Btree_Insert(btree, 'D', 0, 2, 0);
Btree_Insert(btree, 'E', 2, 2, 0);
Btree_Insert(btree, 'F', 0, 3, 0);
Btree_Insert(btree, 'G', 4, 3, 0);
Btree_Insert(btree, 'H', 3, 2, 0);
Display(btree, printA);
printf ("前序遍历:\n");
pre_order (btree->root);
printf ("\n");
printf ("中序遍历:\n");
mid_order (btree->root);
printf ("\n");
printf ("后序遍历:\n");
last_order (btree->root);
printf ("\n");
#if 0
Delete(btree, 0, 1);
printf ("删除后--------------\n");
Display(btree, printA);
printf ("高度: %d\n", BTree_Height(btree));
printf ("度 : %d\n", BTree_Degree(btree));
printf ("清空后--------------\n");
BTree_Clear(btree);
Display(btree, printA);
BTree_Destroy(&btree);
//btree = NULL;
#endif
return 0;
}