当前位置 博文首页 > Scissors_初夏的博客:初夏小谈:前序构造二叉树及三种遍历(完
通过前序来构造出一棵二叉树,创建一颗二叉树,可以先创建根节点,后再创建它的左孩子和右孩子。遇到空就停止。对于每个结点都是先创建它的左孩子,之后再创建它的右孩子。
但是在创建左孩子和右孩子是,最大的问题就是,待创建数据要移动相应的位。每消耗一个数据就要取下一个元素。可以通过一个变量来计数移动的个数。此外要将每个根节点的左右孩子接起来。因此也要记录每个根节点来连接它的左右孩子。并且进行三种遍历。
代码如下:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
typedef struct Node
{
char data;
struct Node* Left;
struct Node* Right;
}Node;
typedef struct StuctNode
{
Node* ptr;
int count;
}StructNode;
//前序遍历构造二叉树
StructNode CreatBinaryTree(char arr[], int size);
//1.前序遍历
void PreorderTraversal(Node* ptr);
//2.中序遍历
void InorderTraversal(Node* ptr);
//3.后序遍历
void PostorderTraversal(Node* ptr);
#include"BinaryTree.h"
//1.前序遍历
void PreorderTraversal(Node* ptr)
{
if (ptr == NULL)
{
return;
}
printf("%c ", ptr->data);
PreorderTraversal(ptr->Left);
PreorderTraversal(ptr->Right);
}
//2.中序遍历
void InorderTraversal(Node* ptr)
{
if (ptr == NULL)
{
return;
}
InorderTraversal(ptr->Left);
printf("%c ", ptr->data);
InorderTraversal(ptr->Right);
}
//3.后序遍历
void PostorderTraversal(Node* ptr)
{
if (ptr == NULL)
{
return;
}
PostorderTraversal(ptr->Left);
PostorderTraversal(ptr->Right);
printf("%c ", ptr->data);
}
//前序遍历构造二叉树
//A B C # # E F # G
StructNode CreatBinaryTree(char arr[], int size)
{
if (size == 0)
{
StructNode result =
{
.ptr = NULL,
.count = 0
};
return result;
}
char data = arr[0];
if (arr[0] == '#')
{
StructNode result =
{
.ptr = NULL,
.count = 1
};
return result;
}
//创建根结点
Node* ptr = (Node*)malloc(sizeof(Node));
ptr->data = data;
//创建左子树
StructNode LeftNode = CreatBinaryTree(arr + 1, size-1);
ptr->Left = LeftNode.ptr;
//创建右子树
StructNode RightNode = CreatBinaryTree(arr + 1 + LeftNode.count, size - 1 - LeftNode.count);
ptr->Right = RightNode.ptr;
StructNode result =
{
.ptr = ptr,
.count = 1 + LeftNode.count + RightNode.count
};
return result;
}
#include"BinaryTree.h"
int main()
{
char* p = "ABD##E##C#F";
int size = strlen(p);
StructNode result = CreatBinaryTree(p, size);
//前序遍历:
printf("前序遍历:");
PreorderTraversal(result.ptr);
printf("\n");
//中序遍历:
printf("中序遍历:");
InorderTraversal(result.ptr);
printf("\n");
//前序遍历:
printf("前序遍历:");
PostorderTraversal(result.ptr);
printf("\n");
system("pause");
return 0;
}
结果显示:
该棵二叉树就是上一篇,二叉树的三种遍历的二叉树。
此次小结:
其中构造二叉树的结果需要用结构体来返回两个结果。应当注意。
在创建的过程中我对创建左子树后。把size--导致size被多次移动,出现了堆栈溢出的错误。走了不少弯路。但堆栈溢出也是极有可能发生的,因为栈区在内存中极其小一般默认1M。但可以一定程度上人为设置它的栈大小。更好的办法就是创建一块栈区。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?珍&源码
cs