初学二叉搜索树

初学二叉搜索树

文章目录

前言一、二叉搜索树的前序遍历，中序遍历，后序遍历，层次遍历

---

前言

二叉搜索树的前序遍历，中序遍历，后序遍历，层次遍历以及求二叉树的最大深度

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、二叉搜索树的前序遍历，中序遍历，后序遍历，层次遍历

#include 
using namespace std;
typedef struct node{//定义结点 
	int data;//当前结点的值 
	struct node* left;//左结点 
	struct node* right;//右结点 
}Node; 

typedef struct{//定义一颗树 
	Node *root;//树的根结点 
}Tree;
void insert(Tree *tree,int value){//创建一颗二叉树 
	Node* node =(Node *)malloc(sizeof(Node));//先创建一颗结点 
	node->data=value;//将插入的值放入结点 
	node->left=NULL;//左子树设为空 
	node->right=NULL;//右子树设为空 
	if(tree->root==NULL){//如果树的根结点为空 
		tree->root=node;//将树的根结点指向这个结点 
	}else{
		Node* temp=tree->root;//创建一个树的根节点的一个临时结点 
		while(temp!=NULL){//如果不为空 
			if(valuedata){//如果当前结点的值小于根节点的值 
				if(temp->left==NULL){//如果根节点的左子树为空 
					temp->left=node;//就直接指向这个结点  
					return;//退出循环 
				}else{
					temp=temp->left;//不为空就继续向左寻找 
				}
			}else{//如果当前结点的值大于根节点的值
				if(temp->right==NULL){//如果根节点的右子树为空 
					temp->right=node;//就直接指向这个结点  
					return;//退出循环 
				}else{
					temp=temp->right;//不为空就继续向右寻找
				}
			}
		}
	}
}
void preorder(Node *node){//树的先序遍历 
	if(node!=NULL){
		printf("%d ",node->data);
		preorder(node->left);
		preorder(node->right);
	}
}
void midorder(Node *node){//树的中序遍历 
	if(node!=NULL){
		midorder(node->left);
		printf("%d ",node->data);
		midorder(node->right);
	}
}
void backorder(Node *node){//树的后序遍历 
	if(node!=NULL){
		backorder(node->left);
		backorder(node->right);
		printf("%d ",node->data);
	}
}
void bfs(Node* root)//bfs也就是树的层次遍历 
{
	queue q;
    //树为空，直接返回
    if (root == NULL)
    {
        return;
    }
    //先将根节点入队
    q.push(root);
    while (!q.empty())
    {
        //出队保存队头并访问
        Node* front = q.front();
        printf("%d ", front->data);
        q.pop();
        //将出队结点的左子树根入队
        if (front->left)
           q.push(front->left);
        //将出队结点的右子树根入队
        if (front->right)
            q.push(front->right);
    }
}

int dfs(Node *root){//dfs找出树的深度 
	if(root==NULL) return 0;
	return max(dfs(root->left),dfs(root->right))+1;
}
int main()
{
   int arr[7]={6,3,8,2,5,1,7};
   Tree tree;
   tree.root=NULL;
   for(int i=0;i<7;i++){
   	insert(&tree,arr[i]);//插入结点 
   }
   preorder(tree.root);//树的先序遍历 
   puts(" ");
   midorder(tree.root);//树的中序遍历 
   puts(" ");
   backorder(tree.root);//树的后序遍历 
   puts(" ");
   bfs(tree.root);//树的层次遍历 
   puts(" ");
   cout< 
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/5714355.html