二叉樹和鏈表相似，只是后節點變成了左右節點，重要的是遞歸思想的理解和返回時候的層級結構

1.滿二叉樹的穿件及前中后序遍歷

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
int date;
struct node * lchild;
struct node * rchild;
}btreenode;

btreenode * btree_create(int a,int b){
btreenode * t = NULL;
t = (btreenode*)malloc(sizeof(btreenode));
t->date = b;
if(2*b<=a){
t->lchild = btree_create(a,2*b);
}
else{
t->lchild = NULL;
}
if(2*b+1<=a){
t->rchild = btree_create(a,2*b+1);
}
else{
t->rchild = NULL;
}
return t;
}

void first_show(btreenode* root){

printf("%d ",root->date);
if(root->lchild != NULL){
first_show(root->lchild);
}
if(root->rchild != NULL){
first_show(root->rchild);
}
}

void middle_show(btreenode* root){

if(root->lchild != NULL){
middle_show(root->lchild);
}
printf("%d ",root->date);
if(root->rchild != NULL){
middle_show(root->rchild);
}
}

void last_show(btreenode* root){

if(root->lchild != NULL){
last_show(root->lchild);
}
if(root->rchild != NULL){
last_show(root->rchild);
}
printf("%d ",root->date);
}

int main(int argc, const char *argv[])
{
btreenode * root = btree_create(10,1);
first_show(root);
printf("\n");
middle_show(root);
printf("\n");
last_show(root);
printf("\n");
return 0;
}

2.不完全二叉樹的創建（sancf和getchar方法均會產生垃圾字符，輸入時候需要區分）

typedef struct node{
int date;
struct node * lchild;
struct node * rchild;
}btreenode;

btreenode * btree_create(){
btreenode * t = NULL;
t = (btreenode*)malloc(sizeof(btreenode));
char i = getchar();
getchar();
t->date = i;

if(i == '#'){
return NULL;
}
t->lchild = btree_create();
t->rchild = btree_create();
return t;
}

void first_show(btreenode* root){

printf("%c ",root->date);
if(root->lchild != NULL){
first_show(root->lchild);
}
if(root->rchild != NULL){
first_show(root->rchild);
}
}

void middle_show(btreenode* root){

if(root->lchild != NULL){
middle_show(root->lchild);
}
printf("%c ",root->date);
if(root->rchild != NULL){
middle_show(root->rchild);
}
}

void last_show(btreenode* root){

if(root->lchild != NULL){
last_show(root->lchild);
}
if(root->rchild != NULL){
last_show(root->rchild);
}
printf("%c ",root->date);
}

int main(int argc, const char *argv[])
{
btreenode * root = btree_create();
first_show(root);
printf("\n");
middle_show(root);
printf("\n");
last_show(root);
printf("\n");
return 0;
}

3、二叉樹的層級遍歷（使用進隊出隊思想，最好是進隊即出隊，別想著全部進隊后出隊，對比下前者還是節省內存的）

#include <stdio.h>
#include <stdlib.h>

typedef struct node{
int date;
struct node * lchild;
struct node * rchild;
}btreenode;

typedef struct linklist{
btreenode * node1;
struct linklist * next;
}linklist;

linklist * linklist_create(){
linklist* ln =NULL;
ln = (linklist*)malloc(sizeof(linklist));
ln->next = NULL;
return ln;
}

void linklist_show(linklist * ln){
while(ln->next != NULL){
printf("%d ",ln->next->node1->date);
ln = ln->next;
}
printf("\n");
}
int linklist_in(linklist* ln,btreenode * btree){
if(btree == NULL) {return -1;}
linklist* t = ln;
linklist* temp = linklist_create();
temp->node1 = btree;
while(t->next != NULL){t = t->next;}
t->next = temp;
temp->next = NULL;
return 0;
}
int linklist_out(linklist * ln){
if(ln->next == NULL){return -1;}

linklist *temp = ln->next;
ln->next = temp->next;

int value = temp->node1->date;
// printf("%d ",temp->node1->date);
free(temp);
temp =NULL;
return value;
}

btreenode * btree_create(int a,int b){
btreenode * t = NULL;
t = (btreenode*)malloc(sizeof(btreenode));
t->date = b;
if(2*b<=a){
t->lchild = btree_create(a,2*b);
}
else{
t->lchild = NULL;
}
if(2*b+1<=a){
t->rchild = btree_create(a,2*b+1);
}
else{
t->rchild = NULL;
}
return t;
}

void btree_tier_show(linklist* ln,btreenode* root){

// linklist* t = ln;
linklist_in(ln,root);
// printf("%d ",linklist_out(ln));
while(ln->next != NULL){
if(ln->next->node1->lchild != NULL)
linklist_in(ln,ln->next->node1->lchild);
if(ln->next->node1->lchild != NULL)
linklist_in(ln,ln->next->node1->rchild);
printf("%d ",linklist_out(ln));
}
printf("\n");
}

?

void first_show(btreenode* root){

printf("%d ",root->date);
if(root->lchild != NULL){
first_show(root->lchild);
}
if(root->rchild != NULL){
first_show(root->rchild);
}
}

int main(int argc, const char *argv[])
{
btreenode * root = btree_create(20,1);
first_show(root);
printf("\n---------------------\n");
linklist *ln = linklist_create();
btree_tier_show(ln,root);
return 0;
}

?

轉載于:https://www.cnblogs.com/huiji12321/p/11246752.html

總結

以上是生活随笔為你收集整理的step3 . day6数据结构之非线性表 满二叉树和不完全二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。