ctree

c语言实现树（二叉树）

树的理解

树是一种非线性的数据结构，它是由 n (n>=0)个有限结点组成的一个具有层次关系的集合。 • 结点的度：一个结点含有的子树个数（结点下的分支） 如结点A的度为5； • 树的度：一棵树中最大的结点的度 如上树的度为5； • 结点的层次：根是第1层，根的子节点所在层是第2层，如此递增； • 树的高(深)度：最大的结点的层次 如上树的高(深)度是4； • 叶子结点：度为0的结点（没有子树） 如结点 N，O； • 双亲结点：如A是B，C，D，E，F的双亲结点； • (孩)子结点：如B，C，D，E，F是A的(孩)子结点； • 兄弟结点：具有相同双亲结点的子节点 如G，H； • 堂兄弟结点：双亲在同一层的结点互为堂兄弟结点 如H，I； • 非终端结点/分支结点：度不为0的结点 如C，D，E…； • 结点的祖先：从根节点所经分支上的所有结点 如A是所有结点的祖先；

二叉树插入节点

#include<stdio.h>
#include<string.h>
#include<stdlib.h>  //左小右大 
struct Node{
	int data;
	struct Node* left;
	struct Node* right;
};
struct Node*GetNewnode(int data)
{
	struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
	newnode->data=data;
	newnode->left=NULL;
	newnode->right=NULL;
 } 
struct Node*Insert(struct Node* root,int data)  //我们想知道的是基于原有的root，插入一个data得到的新地址 
   	if(root==NULL){
   		root=GetNewnode(data);
	   }
	else if(data<=root->data){
		root->left=Insert(root->left,data);
	}
	else {
		root->right=Insert(root->right,data);
	}
	return root;
}
bool Search(struct Node* root,int data)
{
	if(root==NULL) return false;
	else if(root->data==data) return true;
	else if(data<=root->data) return Search(root->left,data);
	else return Search(root->right,data);
}

树的高度

#include<stdio.h>
#include<string.h>
struct Node{
	int data;
	struct Node* left;
	struct Node* right;
};
struct Node* root;
int max(int a,int b){
	if(a>=b) return a;
	else return b;
}
int Height(struct Node*root)
{
	if(root==NULL)
	{
		return -1;
	}
	return max(Height(root->left),Height(root->right))+1;
	
 }

寻找最小值

#include<stdio.h>
#include<string.h>
#include<stdlib.h> 
struct Node{
	int data;
	struct Node* left;
	struct Node* right;
};
struct Node* root;
int Min(struct Node* root)                                          //找最小值函数
{
	if(root==NULL)
	{
		printf("tree is empty！"); 
		return -1;                                                     //结束条件
	}
	else if(root->left==NULL){
	 return root->data;                                       //不断向左递归
	}
	else return Min(root->left); 
}
struct Node*GetNewnode(int data)
{
	struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
	newnode->data=data;
	newnode->left=NULL;
	newnode->right=NULL;
 } 
struct Node*Insert(struct Node* root,int data){  址 
   	if(root==NULL){
   		root=GetNewnode(data);
	   }
	else if(data<=root->data){
		root->left=Insert(root->left,data);
	}
	else {
		root->right=Insert(root->right,data);
	}
	return root;
}
int main()
{
	root=NULL;
    root=Insert(root,2);
    root=Insert(root,3);
    root=Insert(root,4);
    root=Insert(root,5);
    printf("%d",Min(root));
}

遍历

#include<iostream>
#include<queue>
using namespace std;

struct Node {
	char data;
	Node *left;
	Node *right;
};

// Function to print Nodes in a binary tree in Level order
void LevelOrder(Node *root) {
	if(root == NULL) return;
	queue<Node*> Q;
	Q.push(root);  
	//while there is at least one discovered node
	while(!Q.empty()) {
		Node* current = Q.front();
		Q.pop(); // removing the element at front
		cout<<current->data<<" ";
		if(current->left != NULL) Q.push(current->left);
		if(current->right != NULL) Q.push(current->right);
	}
}
// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
	if(root == NULL) {
		root = new Node();
		root->data = data;
		root->left = root->right = NULL;
	}
	else if(data <= root->data) root->left = Insert(root->left,data);
	else root->right = Insert(root->right,data);
	return root;
}

int main() {
	/*Code To Test the logic
	  Creating an example tree
	            M
			   / \
			  B   Q
			 / \   \
			A   C   Z
    */
	Node* root = NULL;
	root = Insert(root,'M'); root = Insert(root,'B');
	root = Insert(root,'Q'); root = Insert(root,'Z'); 
	root = Insert(root,'A'); root = Insert(root,'C');
	//Print Nodes in Level Order. 
	LevelOrder(root);
}