树的c++实现--建立一棵树

时间：2022-08-22 19:45:43

在学习二分查找树的时候，在递归的问题上遇到不少的问题，在这里和大家分享一下自己的学习过程

我在学习树的知识的时候，没有把树当做一个类，只把一个结点当做一个类。树的实现都在函数中，如果大家有兴趣可以试试在一个类中实现树

为了方便起见，这不同模板，结点的值用整数型

结点类的设计:

　　结点类中包含一个表示该节点值的val变量，和指向左结点和指向右结点的指针。这三者构成了一个简单的结点

1 class Node{
2 public:
3     int val;
4     Node *left, *right;
5     Node(){right = NULL; left = NULL;}
6 };

建立一棵树主要通过递归来实现

 1 Node* build(Node* root, int val){
 2       if(root == NULL){
 3            root = new Node();
 4            root->val = val;
 5            return root;
 6       }
 7       if(val < root->val) root->left = build(root->left, val);
 8      else if(val > root->val) root->right = build(root->right, val);
 9      return root;
10 }

 

这里我们用一个函数levelOrder() 来验证我们的树是否正确的建立。该函数是按层遍历树的结点，输出每个结点的值。实现过程在后面的博客会详细的说，现在

直接拿来用就行啦。

 1 void levelOrder(Node* root){
 2     queue<Node*> q;
 3     q.push(root);
 4     while(!q.empty()){
 5         Node *temp = q.front();
 6         q.pop();
 7         cout<<temp->val<<" ";
 8         if(temp->left) q.push(temp->left);
 9         if(temp->right) q.push(temp->right);
10     }
11 }
12 int main(){
13     Node *root = NULL;
14     int t[] = {5,4,6,3,7};
15     for(int i = 0; i < 5; i++) root = build(root, t[i]);
16     levelOrder(root);
17 return 0;}

我们来看看树是怎么建立的

root  = build(root, 5)

 

标签：

相关文章