二叉树三种遍历方法、查询树深度、叶子数_一维数组存储二叉树,按层次遍历统计叶子节点

简介

• 二叉树的相关概念，如，树高度，节点层数，节点度数，路径，叶节点，分支节点，根节点，父节点，左节点，右节点，兄弟节点，祖先节点，子孙节点，左子树，右子树等基本概念，不再赘述。

二叉树分类

1、完全二叉树

• 若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
• 一维数组可以作为完全二叉树的存储结构，堆排序使用的数据结构就是完全二叉树。
  

2、满二叉树

• 国际标准定义是除了叶结点外每一个结点都有左右子结点的二叉树
  
• 国内的定义是：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。很显然，按照这个定义，上面的图示二叉树就不是满二叉树。

3、扩充二叉树

• 扩充二叉树是对已有二叉树的扩充，扩充后的二叉树的节点都变为度数为2的分支节点。也就是说，如果原节点的度数为2，则不变，度数为1，则增加一个分支，度数为0的叶子节点则增加两个分支。
  

4、平衡二叉树

• 是一棵空树或它的任意节点的左右两个子树的高度差的绝对值不超过1
  

二叉树的构建

遍历方式

• 前序遍历：root -> left -> right
• 中序遍历：left -> root -> right
• 后续遍历：left ->right -> root
• 层序遍历：按照层次遍历
• 

样例输入：

1 2 3 4 5 6 0 0 0 7 8 0 9 0 0 0 0 0 0
1

• 以下实现二叉树的所有实现，包括：三种遍历方法、查询树深度叶子数等。但是要通过遍历结果确定一个树，需要中序遍历配合另外的其中一种遍历方式才行。

  代码:

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

struct BTreeNode{
    int data = 0;
    BTreeNode *left;
    BTreeNode *right;
};
class BTree{
public:
    
    //传参需要注意，二叉树是指针类型的，节点本身就是一个指针：*node。所以需要二级指针才能改变二叉树的内容
    //按前序创建二叉树
    void create(BTreeNode* &Node){
        int data;
        cin >> data;
        if(data){
            Node = new BTreeNode;
            Node->data = data;
            //cout<<"data:"<<data<<endl;
            create(Node->left);
            create(Node->right);
        } else{
            Node=NULL;
        }
    }
    
    //按层创建二叉树
    void levelCreate(BTreeNode* &Node){
        queue <BTreeNode*> que;
        int data;
        cin>>data;
        if(data){
            Node = new BTreeNode;
            Node->data = data;
            que.push(Node);
        } else{
            Node = NULL;
            return;
        }
        while(!que.empty()){
            BTreeNode *node = que.front();//取先进入的
            que.pop();
            //输入左边数据
            cin>>data;
            if(data){
                node->left = new BTreeNode;
                node->left->data = data;
                que.push(node->left);
            } else{
                node->left = NULL;
            }
            //输入右边数据
            cin >>data;
            if(data){
                node->right = new BTreeNode;
                node->right->data = data;
                que.push(node->right);
            } else{
                node->right = NULL;
            }
        }
    }
    //1 2 3 4 5 6 0 0 0 7 8 0 9 0 0 0 0 0 0
    //清除链表
    void clear(BTreeNode*& Node){
        BTreeNode *p = Node;
        if(p != NULL){
            clear(Node->left);
            clear(Node->right);
            delete p;
        }
    }
    
    //前序遍历(根左右)
    void preorderTree(BTreeNode* Node){
        if(Node!=NULL){
            cout<<Node->data<<" ,";
            preorderTree(Node->left);
            preorderTree(Node->right);
        }
    }

    //中序遍历(左中右)
    void inorderTree(BTreeNode* Node){
        if(Node != NULL){
            inorderTree(Node->left);
            cout<<Node->data<<" ,";
            inorderTree(Node->right);
        }
    }

    //后序遍历（左右中）
    void postorderTree(BTreeNode* Node){
        if(Node != NULL){
            postorderTree(Node->left);
            postorderTree(Node->right);
            cout<<Node->data<<" ,";
        }
    }
    
    //层序遍历
    void levelTree(BTreeNode *Node){
        queue<BTreeNode*> que;
        if(Node == NULL) return;
        else{
            que.push(Node);
            while(!que.empty()){
                BTreeNode *node = que.front();
                cout<<node->data<<" ";
                que.pop();
                if(node->left != NULL){
                    que.push(node->left);
                }
                if(node->right!=NULL){
                    que.push(node->right);
                }
            }
        }
    }
    //二叉树深度
    int depthOfTree(BTreeNode* Node){
        if(Node){
            return max(depthOfTree(Node->left),depthOfTree(Node->right))+1;
        } else{
            return 0;
        }
    }
    //返回节点总数目
    int getNodeNum(BTreeNode* Node){
        if(Node){
            return 1+getNodeNum(Node->left)+getNodeNum(Node->right);
        } else{
            return 0;
        }
    }
    //返回叶子节点
    int getLeafNum(BTreeNode* Node){
        if(!Node){
            return 0;
        } else if(Node->left == NULL && Node->right == NULL){
            return 1;
        } else{
            return getLeafNum(Node->left)+getLeafNum(Node->right);
        }
    }
};
int main(){
    BTree tree;
    BTreeNode *root;
    //tree.create(root);
    tree.levelCreate(root);//按层创建
    
    cout<<"pre :";//前序
    tree.preorderTree(root);
    cout<<endl;
    
    cout<<"in  :";//中序
    tree.inorderTree(root);
    cout<<endl;
    
    cout<<"post:";//后序
    tree.postorderTree(root);
    cout<<endl;
    
    cout<<"level:";//层序
    tree.levelTree(root);
    cout<<endl;
    
    cout<<"NodeNum:"<<tree.getNodeNum(root)<<",depth:"<<tree.depthOfTree(root)<<",leaf:"<<tree.getLeafNum(root)<<endl;


    tree.clear(root);//清除
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

转自：https://blog.csdn.net/hellowd123/article/details/99692395