C语言--数据结构 二叉树有关操作

以下代码可以直接复制粘贴使用

#include 

typedef struct Node1{
    int data;
    struct Node1* left;
    struct Node1* right;
}Node;

//树根
typedef struct {
   Node *root;
}Tree;

建立二叉树

void Creat_btree(Tree*tree,int data)
{
   Node* temp = malloc(sizeof(Node));  //开辟一个新节点存储数据
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   if(tree->root == NULL)     //判断根节点是否为空，节点赋值为根节点
   {
       tree -> root = temp;
   }
   else                       //根节点不为空，将节点插入
   {
     Node* node = tree->root; //定义一个新节点来接收树根节点
     while(node != NULL)
     {
         if(data < node->data)  //数据比根节点数值小，放到左边
         {
             if(node -> left == NULL) //根节点左边的节点为空，直接放到根节点左边
             {
                 node ->left = temp;
                 return;
             }
             else  //根节点左边节点不为空
             {
                  node = node->left;
             }
         }
         else
         {

             if(node -> right ==NULL)
             {
                 node -> right = temp;
                 return;
             }
             else
             {
                 node = node->right;
             }

         }
     }
   }
}

求二叉树的高度

int get_height(Node* node)
{
    int max;
    if(node == NULL)
        return 0;
    else
    {
        int left_h = get_height(node->left);
        int right_h = get_height(node->right);
        if(left_h > right_h) max = left_h;
        else max = right_h;
    }
    return max+1;
}

求二叉树内的最大值

int get_maxnum(Node* node)
{
    if(node == NULL)
    {
        return -1;
    }
    else
    {
        int m1 = get_maxnum(node->left);
        int m2 = get_maxnum(node->right);
        int m3 = node->data;
        int max = m1;
        if(m2 > max) max = m2;
        if(m3 > max) max = m3;
        return max;
    }

}

查找二叉树内的值

int search_num(Node* node,int val)
{
    if(node == NULL)
    {
        printf("没有找到n");
        return -1;
    }
    if(node->data == val)
    {
        return val;
    }
    else if(val > node->data)
    {
        search_num(node->right,val);
    }
    else
    {
        search_num(node -> left,val);
    }
}

前序遍历二叉树 先访问根再访问左边之后右边

void preorder(Node* node_temp)
{
  if(node_temp != NULL)
  {
      printf("%dn",node_temp->data);
      preorder(node_temp ->left);
      preorder(node_temp ->right);
  }
}

中序遍历，先访问左边，再访问树根，再访问右边

void inorder(Node* node_temp)
{
    if(node_temp != NULL)
    {
        inorder(node_temp ->left);
        printf("%dn",node_temp->data);
        inorder(node_temp ->right);
    }
}

后续遍历，先访问左边，再访问右边，在访问树根

void posorder(Node* node_temp)
{
        if(node_temp != NULL)
    {
        posorder(node_temp ->left);
        posorder(node_temp ->right);
        printf("%dn",node_temp->data);
    }
}

int main()
{
    Node*p =NULL;
    int i;
    int arr[7] = {6,3,8,2,5,1,7};
    Tree tree;
    tree.root = NULL;
    for(i = 0;i < 7;i++)
    {
        Creat_btree(&tree,arr[i]);
    }
    i = get_height(tree.root);
    printf("height = %dn",i);
    inorder(tree.root);
    i = get_maxnum(tree.root);
    printf("maxnum = %dn",i);
    i = search_num(tree.root,20);
    printf("findnum = %dn",i);
    return 0;
}