二叉树（我们组的代码

ssssshi

#include<bits/stdc++.h>
using namespace std;
struct bstnode
{
    int data;
    bstnode*left;
    bstnode*right;
};
bstnode*newroot(int n)//构建节点
{
    bstnode*root=new bstnode();
    root->data=n;
    root->left=NULL;
    root->right=NULL;
    return root;
}
bstnode* insert(bstnode* root, int num) // 插入节点
{
    if (root == NULL) {
        root = newroot(num);
    } else if (num <= root->data) {
        root->left = insert(root->left, num);
    } else {
        root->right = insert(root->right, num);
    }
    return root;
}
void deleteroot(bstnode* root)//删除所有节点
{
    if (root == NULL) return;
    deleteroot(root->left);
    deleteroot(root->right);
    delete root;
}
void bfsbianli(bstnode*root)//层序遍历
{
    if(root==NULL)return ;
    int cnt1=0,cnt2=0;
    queue<bstnode*>q;
    q.push(root);
    while(!q.empty())
    {
        bstnode*bianli=q.front();
        q.pop();
        cout<<bianli->data<<" ";
        if(bianli->left!=NULL)q.push(bianli->left);
        if(bianli->right!=NULL)q.push(bianli->right);
    }
}
void dfsqian(bstnode*root)//先序遍历
{
    cout<<root->data<<" ";
    if(root->left!=NULL)dfsqian(root->left);
    if(root->right!=NULL)dfsqian(root->right);
}
void dfszhong(bstnode*root)//中序遍历
{
    if(root->left!=NULL)dfszhong(root->left);
    cout<<root->data<<" ";
    if(root->right!=NULL)dfszhong(root->right);
}
void dfshou(bstnode*root)//后序遍历
{
    if(root->left!=NULL)dfshou(root->left);
    if(root->right!=NULL)dfshou(root->right);
    cout<<root->data<<" ";
}
int main()
{
    int n,num;
    cin>>n;
    bstnode*root=NULL;//根
    while(n--)
    {
        cin>>num;
        root = insert(root, num);
        bfsbianli(root);
        cout<<endl;
    }
    bfsbianli(root);
    //dfsqian(root);
    //dfszhong(root);
    //dfshou(root);
    deleteroot(root);
    return 0;
}
//9 50 30 70 20 40 60 80 10 90
//输入/50 /30 70 /20 40 60 80 /10 90/时(//内的顺序可随意改变)
/*所构造出的树
             50
       30          70
    20   40      60   80
10                          90
*/

Zero_canyon

#include<stdio.h>
#include<stdlib.h>
#define scanf scanf_s
const int N = 10;
typedef struct Node
{
	int data;
	Node* left;
	Node* right;
};
//创建
Node* creatNode(int a)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	if (!newNode)printf("分配失败\n");
	newNode->data = a;
	newNode->left = NULL;
	newNode->right = NULL;
	return newNode;
}
//插入
Node* myinsert(Node* place, int a)
{
	if (place == NULL)return creatNode(a);
	if (a < place->data) {
		place->left = myinsert(place->left, a);
	}
	else if (a > place->data) {
		place->right = myinsert(place->right, a);
	}
	else printf("输入重复\n");
	return place;
}
//前序
void qx(Node* Node)
{
	if (Node == NULL)return;
	printf("->%d", Node->data);
	qx(Node->left);
	qx(Node->right);
}
//后序
void hx(Node* Node)
{
	if (Node == NULL)return;
	hx(Node->left);
	hx(Node->right);
	printf("->%d", Node->data);
}
//中序
void zx(Node* Node)
{
	if (Node == NULL)return;
	zx(Node->left);
	printf("->%d", Node->data);
	zx(Node->right);
}
//层序
void cx(Node* Node1, Node* top,int line,int k,int kk)
{
	if (Node1 == NULL)return;
	if (line!=k)
	{
		cx(Node1->left, top, line + 1, k, 0);

		cx(Node1->right, top, line + 1, k, 0);
		return;
	}
	printf("第%d层:%d ",line, Node1->data);
	if (!kk)return;
	for (int i = 1; i < N; i++)
	{
		printf("\n");
		cx(top, top, 0, k + i, 1);
	}
}
//释放
void myfree(Node* Node)
{
	if (Node == NULL)return;
	myfree(Node->left);
	myfree(Node->right);
	free(Node);
}
int main()
{
	Node* list = NULL;
	list = myinsert(list,3);
	list = myinsert(list, 1);
	list = myinsert(list, 2);
	list = myinsert(list, 0);
	list = myinsert(list, 5);
	list = myinsert(list, 4);
	list = myinsert(list, 6);
	int a;
	int n; scanf("%d", &n);//输入n个数
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a);
		list = myinsert(list, a);
	}
	printf("前序：");
	qx(list);
	printf("\n");
	printf("中序：");
	zx(list);
	printf("\n");
	printf("后序：");
	hx(list);
	printf("\n");
	printf("层序：");
	cx(list,list,0,0,1);
	myfree(list);
	printf("\n");
	printf("检验：%d",list->data);//检验是否释放完毕
	return 0;
}
//初始树为：         3
		1	 5
	      0   2    4   6

xatu-chcq

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
#define eleType int

