二叉树性质:度为0的节点比度为2的节点多一个。
解释:度为1的节点均可忽略;度为2的节点就相当于分割点,而度为0的节点就相当于线段;不分割时即有一条线段,当每多一个分割点时,线段也就相应会多一个。
二叉树分类(国际版):
- 完全二叉树(可编号):设二叉树的深度为 h,除第 h 层外,其它各层 (1~h-1) 的节点数都达到最大个数,第 h 层所有的节点都连续集中在最左边
- 满二叉树
- 完美二叉树
二叉树可用广义表进行表示:A(B(D, E), C(F,)) 或 1(2(4, 5), 3(6,))(完全二叉树)
深搜遍历(栈或递归):
- 前序遍历
- 中序遍历
- 后序遍历
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
//结构定义:链表节点
typedef struct Node {
int data;
Node *lchild, *rchild;
} Node;
//结构定义:树
typedef struct Tree {
Node *root;
int length;
} Tree;
//结构操作
Node *getNewNode(int val);
Tree *getNewTree();
void clear_node(Node *node);
void clear_tree(Tree *tree);
Node *insert_node(Node *node, int val, int *flag);
int insert(Tree *tree, int val);
void output_node(Node *node);
void output(Tree *tree);
void preorder_node(Node *node);
void preorder(Tree *tree);
void inorder_node(Node *node);
void inorder(Tree *tree);
void postorder_node(Node *node);
void postorder(Tree *tree);
int main() {
srand(time(0));
#define MAX_N 10
Tree *tree = getNewTree();
for (int i = 0; i < MAX_N; i++) {
int val = rand() % 100;
insert(tree, val);
output(tree);
}
preorder(tree);
inorder(tree);
postorder(tree);
#undef MAX_N
clear_tree(tree);
return 0;
}
//结构操作:获得一个新节点
Node *getNewNode(int val) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = val;
node->lchild = node->rchild = NULL;
return node;
}
//结构操作:获得一棵新树
Tree *getNewTree() {
Tree *tree = (Tree *)malloc(sizeof(Tree));
tree->root = NULL;
tree->length = 0;
return tree;
}
//结构操作:释放一个节点
void clear_node(Node *node) {
if (node == NULL) return;
clear_node(node->lchild);
clear_node(node->rchild);
free(node);
return;
}
//结构操作:销毁树
void clear_tree(Tree *tree) {
if (tree == NULL) return;
clear_node(tree->root);
free(tree);
return;
}
//结构操作:插入元素的递归操作(排序二叉树)
Node *insert_node(Node *node, int val, int *flag) {
if (node == NULL) {
*flag = 1;
return getNewNode(val);
}
if (val == node->data) return node;
if (val < node->data) node->lchild = insert_node(node->lchild, val, flag);
else node->rchild = insert_node(node->rchild, val, flag);
return node;
}
//结构操作:插入一个元素
int insert(Tree *tree, int val) {
if (tree == NULL) return 0;
int flag = 0;
tree->root = insert_node(tree->root, val, &flag);
tree->length += flag;
return flag;
}
//结构操作:输出该树的递归操作
void output_node(Node *node) {
if (node == NULL) return;
printf("%d", node->data);
if (node->lchild == NULL && node->rchild == NULL) return;
printf("(");
output_node(node->lchild);
printf(", ");
output_node(node->rchild);
printf(")");
return;
}
//结构操作:用广义表的形式输出该树
void output(Tree *tree) {
if (tree == NULL) return;
printf("tree(%d): ", tree->length);
output_node(tree->root);
printf("\n");
return;
}
//结构操作:前序遍历的递归操作
void preorder_node(Node *node) {
if (node == NULL) return;
printf("%d ", node->data);
preorder_node(node->lchild);
preorder_node(node->rchild);
return;
}
//结构操作:用前序遍历的方式输出所有元素
void preorder(Tree *tree) {
if (tree == NULL) return;
printf("preorder: ");
preorder_node(tree->root);
printf("\n");
return;
}
//结构操作:中序遍历的递归操作
void inorder_node(Node *node) {
if (node == NULL) return;
inorder_node(node->lchild);
printf("%d ", node->data);
inorder_node(node->rchild);
return;
}
//结构操作:用中序遍历的方式输出所有元素
void inorder(Tree *tree) {
if (tree == NULL) return;
printf("inorder: ");
inorder_node(tree->root);
printf("\n");
return;
}
//结构操作:后序遍历的递归操作
void postorder_node(Node *node) {
if (node == NULL) return;
postorder_node(node->lchild);
postorder_node(node->rchild);
printf("%d ", node->data);
return;
}
//结构操作:用后序遍历的方式输出所有元素
void postorder(Tree *tree) {
if (tree == NULL) return;
printf("postorder: ");
postorder_node(tree->root);
printf("\n");
return;
}
原文地址:http://www.cnblogs.com/Kelvin-Wu/p/16795300.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性