- /*******************************************************
- DS_BinaryTree
- By_h4breeze
- Date:Apr.27,2012
- *******************************************************/
- #include<iostream>
- using namespace std;
- typedef struct BiTreeNode{ //二叉树节点结构：数据域，左、右子树域
- char elem;
- struct BiTreeNode *lnode,*rnode;
- }BiTreeNode,*Tree;
- void CreatTree(Tree *T) //创建一个二叉树节点
- {
- char elem;
- cin >> elem;
- if(elem == '0') //以0作为叶子标记
- *T = NULL; //如果输入0，此二叉树为空，无。
- else
- {
- *T = (BiTreeNode *)malloc(sizeof(BiTreeNode)); //给该节点分配空间
- (*T)->elem = elem; //(*T)括号：结构成员引用符 优先于 间接符号，且，可读性强
- CreatTree( &((*T)->lnode) ); //递归过程：给当前节点数据域赋值后该递归创建左右子树了，顺序为先左后右
- CreatTree( &((*T)->rnode) ); //形参为指针，传递地址
- }
- }
- void visit(char elem,int level) // 输出位于第level层的元素
- {
- cout << elem << " is at " << level << " level" << endl;
- }
- void PreOrder(Tree T,int level) //先序：根-左-右
- {
- if(T)
- {
- visit(T->elem,level); //输出位于第level层的元素，然后递归遍历
- PreOrder(T->lnode,level + 1); //递归遍历过程：先递归遍历左子树，再递归遍历右子树
- PreOrder(T->rnode,level + 1);
- }
- }
- void FrontOrder(Tree T,int level) //中序：左-根-右
- {
- if(T)
- {
- FrontOrder(T->lnode,level + 1);
- visit(T->elem,level); //输出位于第level层的元素，然后递归遍历
- FrontOrder(T->rnode,level + 1); //递归遍历过程：先递归遍历左子树，再递归遍历右子树
- }
- }
- void BackOrder(Tree T,int level) //后序：左-右-根
- {
- if(T)
- {
- BackOrder(T->lnode,level + 1);
- BackOrder(T->rnode,level + 1); //递归遍历过程：先递归遍历左子树，再递归遍历右子树
- visit(T->elem,level); //输出位于第level层的元素，然后递归遍历
- }
- }
- int main(void)
- {
- int level = 1;
- Tree T = NULL;
- CreatTree(&T);
- cout << "\tPreOrder" << endl;
- PreOrder(T,level); //从第一层开始遍历树
- cout << "\tFrontOrder" << endl;
- FrontOrder(T,level);
- cout << "\tBackOrder" << endl;
- BackOrder(T,level);
- return 0;
- }
- /**************************************************************************
- 1.二叉树的性质
- 性质1 二叉树第i层上的结点数目最多为power(2,i-1)(i≥1)。
- 性质2 深度为k的二叉树至多有power(2,k)-1个结点(k≥1)。
- 性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
- 性质4 具有n个结点的完全二叉树的深度为log(n)+1或log(n+1);
- 2.特殊二叉树
- 1、满二叉树(FullBinaryTree)
- 一棵深度为k且有2k-1个结点的二又树称为满二叉树。
- 满二叉树的特点：
- （1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
- （2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
- 2、完全二叉树(Complete BinaryTree)
- 若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
- 特点：
- （1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
- （2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
- （3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
- 3.二叉树的遍历
- 3.1．三种遍历的命名
- 根据访问结点操作发生位置命名：
- ① NLR：前序遍历(PreorderTraversal亦称(先序遍历))
- ——访问结点的操作发生在遍历其左右子树之前。
- ② LNR：中序遍历(InorderTraversal)
- ——访问结点的操作发生在遍历其左右子树之中(间)。
- ③ LRN：后序遍历(PostorderTraversal)
- ——访问结点的操作发生在遍历其左右子树之后。
- 注意：
- 由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
- 遍历算法
- 1．中序遍历的递归算法定义：
- 若二叉树非空，则依次执行如下操作：
- (1)遍历左子树；
- (2)访问根结点；
- (3)遍历右子树。
- 2．先序遍历的递归算法定义：
- 若二叉树非空，则依次执行如下操作：
- (1) 访问根结点；
- (2) 遍历左子树；
- (3) 遍历右子树。
- 3．后序遍历得递归算法定义：
- 若二叉树非空，则依次执行如下操作：
- (1)遍历左子树；
- (2)遍历右子树；
- (3)访问根结点。
- ***************************************************************************/