C语言二叉树知识点讲解与实现代码

时间：2022-07-18 15:23:14

C语言二叉树概念讲解与实现代码

 二叉树的特点  

 二叉树作为树的一种，其节点至多有两个子节点。  (1).有限节点构成，集合可为空；  (2).二叉树的根节点可分成两个子树，左子树和右子树；  (3).可为空，但树不可以,至少要有根节点；  (4).子树有顺序关系，树没有；  (5).二叉树的分支度必为0、1、2，树的分支度可大于2；

 二叉树的分类

  1.歪斜树：左歪斜树或者右歪斜树，即所有节点的L或R均不存在。   2.满二叉树:树中所有节点均在同一阶层，而其它非终端节点之分支度均为2.   3.完全二叉树:若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布.

 二叉树的性质

 1.在二叉树中，第i层的结点总数不超过2^(i-1)；
 2.深度为h的二叉树最多有2^h-1个结点(h>=1)，最少有h个结点；
 3.对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
 4.具有n个结点的完全二叉树的深度为int（log2n）+1
 5.有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
   若I为结点编号则 如果I>1，则其父结点的编号为I/2；
   如果2*I<=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；
   如果2*I+1<=N，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。
 6.设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i

 二叉树节点表示法

  1.数组表示法 
#include <stdio.h>

void create_btree(int *b_tree,int *nodelist,int len)
{
int i;
int level;
b_tree[1]=nodelist[1];
for(i=2;i<len;i++){
level=1;
while(b_tree[level]!=0){
if(nodelist[i]<b_tree[level])
level=level*2;
else
level=level*2+1;
}
b_tree[level]=nodelist[i];
}

}
void main()
{
int i,index;
int data;
int b_tree[16],nodelist[16];
printf("please input data,0end\n");
index=1;
scanf("%d",&data);
while(data!=0){
nodelist[index]=data;
index=index+1;
scanf("%d",&data);
}
for(i=1;i<16;i++)
b_tree[i]=0;
create_btree(b_tree,nodelist,index);
for(i=1;i<16;i++)
printf("%2d: [%d]\n",i,b_tree[i]);

}

    2.链表表示法 
#include <stdio.h>
#include <stdlib.h>

struct tree
{
struct tree *left;
int data;
struct tree *right;
};
typedef struct tree treenode;
typedef treenode *b_tree;/*state b_tree list*/

/*insert b_tree node*/
b_tree insert_node(b_tree root,int node)
{
b_tree newnode;
b_tree currentnode;
b_tree parentnode;

newnode=(b_tree)malloc(sizeof(treenode));

newnode->data=node;
newnode->right=NULL;
newnode->left=NULL;

if(root==NULL)
return newnode;
else{
currentnode=root;
while(currentnode!=NULL){
parentnode=currentnode;
if((currentnode->data)>node)
currentnode=currentnode->left;
else
currentnode=currentnode->right;
}
if(parentnode->data > node)
parentnode->left=newnode;
else
parentnode->right=newnode;

}
return root;
}
/*build b_tree*/
b_tree create_btree(int *data,int len)
{
b_tree root=NULL;
int i;

for(i=0;i<len;i++)
root=insert_node(root,data[i]);
return root;
}
/*print b_tree*/
void print_btree(b_tree root)
{
       /*b_tree pointer;

pointer=root->left;
printf("print left_subtree node of root:\n");
while(pointer!=NULL){
printf("[%2d]\n",pointer->data);
pointer=pointer->left;
}
pointer=root->left;
printf("print right_subtree node of root:\n");
while(pointer!=NULL){
                printf("[%2d]\n",pointer->data);
                pointer=pointer->right;
        }*/
if(root==NULL)
return;
print_btree(root->left);
printf("%d\n",root->data);
print_btree(root->right);

}
void main()
{
b_tree root=NULL;
int i,index;/*how many elements you input*/
int value;
int nodelist[20];

printf("please input the elements of binary tree(exit for 0):\n");
index=0;
scanf("%d",&value);
while(value!=0){
nodelist[index]=value;
index=index+1;
scanf("%d",&value);
}
root=create_btree(nodelist,index);
print_btree(root);
}
currentnode指针不断移动寻找叶子节点，currentnode最终变为NULL，所以用parentnode指针保存了currentnode的值以便插入新元素。
     二叉树的结构数组表示法就不介绍啦，麻烦并且不如链表的灵活！

 二叉树的遍历 

        if(root==NULL)
                return;
        printf("%d\n",root->data);
        print_btree(root->left);
        print_btree(root->right);
        if(root!=NULL){
                print_btree(root->left);
                printf("%d\n",root->data);
                print_btree(root->right);
        }
        if(root!=NULL){
                print_btree(root->left);
                print_btree(root->right);
                printf("%d\n",root->data);
        }
      

      递归建立二叉树 

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

struct tree
{
struct tree *left;
int data;
struct tree *right;
};
typedef struct tree treenode;
typedef treenode *b_tree;
b_tree create_btree(int *nodelist,int position)
{
b_tree newnode;
if(nodelist[position]==0||position>15)
return NULL;
else{
newnode=(b_tree)malloc(sizeof(treenode));
newnode->data=nodelist[position];
newnode->left=create_btree(nodelist,2*position);
newnode->right=create_btree(nodelist,2*position+1);
return newnode;
}
}
/*print b_tree*/
void print_btree(b_tree root)
{
if(root!=NULL){
print_btree(root->left);
printf("%d\n",root->data);
print_btree(root->right);
}
/*if(root!=NULL){
print_btree(root->left);
print_btree(root->right);
printf("%d\n",root->data);
}*/
}
void main()
{
b_tree root=NULL;
int nodelist[16]={0,5,2,9,1,4,7,0,0,0,3,0,6,8,0,0};
root=create_btree(nodelist,1);
print_btree(root);
}

  二叉树二分查找

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

struct tree
{
struct tree *left;
int data;
struct tree *right;
};
typedef struct tree treenode;
typedef treenode *b_tree;
/*create the binary tree*/
b_tree create_btree(int *nodelist,int position)
{
b_tree newnode;
if(nodelist[position]==0||position>15)
return NULL;
else{
newnode=(b_tree)malloc(sizeof(treenode));
newnode->data=nodelist[position];
newnode->left=create_btree(nodelist,2*position);
newnode->right=create_btree(nodelist,2*position+1);
return newnode;
}
}
/*print b_tree*/
void print_btree(b_tree root)
{
if(root!=NULL){
print_btree(root->left);
printf("%d\n",root->data);
print_btree(root->right);
}
/*if(root!=NULL){
print_btree(root->left);
print_btree(root->right);
printf("%d\n",root->data);
}*/
}
/*search the binary tree*/
b_tree search_btree(b_tree point,int node)
{
while(point!=NULL){
if(point->data==node)
return point;
else{
if(point->data > node)
point=point->left;
else
point=point->right;
}
}
return NULL;
}
void main()
{
b_tree root=NULL;
b_tree point=NULL;
int node;
int nodelist[16]={0,5,2,9,1,4,7,0,0,0,3,0,6,8,0,0};
root=create_btree(nodelist,1);
print_btree(root);
printf("input the node you want search(1~9):\n");
scanf("%d",&node);
point=search_btree(root,node);
if(point==NULL)
printf("the node not find!\n");
else
printf("the node you want search is:%d\n",point->data);
}
标签：

相关文章