struct TreeNode {
    eleType val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Tree {
    public:
    TreeNode* create() {
        auto root = new TreeNode(1);
        root->left = new TreeNode(2);
        root->right = new TreeNode(3);
        root->left->left = new TreeNode(4);
        root->left->right = new TreeNode(5);
        root->right->left = new TreeNode(6);
        root->right->right = new TreeNode(7);
        return root;
    }
    /* 前中后序遍历-I
     * 递归的写法，这种遍历隐式的维护了一个栈
     */
    void prefunc(TreeNode* root,vector<int>& v){  //前(先)序遍历
        if(root==nullptr)return;
        v.push_back(root->val);
        prefunc(root->left,v);
        prefunc(root->right,v);
    }
    vector<int> preorder(TreeNode* root) {
        vector<int> v;
        prefunc(root,v);
        return v;
    }


    void infunc(TreeNode* root,vector<int>& v){   //中序遍历
        if(root==nullptr)return;
        infunc(root->left,v);
        v.push_back(root->val);
        infunc(root->right,v);
    }
    vector<int> inorder(TreeNode* root) {
        vector<int> v;
        infunc(root,v);
        return v;
    }


    void postfunc(TreeNode* root,vector<int>& v){  //后序遍历
        if(root==nullptr)return;
        postfunc(root->left,v);
        postfunc(root->right,v);
        v.push_back(root->val);
    }
    vector<int> postorder(TreeNode* root) {
        vector<int> v;
        postfunc(root,v);
        return v;
    }

    /* 前中后序遍历-II
     * 迭代的写法，使上文隐式维护的栈 显式地模拟出来
     */
    vector<int> preorderII(TreeNode* root){  //前(先)序遍历
        vector<int> v;
        stack<TreeNode*> k;
        while(root!=nullptr || !k.empty()){
            while(root!=nullptr){
                v.push_back(root->val);
                k.push(root);
                root=root->left;
            }
            root=k.top();
            k.pop();
            root=root->right;
        }
        return v;
    }
    vector<int> inorderII(TreeNode* root){   //中序遍历
        vector<int> v;
        stack<TreeNode*> k;
        while(root!=nullptr || !k.empty()){
            while(root!=nullptr){
                k.push(root);
                root=root->left;
            }
            root=k.top();
            k.pop();
            v.push_back(root->val);
            root=root->right;
        }
        return v;
    }
    vector<int> postorderII(TreeNode* root){  //后序遍历
        vector<int> v;
        stack<TreeNode*> k;
        TreeNode* prev=nullptr;
        while(root!=nullptr || !k.empty()) {
            while(root!=nullptr) {
                k.push(root);
                prev=root;
                root=root->left;
            }
            root=k.top();
            k.pop();
            if(root->right==nullptr || root->right==prev) {
                v.push_back(root->val);
                prev=root;
                root=nullptr;
            }else{
                k.push(root);
                prev=root;
                root=root->right;
            }
        }
        return v;
    }
    vector<vector<int>> levelorder(TreeNode* root) {
        vector<vector<int>> v;
        if(root==nullptr)return v;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int n=q.size();
            v.push_back(vector<int>());
            while(n--) {
                TreeNode* node = q.front();
                v.back().push_back(node->val);
                if(node->left)q.push(node->left);
                if(node->right)q.push(node->right);
                q.pop();
            }
        }
        return v;
    }
    void solve(TreeNode* root) {
        vector<int> pri = preorder(root),
                    ini = inorder(root),
                    poi = postorder(root),

                    prii = preorderII(root),
                    inii = inorderII(root),
                    poii = postorderII(root);

        vector<vector<int>> lo = levelorder(root);

        cout<<"PreOrder I : ";
        for(int & it : pri) {
            cout<<it<<" ";
        }
        cout<<endl;
        cout<<"PreOrder II: ";
        for(int & it : prii) {
            cout<<it<<" ";
        }
        cout<<endl<<endl;

        cout<<"InOrder I : ";
        for(int & it : ini) {
            cout<<it<<" ";
        }
        cout<<endl;
        cout<<"InOrder II: ";
        for(int & it : inii) {
            cout<<it<<" ";
        }
        cout<<endl<<endl;

        cout<<"PostOrder I : ";
        for(int & it : poi) {
            cout<<it<<" ";
        }
        cout<<endl;
        cout<<"PostOrder II: ";
        for(int & it : poii) {
            cout<<it<<" ";
        }
        cout<<endl<<endl;
        cout<<"LevelOrder :"<<endl;
        for(vector<int>& iter : lo) {
            cout<<"[";
            for(int& its : iter) {cout<<its<<" ";}
            cout<<"],"<<endl;
        }
        cout<<endl<<endl;

    }
};

int main() {
    Tree t;
    TreeNode* root = t.create();
    t.solve(root);
    delete root;
    return 0;
}

ssssshi

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int dat[N], lef[N], rig[N];
int head = -1, idx = -1;

void insert1(int root);

void goujian(int n)//构建节点 
{
    dat[++idx] = n;
    lef[idx] = -1;
    rig[idx] = -1;
    if (head=-1) {
        head = idx;
    } 
    else {
        insert1(head);
    }
}

void insert1(int root)//将节点插入 
{
    if (dat[root] < dat[idx]) {
        if (rig[root] == -1) rig[root] = idx;
        else insert1(rig[root]);
    } 
    else {
        if (lef[root] == -1) lef[root] = idx;
        else insert1(lef[root]);
    }
}
void cengxu(int root) {
    queue<int> q;
    q.push(head);
    while (!q.empty()) {
        root = q.front();
        cout << dat[root] << " ";
        q.pop();
        if (lef[root] != -1) q.push(lef[root]);
        if (rig[root] != -1) q.push(rig[root]);
    }
}

int main() {
    int n, a;
    cin >> n;
    while (n--) {
        cin >> a;
        goujian(a);
    }
    cengxu(head);
    return 0;
}
//9 50 70 30 80 40 20 60 10 90
//输入/50 /30 70 /20 40 60 80 /10 90/时(//内的顺序可随意改变)
/*所构造出的树
             50
       30          70
    20   40      60   80
10                          90
*/