数据结构 二叉树的基本操作(递归版本)
程序员文章站
2022-06-07 07:54:57
...
此处我们采用孩子表示法来完成遍历:
typedef char TreeNodeType;
typedef struct TreeNode{
TreeNodeType data;
struct TreeNode* lchild;
struct TreeNode* rchild;
}TreeNode;
首先我们先构造一棵树:
先序遍历:ABDGHEICFJ
中序遍历:GHDBIEAFJC
后序遍历:HGDIEBJFCA
层序遍历:ABCDEFGIJH
先序遍历思路
- 先访问根节点
- 递归地对左子树进行访问
- 递归地对右子树进行访问
中序遍历思路
- 递归地对左子树进行访问
- 访问根节点
- 递归地对右子树进行访问
后序遍历思路
- 递归地对左子树进行访问
- 递归地对右子树进行访问。
- 最后访问根节点
层序遍历思路
需要借助队列来完成
以下为代码:
#pragma once
#include<stdio.h>
#include<stdlib.h>
#define TITLE printf("\n======================%s===================\n",__FUNCTION__);
typedef char TreeDataType;
typedef struct TreeNode{
TreeDataType data;
struct TreeNode* lchild;
struct TreeNode* rchild;
}TreeNode;
void TreeInit(TreeNode** root);//二叉树的初始化
TreeNode* CreateTreeNode(TreeDataType value);//创建结点
void DestroyNode(TreeNode* Node);//销毁结点
void TreePreOrder(TreeNode* root);//先序遍历二叉树
void TreeInOrder(TreeNode* root);//中序遍历二叉树
void TreePostOrder(TreeNode* root);//后序遍历二叉树
void TreeLevelOrder(TreeNode* root);//层序遍历二叉树
#include"tree.h"
#include"seqqueue.h"
void TreeInit(TreeNode** root)
{
if(root == NULL)
{
return;
}
*root = NULL;
}
TreeNode* CreateTreeNode(TreeDataType value)
{
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = value;
newNode->lchild = NULL;
newNode->rchild = NULL;
return newNode;
}
void TreePreOrder(TreeNode* root)
{
if(root == NULL)
{
return;
}
//先访问根节点
printf("%c ",root->data);
//递归访问左子树
TreePreOrder(root->lchild);
//递归访问右子树
TreePreOrder(root->rchild);
}
void TreeInOrder(TreeNode* root)
{
if(root == NULL)
{
return;
}
//递归访问左子树
TreeInOrder(root->lchild);
//访问根节点
printf("%c ",root->data);
//递归访问右子树
TreeInOrder(root->rchild);
}
void TreePostOrder(TreeNode* root)
{
if(root == NULL)
{
return;
}
//递归访问左子树
TreePostOrder(root->lchild);
//递归访问右子树
TreePostOrder(root->rchild);
//访问根节点
printf("%c ",root->data);
}
void TreeLevelOrder(TreeNode* root)
{
if(root == NULL)
{
//空树
return;
}
SeqQueue queue;
SeqQueueInit(&queue);
//程序运行至此人r,说明树不为空,将根节点入队列
SeqQueuePush(&queue,root);
TreeNode* cur = NULL;
while(1)
{
int ret = SeqQueueGet(&queue,&cur);
if(ret == 0)
{
//说明队列空了
//也就是,树遍历完了
break;
}
printf("%c ",cur->data);
SeqQueuePop(&queue);
if(cur->lchild != NULL)
{
SeqQueuePush(&queue,cur->lchild);
}
if(cur->rchild != NULL)
{
SeqQueuePush(&queue,cur->rchild);
}
}
printf("\n");
}
//////////////////////////////////////////////////
// 以下为测试函数 //
/////////////////////////////////////////////////
void TestInit()
{
TITLE;
TreeNode* root;
TreeInit(&root);
printf("expected is NULL,actul is %p\n",root);
}
void TestTreeOrder()
{
TITLE;
TreeNode* A = CreateTreeNode('A');
TreeNode* B = CreateTreeNode('B');
TreeNode* C = CreateTreeNode('C');
TreeNode* D = CreateTreeNode('D');
TreeNode* E = CreateTreeNode('E');
TreeNode* F = CreateTreeNode('F');
TreeNode* G = CreateTreeNode('G');
TreeNode* H = CreateTreeNode('H');
TreeNode* I = CreateTreeNode('I');
TreeNode* J = CreateTreeNode('J');
A->lchild = B;
A->rchild = C;
B->lchild = D;
B->rchild = E;
C->lchild = F;
D->lchild = G;
E->lchild = I;
F->rchild = J;
G->rchild = H;
printf("[先序遍历]:\n");
TreePreOrder(A);
printf("\n");
printf("[中序遍历]:\n");
TreeInOrder(A);
printf("\n");
printf("[后序遍历]:\n");
TreePostOrder(A);
printf("\n");
printf("[层序遍历]:\n");
TreeLevelOrder(A);
}
int main()
{
TestInit();
TestTreeOrder();
return 0;
}
运行结果: