tree.h
#pragma once
typedef char TreeNodeType;
typedef struct TreeNode {
TreeNodeType data;
struct TreeNode* lchild;
struct TreeNode* rchild;
} TreeNode;
void TreeInit(TreeNode** root); //初始化二叉树
void PreOrder(TreeNode* root); //递归先序遍历
void InOrder(TreeNode* root); 递归中序遍历
void PostOrder(TreeNode* root); 递归后序遍历
void LevelOrder(TreeNode* root); //层序遍历
TreeNode* _TreeCreate(TreeNodeType array[], size_t *index,size_t size, TreeNodeType null_node);
void TreeDestroy(TreeNode* root);
TreeNode* TreeClone(TreeNode* root); //二叉树的克隆
size_t TreeSize(TreeNode* root); //求节点个数
size_t TreeLeafSize(TreeNode* root); //求叶子节点个数
size_t TreeKLevelSize(TreeNode* root, int K); //第K层节点个数
size_t TreeHeight(TreeNode* root); //二叉树的高度
TreeNode* TreeFind(TreeNode* root, TreeNodeType to_find); //二叉树的查找
reeNode* LChild(TreeNode* node); //查找当前节点的左子树
TreeNode* RChild(TreeNode* node); //查找当前节点的右子树
TreeNode* Parent(TreeNode* root, TreeNode* node); //查找当前节点的父节点
void PreOrderByLoop(TreeNode* root); //非递归先序遍历
void InOrderByLoop(TreeNode* root); //非递归中序遍历
void PostOrderByLoop(TreeNode* root); //非递归后序遍历
void TreeMirror(TreeNode* root); //镜像二叉树
int IsCompleteTree(TreeNode* root);//判读是否为完全二叉树
tree.c
#include"seqstack.h"
#include<stdio.h>
#include"tree.h"
#include"linkqueue.h"
#include<stdlib.h>
void TreeInit(TreeNode** root)
{
if(root == NULL)
{
return;
}
*root = NULL;
}
void PreOrder(TreeNode* root)
{
if(root == NULL)
{
return;
}
printf("%c ",root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
void InOrder(TreeNode* root)
{
if(root == NULL)
{
return;
}
InOrder(root->lchild);
printf("%c ",root->data);
InOrder(root->rchild);
}
void PostOrder(TreeNode* root)
{
if(root == NULL)
{
return;
}
PostOrder(root->lchild);
PostOrder(root->rchild);
printf("%c ",root->data);
}
void LevelOrder(TreeNode* root)
{
if(root == NULL)
{
return;
}
LinkQueue queue;
LinkQueueInit(&queue);
LinkQueuePush(&queue,root);
while(1)
{
LinkQueueType top;
int ret = LinkQueueFront(&queue,&top);
if(ret == 0)
{
//取队首元素失败（队列为空）
break;
}
printf("%c ",top->data);
LinkQueuePop(&queue);
if(top->lchild != NULL)
{
LinkQueuePush(&queue,top->lchild);
}
if(top->rchild != NULL)
{
LinkQueuePush(&queue,top->rchild);
}
}
}
TreeNode* CreateNode(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);
}
TreeNode* _TreeCreate(TreeNodeType array[],size_t *index,size_t size,TreeNodeType null_node)
{
if(index == NULL)
{
return NULL;//error
}
if(*index >= size)
{
return NULL;//越界
}
if(array[*index] == null_node)
{
return NULL;//NULL
}
TreeNode* root = CreateNode(array[*index]);
++(*index);
root->lchild = _TreeCreate(array,index,size,null_node);
++(*index);
root->rchild = _TreeCreate(array,index,size,null_node);
return root;
}
TreeNode* CreateTree(TreeNodeType array[],size_t size,TreeNodeType null_node)
{
size_t index = 0;
TreeNode* root = _TreeCreate(array,&index,size,null_node);
return root;
}
void TreeDestroy(TreeNode* root)
{
//方法一
if(root == NULL)
{
return;
}
TreeDestroy(root->lchild);
TreeDestroy(root->rchild);
DestroyTreeNode(root);
//方法二
// TreeNode* lchild = root->lchild;
// TreeNode* rchild = root->lchild;
// DestroyTreeNode(root);
// TreeDestroy(lchild);
// TreeDestroy(rchild);
}
TreeNode* TreeClone(TreeNode* root)
{
if(root == NULL)
{
return NULL;
}
//按先序遍历方式
TreeNode* New_node = CreateNode(root->data);
printf("%c ",root->data);
New_node->lchild = TreeClone(root->lchild);
New_node->rchild = TreeClone(root->rchild);
return New_node;
}
//节点个数：方法一
size_t TreeSize(TreeNode* root)
{
if(root == NULL)
{
return 0;
}
return 1 + TreeSize(root->lchild) + TreeSize(root->rchild);
}
//节点个数：方法二
void _TreeSize(TreeNode* root,size_t *size)
{
if(root == NULL || size == NULL)
{
return ;
}
++(*size);
_TreeSize(root->lchild,size);
_TreeSize(root->rchild,size);
}
//求叶子节点个数（左右子树都为空）
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);
}
//第K层节点个数
size_t TreeKLevelSize(TreeNode* root,int K)
{
if(root == NULL)
{
return 0;
}
if(K == 1)
{
return 1;
}
return TreeKLevelSize(root->lchild,K - 1) + TreeKLevelSize(root->rchild,K - 1);
}
//树的高度
size_t TreeHeight(TreeNode* root)
{
if(root == NULL)
{
return 0;
}
if(root->lchild == NULL && root->rchild == NULL)
{
return 1;
}
size_t lheight = TreeHeight(root->lchild);
size_t rheight = TreeHeight(root->rchild);
return 1 + (lheight > rheight ? lheight:rheight);
}
//查找节点（给定一个值，求对应节点的指针）
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;
}
//求当前节点的左子树
TreeNode* LChild(TreeNode* node)
{
if(node == NULL)
{
return NULL;
}
return node->lchild;
}
//求当前节点的右子树
TreeNode* RChild(TreeNode* node)
{
if(node == NULL)
{
return NULL;
}
return node->rchild;
}
//求当前节点的父节点
TreeNode* Parent(TreeNode* root,TreeNode* node)
{
if(root == NULL || node == NULL)
{
return NULL;
}
if(root->lchild == node || root->lchild == node)
{
return root;
}
TreeNode* lresult = Parent(root->lchild,node);
TreeNode* rresult = Parent(root->rchild,node);
return lresult != NULL ? lresult:rresult;
}
//非递归遍历
//
//先序遍历
//1.先将根节点入栈
//2.循环开始
//a.取栈顶元素为当前元素
//b.出栈
//c.把当前元素的右子树入栈
//d.把当前元素的左子树入栈
void PreOrderByLoop(TreeNode* root)
{
if(root == NULL)
{
return;
}
SeqStack stack;
SeqstackInit(&stack);
SeqstackPush(&stack,root);
TreeNode* cur = NULL;
while(SeqstackFront(&stack,&cur))
{
SeqstackPop(&stack);
printf("%c ",cur->data);
if(cur->rchild != NULL)
{
SeqstackPush(&stack,cur->rchild);
}
if(cur->lchild != NULL)
{
SeqstackPush(&stack,cur->lchild);
}
}
printf("\n");
}
//中序遍历
void InOrderByLoop(TreeNode* root)
{
if(root == NULL)
{
return;
}
//1.定义cur指向根节点
//2.循环判定cur，若不为null，将cur入栈，并且cur->lchild
//3.如果cur=null，取栈顶元素，访问、出栈
//4.让cur指向栈顶元素的右子树，重复
SeqStack stack;
SeqstackInit(&stack);
TreeNode* cur = root;
while(1)
{
while(cur != NULL)
{
SeqstackPush(&stack,cur);
cur = cur->lchild;
}
TreeNode* top = NULL;
int ret = SeqstackFront(&stack,&top);
if(ret == 0)
{
printf("\n");
return;
}
printf("%c ",top->data);
SeqstackPop(&stack);
cur = top->rchild;
}
}
//后序遍历
//和中序遍历的区别：取到的栈顶元素不能立即访问，因为不能确定当前节点的右子树是否访问过
void PostOrderByLoop(TreeNode* root)
{
if(root == NULL)
{
return;
}
//对于栈顶元素能不能访问，需要满足以下2个条件之一：
//1.当前元素没有右子树
//2.当前元素的右子树是否被访问过了（是否为下一个元素）
//
//此时思路为：
//1.定义一个指针cur指向root
//2.循环判定cur是否为空，如果不为空，cur入栈，cur = cur->lchild;
//3.cur = NULL 循环取栈顶元素。
//4.对栈顶元素进行判断
//a. 如果栈顶元素的右子树和访问上一个元素是同一个元素
//b.栈顶元素的右子树为空
//此时才能取栈顶元素，同时出栈
TreeNode* cur = root;
SeqStack stack;
SeqstackInit(&stack);
TreeNode* pre = NULL;
while(1)
{
while(cur != NULL)
{
SeqstackPush(&stack,cur);
cur = cur->lchild;
}
TreeNode* top = NULL;
int ret = SeqstackFront(&stack,&top);
if(ret == 0)
{
printf("\n");
return;
}
if(top->rchild == NULL || top->rchild == pre)
{
printf("%c ",top->data);
SeqstackPop(&stack);
pre = top;
}
else
{
cur = top->rchild;
}
}
}
//镜像递归
void Swap(TreeNode** a,TreeNode** b)
{
TreeNode* tmp = *a;
*a = *b;
*b = tmp;
return;
}
void TreeMirror(TreeNode* root)
{
if(root == NULL)
{
return;
}
Swap(&root->lchild,&root->rchild);
TreeMirror(root->lchild);
TreeMirror(root->rchild);
}
//镜像非递归
void TreeMirrorByLoop(TreeNode* root)
{
if(root == NULL)
{
return;
}
LinkQueue queue;
LinkQueueInit(&queue);
LinkQueuePush(&queue,root);
TreeNode* cur = NULL;
while(LinkQueueFront(&queue,&cur))
{
LinkQueuePop(&queue);
if(cur->lchild != NULL)
{
LinkQueuePush(&queue,cur->lchild);
}
if(cur->rchild != NULL)
{
LinkQueuePush(&queue,cur->rchild);
}
}
printf("\n");
return;
}
//判断是否为完全二叉树
//条件：层序遍历
//可分为两个阶段
//一、任何一个节点同时具有左右子树，一旦发现哪个子树不是同时具备
//a.当前节点只有右子树，一定不是完全二叉树
//b.如果当前节点只有左子树，进入第二阶段。
//c.当前节点没有子树，也进入阶段二。
//二、当遍历结束后，所有条件都满足，则为完全二叉树，不满足则不是。
int IsCompleteTree(TreeNode* root)
{
if(root == NULL)
{
return 0;
}
LinkQueue queue;
LinkQueueInit(&queue);
LinkQueuePush(&queue,root);
TreeNode* cur = NULL;
int if_start_step_to_flag = 0;
while(LinkQueueFront(&queue,&cur))
{
LinkQueuePop(&queue);
if(if_start_step_to_flag = 0)
{
if(cur->lchild != NULL && cur->rchild == NULL)
{
//同时具备右子树
LinkQueuePush(&queue,cur->lchild);
LinkQueuePush(&queue,cur->rchild);
}
else if(cur->lchild == NULL && cur->rchild != NULL)
{
//只有右子树，没有左子树，一定不是完全二叉树
return 0;
}
else if(cur->lchild != NULL && cur->rchild == NULL)
{
if_start_step_to_flag = 1;
}
else
{
if(cur->lchild == NULL && cur->rchild == NULL)
{
;
}
}
}
else
{
return 0;
}
}
}
