数据结构之二叉树

时间：2021-05-07 10:48:15

一.二叉树如何表示输入：

数据结构之二叉树

 

二.二叉树完整代码

 

#include <iostream>
#include<cstdio>
#include<cstdlib>

using namespace std;

typedef struct BinaryTreeNode
{
    int data;
    struct BinaryTreeNode *Left;
    struct BinaryTreeNode *Right;
}Node;


//创建二叉树，顺序依次为中间节点->左子树->右子树
Node* createBinaryTree()
{
    Node *p;
    int ch;
    cin>>ch;
    if(ch == 0)     //如果到了叶子节点，接下来的左、右子树分别赋值为0
    {
        p = NULL;
    }
    else
    {
        p = (Node*)malloc(sizeof(Node));//动态分配空间
        p->data = ch;
        p->Left  = createBinaryTree();  //递归创建左子树
        p->Right = createBinaryTree();  //递归创建右子树
    }
    return p;
}

//先序遍历
void preOrderTraverse(Node* root)
{
    if( root )
    {
        cout<<root->data<<' ';
        preOrderTraverse(root->Left);
        preOrderTraverse(root->Right);
    }
}

//中序遍历
void inOrderTraverse(Node* root)
{
    if( root )
    {
        inOrderTraverse(root->Left);
        cout<<root->data<<' ';
        inOrderTraverse(root->Right);
    }
}

//后序遍历
void lastOrderTraverse(Node* root)
{
    if( root )
    {
        lastOrderTraverse(root->Left);
        lastOrderTraverse(root->Right);
        cout<<root->data<<' ';
    }
}

//二叉树节点总数目
int Nodenum(Node* root)
{
    if(root == NULL)
    {
        return 0;
    }
    else
    {
        return 1+Nodenum(root->Left)+Nodenum(root->Right);

    }
}

//二叉树的深度
int DepthOfTree(Node* root)
{
    if(root)
    {
        return DepthOfTree(root->Left)>DepthOfTree(root->Right)?DepthOfTree(root->Left)+1:DepthOfTree(root->Right)+1;
    }
    if( root == NULL )
    {
        return 0;
    }
}

//二叉树叶子节点数
int Leafnum(Node* root)
{
    if(!root)
    {
        return 0;
    }
    else if(  (root->Left == NULL) && (root->Right == NULL) )//两边都是空，才说明它是叶子节点
    {
        return 1;
    }
    else
    {
        return  (Leafnum(root->Left) + Leafnum(root->Right)) ;
    }
}


int main()
{
    Node *root = NULL;
    root = createBinaryTree();
    printf("二叉树建立成功");
    cout<<endl;

    cout<<"二叉树总节点数为："<<Nodenum(root)<<endl;

    cout<<"二叉树深度为："<<DepthOfTree(root)<<endl;

    cout<<"二叉树叶子节点数为："<<Leafnum(root)<<endl;

    cout<<"前序遍历结果:"<<endl;
    preOrderTraverse(root);
    cout<<endl;

    cout<<"中序遍历结果:"<<endl;
    inOrderTraverse(root);
    cout<<endl;

    cout<<"后序遍历结果:"<<endl;
    lastOrderTraverse(root);
    cout<<endl;

    return 0;
}

 

