二叉树,顾名思义,是有每个结点有两个分支的树,我们将结点称为根节点,将它的两个分支称为它的左子树、右子树,所以我们用以下结构来定义二叉树的结构。
typedef char TreeNodeType;
typedef struct TreeNode//树的结点
{
TreeNodeType data;//数据
struct TreeNode* lchild;//左子树
struct TreeNode* rchild;//右子树
}TreeNode;
树的基本实现:
void TreeInit(TreeNode** proot)//初始化
{
if(proot == NULL)//非法输入
return;
*proot = NULL;
return;
}
TreeNode* CreateTreeNode(TreeNodeType value)//创造一个新结点
{
TreeNode* new_node = (TreeNode*)malloc(sizeof(TreeNode));
new_node->data = value;
new_node->lchild = NULL;
new_node->rchild = NULL;
return new_node;
}
void DestroyTreeNode(TreeNode* node)//销毁结点
{
free(node);
return;
}
对于二叉树,最最基本的操作就是对二叉树进行遍历。而二叉树的遍历方式我们有先序遍历、中序遍历、后序遍历、层次遍历这几种,且遍历二叉树最重要的就是做到“不重不漏”。
1. 先序遍历(先访问根节点,再访问左子树,最后访问右子树)
如图,即我们对图中二叉树进行了一个先序遍历。
(1)我们对整棵树的根节点进行访问,也就是图中的1即结点A;
(2)然后访问整棵树的左子树即2,对于2子树,我们再访问它的根节点也就是B,再访问它的左子树也就是3;
(3)我们可以看到3子树,只有根结点而无子树,所以我们访问了根结点D就可以返回到2树;
(4)返回到2树之后,按先序遍历的顺序接下来该访问2的右子树即4树;
(5)访问4树的根节点E,再访问它的左子树,因为它的左子树只有根结点G,所以我们访问完G就可以返回,而4树也无右子树,所以我们继续返回;
(6)上步最后我们应该返回到1树,去访问它的右子树5,对于5树先访问它的根节点C;
(7)访问完C后,应该访问C的左子树,但它左子树为空,所以我们直接访问右子树F;
(8)至此,该树已遍历完,所以先序遍历的结果是:A B D E G C F
整个过程,利用代码我们可以用递归实现,实现代码如下:
void TreePreOrder(TreeNode* root)//先序遍历
{//根左右
//树为空也是遍历结束的条件
if(root == NULL)//空树
{
printf("[%c] ",'#');
return;
}
//访问根结点
printf("[%c] ",root->data);
//递归访问左子树
TreePreOrder(root->lchild);
//递归访问右子树
TreePreOrder(root->rchild);
return;
}
2. 中序遍历(先访问左子树,再访问根节点,最后访问右子树)
中序遍历的思想与先序遍历一样,只是访问顺序改变了。针对上图的二叉树,我们进行中序访问:
1)首先访问1树的左子树2,对2树再访问左子树即3,3树无子树,所以访问根节点D,再返回到2树;
(2)此时,2树已访问完左子树,接下来访问根节点B,再到右子树4树;
(3)对4树,先访问它的左子树,左子树仅一个单节点,所以直接访问G,再返回访问E,4树无右子树,所以返回到2树,2树也访问完了,再继续返回到1树;
(4)1树该访问根节点即A,再访问1树的右子树即5树;
(5)对5树再按中序遍历访问,即C再F;
(6)至此,中序遍历访问结束,结果是:D B G E A C F
利用递归实现,实现代码如下:
void TreeInOrder(TreeNode* root)//中序遍历
{//左根右
//树为空也是遍历结束的条件
if(root == NULL)//空树
return;
//递归访问左子树
TreeInOrder(root->lchild);
//访问根结点
printf("[%c] ",root->data);
//递归访问右子树
TreeInOrder(root->rchild);
return;
}
- 后序遍历(先访问左子树,再访问右子树,最后访问根节点)
(1)首先访问1的左子树2树,再访问2的左子树3,所以访问结点D,再返回到2树访问2的右子树4树;
(2)对4树,先访问左子树G,再访问右子树,因为右子树为空,所以访问根节点E,再返回到2树;
(3)此时该访问2树的根节点B,再返回到1树;
(4)此时该访问1树的右子树5树,对于5树先访问左子树为空,再访问右子树为F,最后访问根节点C,再返回1树;
(5)最后访问1树的根节点即A;
(6)至此,遍历结束结果为:D G E B F C A
利用递归实现代码如下:
void TreePostOrder(TreeNode* root)//后序遍历
{//左右根
//树为空也是遍历结束的条件
if(root == NULL)//空树
return;
//递归访问左子树
TreePostOrder(root->lchild);
//递归访问右子树
TreePostOrder(root->rchild);
//访问根结点
printf("[%c] ",root->data);
return;
}
4.层序遍历(从第一层,一层一层向下访问)
层序遍历很简单,大家应该都能很快地遍历出来:A B C D E F G
代码实现的思想:
(1)我们可以利用队列实现,首先将二叉树的根节点放入队列即入A;
(2)拿队首元素为当前元素并访问,访问完出队,同时将当前元素的左右子树即B、C入队(子树为空则不入队);
(3)重复(2)步骤,即访问B再入D、E;访问C再入F;
(4)直至队列为空,遍历结束
void TreeLevelOrder(TreeNode* root)//层序遍历
{//1.建一个队列,若根结点非空,先将根结点入队
//2.打印当前队列的首元素结点的data值,并将其出队
//3.若刚刚出队元素的左/右子树不为空,就将其入列,再重复23步骤,直至队列为空即遍历结束
//树空也作为遍历结束的条件
if(root == NULL)//空树
return;
SeqQueue queue;
SeqQueueInit(&queue);
SeqQueuePush(&queue,root);
while(1)
{
SeqQueueType front;
int ret = SeqQueueGetFront(&queue,&front);
//队首元素为空说明遍历结束
if(ret == 0)
break;
//访问当前元素结点,并打印其值
printf("[%c] ",front->data);
//将当前结点出队
SeqQueuePop(&queue);
//将当前结点的左右子树(若非空)则入队
if(front->lchild != NULL)
SeqQueuePush(&queue,front->lchild);
if(front->rchild != NULL)
SeqQueuePush(&queue,front->rchild);
}
printf("\n");
return;
}
其中,以上用到的队列相关代码如下:(具体队列相关操作的实现,大家都可以在这里找到点击打开链接,这里的代码只是稍作了修改而已)
typedef TreeNode* SeqQueueType;
typedef struct SeqQueue//整个队列的元素是从head到tail,
{ //由于出队是头删,所以前面可能会有空,所以当tail走到最后时,tail再指向0,只要size与MAX_SIZE不相等,就还有空间
SeqQueueType data[MAX_SIZE];
size_t head;//队列第一个元素下标
size_t tail;//队列最后一个元素的下标
size_t size;//用了多少个元素的空间
}SeqQueue;
因为这里,要向队列里存放的是子树结点的指针,所以这里稍微修改了,下面的基本操作代码还是没有什么变化的。
void SeqQueueInit(SeqQueue* q)//初始化
{
if(q == NULL)//非法操作
return;
q->size = 0;
q->head = 0;
q->tail = 0;
return;
}
void SeqQueueDestroy(SeqQueue* q)//销毁队列
{
if(q == NULL)
return;
q->size = 0;
q->head = 0;
q->tail = 0;
return;
}
void SeqQueuePush(SeqQueue* q,SeqQueueType value)//入队列(尾插)
{
if(q == NULL)
return;
if(q->size >= MAX_SIZE)//队列已满
return;
q->data[q->tail++] = value;
if(q->tail >= MAX_SIZE)//tail走到最后,就再指向头(只要size<MAX_SIZE)
q->tail = 0;
q->size++;
return;
}
void SeqQueuePop(SeqQueue* q)//出列队(头删)
{
if(q == NULL)//非法操作
return;
if(q->size == 0)//空队
return;
q->head++;
if(q->head >= MAX_SIZE)//别忘记!!!
q->head = 0;
q->size--;
return;
}
int SeqQueueGetFront(SeqQueue* q,SeqQueueType* value)//取队首元素
{
if(q == NULL)
return 0;
if(q->size == 0)
return 0;
*value = q->data[q->head];
return 1;
}
void SeqQueuePrint(SeqQueue* q,const char* msg)//打印
{
printf("[%s]\n",msg);
if(q == NULL)
return;
if(q->size == 0)//空队列
{
printf("空队\n");
return;
}
size_t i = q->head;
if(q->tail <= q->head)//tail在head前
{
for(; i<MAX_SIZE; ++i)
printf("[%c] ",q->data[i]);
for(i=0; i<q->tail; ++i)//q->tail指向最后一个元素的下一个位置
printf("[%c] ",q->data[i]);
}
else//tail在head后
{
for(i=q->head; i<q->tail; ++i)
printf("[%c] ",q->data[i]);
}
printf("\n");
return;
}
5.根据数组所给内容(包括空子树),构建一颗二叉树
TreeNode* _TreeCreate(TreeNodeType data[],size_t size,size_t* index,TreeNodeType null_node)//真正实现构建二叉树的代码
{
if(index == NULL)//非法输入
return NULL;
if(*index >= size)//访问数组越界
return NULL;
if(data[*index] == null_node)//当前是空子树
return NULL;
TreeNode* new_node = CreateTreeNode(data[*index]);//2.
++(*index);//3.
new_node->lchild = _TreeCreate(data,size,index,null_node);
++(*index);//4.
new_node->rchild = _TreeCreate(data,size,index,null_node);
return new_node;//返回当前子树的根结点
}
TreeNode* TreeCreate(TreeNodeType data[],size_t size,TreeNodeType null_node)//根据数组所给内容构建一颗二叉树
{//数组所给内容(这里给的是先序遍历结果)包括空子树,即参数null_node所代表的,第二个参数size表示树的大小
//1.index用来标记当前元素为数组的哪个元素的下标
//2.根据index所指内容创建一个结点
//3.先++index,然后递归构建新结点的左子树
//4.再++index,然后构建新结点的右子树
size_t index = 0;
return _TreeCreate(data,size,&index,null_node);
}
6.树的深拷贝
拷贝分为深拷贝、浅拷贝两种。浅拷贝是新建一个指针,将所要拷贝内容的空间的地址拿到放入指针;而深拷贝则是创建一块新内存,将想要的内容全部拷贝一份。
TreeNode* TreeClone(TreeNode* root)//树的深拷贝
{
if(root == NULL)//空树
return NULL;
//按先序来拷贝
TreeNode* new_node = CreateTreeNode(root->data);
new_node->lchild = TreeClone(root->lchild);
new_node->rchild = TreeClone(root->rchild);
return new_node;
}
7. 树的销毁
法一:
void TreeDestroy1(TreeNode** root)//树的销毁1
{//基于后序来遍历销毁,防止根结点销毁之后找不到子树,造成没有全部销毁
if(root == NULL)//非法输入
return;
if(*root == NULL)//空树
return;
TreeDestroy1(&((*root)->lchild));
TreeDestroy1(&((*root)->rchild));
DestroyTreeNode(*root);
*root = NULL;
return;
}
法二:
void TreeDestroy2(TreeNode** root)//树的销毁2
{//基于先序来遍历销毁,在销毁当前子树的根结点时,先保存左右子树,避免找不到而没删除
if(root == NULL)//非法输入
return;
if(*root == NULL)//空树
return;
TreeNode* lchild = (*root)->lchild;
TreeNode* rchild = (*root)->rchild;
DestroyTreeNode(*root);
TreeDestroy2(&lchild);
TreeDestroy2(&rchild);
*root = NULL;
return;
}
8. 求树的结点
法一:
void _TreeSize(TreeNode* root,size_t* size)//真正用来计算树的结点
{
if(root == NULL)//空树
return;
++(*size);
_TreeSize(root->lchild,size);
_TreeSize(root->rchild,size);
}
size_t TreeSize(TreeNode* root)//求树的结点(不计算空结点)
{//用一个计数器,依次遍历结点,不为空就加1
size_t size = 0;
_TreeSize(root,&size);
return size;
}
法二:
size_t TreeSize1(TreeNode* root)//求树的结点
{//根结点加左右子树的结点树
if(root == NULL)//空树
return 0;
return 1+TreeSize(root->lchild)+TreeSize(root->rchild);
}
9. 求树的叶子结点个数
size_t TreeLeafSize(TreeNode* root)//求叶子结点的个数
{//左子树的叶子结点和右子树的叶子结点的和
if(root == NULL)//空树
return 0;
//当前结点是叶子结点
if(root->lchild == NULL && root->rchild == NULL)
return 1;
//当前结点不是叶子结点
return TreeLeafSize(root->lchild) + TreeLeafSize(root->rchild);
}
10. 求树第K层结点个数
size_t TreeKlevelSize(TreeNode* root,int K)//求第K层结点的个数(这里从第一层开始数)
{//求树的第K层结点数即求树的第K-1层结点子树的第一层结点数之和
if(root == NULL || K < 1)//非法输入
return 0;
if(K == 1)
return 1;
return TreeKlevelSize(root->lchild,K-1)+TreeKlevelSize(root->rchild,K-1);
}
11.求树的高度
size_t TreeHeight(TreeNode* root)//求树的高度
{//根结点左右子树的高度较高者加1
if(root == NULL)
return 0;
//当前结点无子树
if(root->lchild==NULL && root->rchild==NULL)
return 1;
//当前结点有子树
size_t lchild = TreeHeight(root->lchild);
size_t rchild = TreeHeight(root->rchild);
return 1+(lchild > rchild ? lchild : rchild);
}
12.给定一个数值,返回对应结点的指针(假设树上结点值无重复)
TreeNode* TreeFind(TreeNode* root,TreeNodeType to_find)//查找结点
{//给出一个数值,求对应结点的指针(假设无重复的数值结点)
if(root == NULL)
return NULL;
//按照先序遍历访问
if(root->data == to_find)
return root;
TreeNode* lresult = TreeFind(root->lchild,to_find);
TreeNode* rresult = TreeFind(root->rchild,to_find);
return lresult != NULL ? lresult :rresult;
}
13.给定一个结点,返回它的父结点
TreeNode* Parent(TreeNode* root,TreeNode* child)//求结点的父结点
{
if(root == NULL || child == NULL)//非法输入
return NULL;
//当前结点的左或右子树是输入参数孩子结点
if(root->lchild==child || root->rchild==child)
return root;
TreeNode* lresult = Parent(root->lchild,child);
TreeNode* rresult = Parent(root->rchild,child);
return lresult != NULL ? lresult : rresult;
}
14.给定一个结点,求它的左右子树
TreeNode* Lchild(TreeNode* root)//求当前结点的左子树
{
if(root == NULL)
return NULL;
return root->lchild;
}
TreeNode* Rchild(TreeNode* root)//求当前结点的右子树
{
if(root == NULL)
return NULL;
return root->rchild;
}
点击数:71