鞍钢建设集团网站/杭州搜索引擎推广排名技术

（1）树

基本概念：
1.【根节点】：根节点是一个没有双亲结点的结点，一课树最多只能有一个根节点；
2.【结点】：树上面的所有数据都是结点，但结点不只包括数据，还包含指向子树的分支（地址）；
3.【结点的度】：结点拥有子树或分支的个数；
4.【树的度】：树中各结点的最大值；
5.【结点的层数】：根结点的层数为0，其他结点的层数等于其父结点的层数加1；
6.【树的深度】：树中所有结点层数的最大值；
7.【树的高度】：数的深度加1；
8.【叶子结点】：没有孩子结点的结点；

（2）二叉树

【概念】：二杈树是树型结构的一种特殊形式。其特点：所有结点的度都小于等于2.
【区别】：二杈树的子树有左右子树之分，次序不可颠倒，因此二叉树是有序树；

两种特殊的二杈树：
1.【完全二杈树】：一课高度为h的二杈树，除最后一层以外的其他所有层上的结点数都达到最大值，而最后一层的所有结点分布在该层最左边的连续位置上。
2.【满二叉树】：每一层的结点数都达到最大值。所有分支结点的度都为2，叶子结点都出现在最后一层。高度为h的二叉树有2^h-1个结点。即：二叉树中的每个结点恰好有两个孩子结点且所有叶子结点在同一层。

二叉树的遍历：
前序遍历：根节点----->左子树----->右子树

void preorder(struct node* p1)	//先序遍历：根->左->右
{if (p1 != NULL){printf("%d\n", p1->data);preorder(p1->left);preorder(p1->right);}
}

中序遍历：左子树----->根节点----->右子树

void inorder(struct node* p2)		//中序遍历：左->根->右。
{if (p2 != NULL){inorder(p2->left);printf("%d\n", p2->data);inorder(p2->right);}
}

后序遍历：左子树----->右子树----->根节点

void postorder(struct node* p3)		//后序遍历：左->右->根。
{if (p3 != NULL){postorder(p3->left);postorder(p3->right);printf("%d\n", p3->data);}
}

创建一个简单的二叉树并遍历，代码实现：

#include<iostream>
#include<cstdlib>
using namespace std;
struct node
{int data;struct node* left;struct node* right;
};
void preorder(struct node* p1)	//先序遍历：根->左->右
{if (p1 != NULL){printf("%d\n", p1->data);preorder(p1->left);preorder(p1->right);}
}
void inorder(struct node* p2)		//中序遍历：左->根->右。
{if (p2 != NULL){inorder(p2->left);printf("%d\n", p2->data);inorder(p2->right);}
}
void postorder(struct node* p3)		//后序遍历：左->右->根。
{if (p3 != NULL){postorder(p3->left);postorder(p3->right);printf("%d\n", p3->data);}
}
int main()
{struct node n1, n2, n3, n4;n1.data = 5;n2.data = 6;n3.data = 7;n4.data = 8;n1.left = &n2;n1.right = &n3;n2.left = &n4;n2.right = NULL;n4.left = NULL;n4.right = NULL;n3.left = NULL;n3.right = NULL;cout << "先序遍历：" << endl;preorder(&n1);cout << "中序遍历：" << endl;inorder(&n1);cout << "后序遍历：" << endl;postorder(&n1);return 0;
}