数据结构之二叉树数据结构之二叉树
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 
  4 typedef struct BinaryTreeNode
  5 {
  6     int date;
  7     struct BinaryTreeNode*Left;
  8     struct BinaryTreeNode*Right;
  9 }Node;
 10 
 11 Node* createBinaryTree()
 12 {
 13     Node *p;
 14     int val;
 15     cin>>val;
 16     if(val==0)
 17         p=NULL;
 18     else
 19     {
 20         p=(Node*)malloc(sizeof(Node));
 21         p->date=val;
 22         p->Left=createBinaryTree();
 23         p->Right=createBinaryTree();
 24     }
 25     return p;
 26 }
 27 
 28 void preOrderTraverse(Node* root){
 29     if(root!=NULL)
 30     {
 31         cout<<root->date<<" ";
 32         preOrderTraverse(root->Left);
 33         preOrderTraverse(root->Right);
 34     }
 35 }
 36 
 37 void inOrderTraverse(Node* root){
 38     if(root!=NULL)
 39     {
 40         preOrderTraverse(root->Left);
 41         cout<<root->date<<" ";
 42         preOrderTraverse(root->Right);
 43     }
 44 }
 45 
 46 void lastOrderTraverse(Node* root){
 47     if(root!=NULL)
 48     {
 49         preOrderTraverse(root->Left);
 50         preOrderTraverse(root->Right);
 51         cout<<root->date<<" ";
 52     }
 53 }
 54 
 55 int Nodenum(Node* root)//二叉树节点数
 56 {
 57     if(root==NULL)
 58         return 0;
 59     else
 60         return Nodenum(root->Left)+Nodenum(root->Right)+1;
 61 }
 62 
 63 int DepthofTree(Node* root)
 64 {
 65     if(root)
 66         return DepthofTree(root->Left)>DepthofTree(root->Right)?DepthofTree(root->Left)+1:DepthofTree(root->Right)+1;
 67     if(root==NULL)
 68         return 0;
 69 }
 70 
 71 int Leafnum(Node* root)
 72 {
 73     if(!root)
 74         return 0;
 75     else if(root->Left==NULL&&root->Right==NULL)
 76         return 1;
 77     else
 78         return Leafnum(root->Left)+Leafnum(root->Right);
 79 }
 80 
 81 
 82 int main(){
 83     Node *root=NULL;
 84     root=createBinaryTree();
 85     cout<<endl;
 86     cout<<"二叉树总节点数为："<<Nodenum(root)<<endl;
 87 
 88     cout<<"二叉树深度为："<<DepthofTree(root)<<endl;
 89 
 90     cout<<"二叉树叶子节点数为："<<Leafnum(root)<<endl;
 91 
 92     cout<<"前序遍历结果:"<<endl;
 93     preOrderTraverse(root);
 94     cout<<endl;
 95 
 96     cout<<"中序遍历结果:"<<endl;
 97     inOrderTraverse(root);
 98     cout<<endl;
 99 
100     cout<<"后序遍历结果:"<<endl;
101     lastOrderTraverse(root);
102     cout<<endl;
103 
104     return 0;
105 }
View Code

 

 

数据结构之二叉树数据结构之二叉树
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef struct TreeNode{
  4     int data;
  5     struct TreeNode* left1;
  6     struct TreeNode* right1;
  7 }Node;
  8 
  9 Node* createTreeNode()
 10 {
 11     Node* p;
 12     int val;
 13     cin>>val;
 14     if(val==0)
 15         p=NULL;
 16     else
 17     {
 18        p=(Node*)malloc(sizeof(Node));
 19        p->data=val;
 20        p->left1=createTreeNode();
 21        p->right1=createTreeNode();
 22     }
 23     return p;
 24 }
 25 
 26 //先序遍历
 27 void PreCheck(Node* root)
 28 {
 29     if(root!=NULL)
 30     {
 31         cout<<root->data<<" ";
 32         PreCheck(root->left1);
 33         PreCheck(root->right1);
 34     }
 35 }
 36 
 37 //中序遍历
 38 void InCheck(Node* root)
 39 {
 40     if(root!=NULL)
 41     {
 42         PreCheck(root->left1);
 43         cout<<root->data<<" ";
 44         PreCheck(root->right1);
 45     }
 46 }
 47 
 48 //后序遍历
 49 void LastCheck(Node* root)
 50 {
 51     if(root!=NULL)
 52     {
 53         PreCheck(root->left1);
 54         PreCheck(root->right1);
 55         cout<<root->data<<" ";
 56     }
 57 }
 58 
 59 //节点总数
 60 int TreeNum(Node* root)
 61 {
 62     if(root==NULL)
 63         return 0;
 64     else
 65        return 1+TreeNum(root->left1)+TreeNum(root->right1);
 66 }
 67 
 68 //叶叶子节点总数
 69 int LeafNum(Node* root)
 70 {
 71     if(root==NULL)
 72         return 0;
 73     else if(root->left1==NULL&&root->right1==NULL)
 74          return 1;
 75     else
 76       return  LeafNum(root->left1)+LeafNum(root->right1);
 77 }
 78 
 79 //二叉树的深度
 80 int DepthTree(Node* root)
 81 {
 82     if(root==NULL)
 83        return 0;
 84     else
 85         return DepthTree(root->left1)>DepthTree(root->right1)?DepthTree(root->left1)+1:DepthTree(root->right1)+1;
 86 }
 87 
 88 int main()
 89 {
 90     Node* p=NULL;
 91     cout<<"创建二叉树"<<endl;
 92     p=createTreeNode();
 93     cout<<"二叉树创建成功"<<endl;
 94     cout<<endl;
 95     cout<<"先序遍历"<<endl;
 96     PreCheck(p);
 97     cout<<endl;
 98     cout<<"中序遍历"<<endl;
 99     InCheck(p);
100     cout<<endl;
101     cout<<"后序遍历"<<endl;
102     LastCheck(p);
103     cout<<endl;
104     cout<<TreeNum(p)<<endl;
105     cout<<LeafNum(p)<<endl;
106     cout<<DepthTree(p)<<endl;
107 }
View Code

 

　　

 

标签：

相关文章