二叉树的遍历、查找

一、二叉树的性质

1、非空二叉树的第n层上至多有2^(n-1)个元素。 2、深度为h的二叉树至多有2^h-1个结点。 3、满二叉树：所有终端都在同一层次，且非终端结点的度数为2。在满二叉树中若其深 度为h，则其所包含的结点数必为2^h-1。 4、完全二叉树：叶子节点只能出现在最下两层，最下层的叶子一定集中在左部连续的位 置。如果节点只有一个孩子，只可能是左孩子。 5、对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点 (如果有左右节点的话）。 6、每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。

二、存储结构 1、顺序存储：将数据结构存在一块固定的数组中。

#define LENGTH 100 typedef char datatype; typedef struct node{ datatype data; int lchild,rchild; int parent; }Node; Node tree[LENGTH]; int length; int root;

2、链式存储：二叉树通常以链式存储，定义如下：

typedef char datatype; typedef struct BitNode { datatype data; struct BitNode *lchild,*rchild; }BitNode,*BiTree;

三、二叉树的创建 为了能让每个节点确认是否有左右孩子，将二叉树中的每个节点的空指针引出一个虚节点，用“#”表示，构建出的二叉树为原二叉树的扩展二叉树，就可以做到一个遍历序列确定一棵二叉树了。

//按前序输入创建二叉树 void CreateBiTree(BiTree *T) { datatype data; scanf("%c",&data); if(ch=='#') T=NULL; else { *T=(BiTree)malloc(sizeof(BitNode)); //生成根结点 *T->data = data; //构造左子树 CreateBiTree(&(*T)->lchild); //构造右子树 CreateBiTree(&(*T)->rchild); } return 0; }

三、二叉树的遍历、 遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。 前序遍历：根节点->左子树->右子树 中序遍历：左子树->根节点->右子树 后序遍历：左子树->右子树->根节点

1、递归算法

//前序遍历 void PreOrder(BiTree T) { if(T==NULL) return; ptintf("%c",T->data); PreOrder(T->lchild)； PreOrder(T->rchild)； } //中序遍历 void InOrder(BiTree T) { if(T==NULL) return; InOrder(T->lchild)； ptintf("%c",T->data); InOrder(T->rchild)； } //后序遍历 void PostOrder(BiTree T) { if(T==NULL) return; PostOrder(T->lchild)； PostOrder(T->rchild)； ptintf("%c",T->data); }

2、非递归算法 <1>先序遍历：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元 素应为T，出栈，再先序遍历T的右子树。

void PreOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //访问根节点 printf("%c ",p->data); //遍历左子树 p = p->lchild; } else{ //退栈 p = stack.top(); stack.pop(); //访问右子树 p = p->rchild; } } }

<2>中序遍历：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。

void InOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //遍历左子树 p = p->lchild; } else{ //退栈，访问根节点 p = stack.top(); printf("%c ",p->data); stack.pop(); //访问右子树 p = p->rchild; } } }

<3>后序遍历：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。

//后序遍历(非递归) typedef struct BiTNodePost{ BiTree biTree; char tag; }BiTNodePost,*BiTreePost; void PostOrder2(BiTree T){ stack<BiTreePost> stack; //p是遍历指针 BiTree p = T; BiTreePost BT; //栈不空或者p不空时循环 while(p != NULL || !stack.empty()){ //遍历左子树 while(p != NULL){ BT = (BiTreePost)malloc(sizeof(BiTNodePost)); BT->biTree = p; //访问过左子树 BT->tag = 'L'; stack.push(BT); p = p->lchild; } //左右子树访问完毕访问根节点 while(!stack.empty() && (stack.top())->tag == 'R'){ BT = stack.top(); //退栈 stack.pop(); BT->biTree; printf("%c ",BT->biTree->data); } //遍历右子树 if(!stack.empty()){ BT = stack.top(); //访问过右子树 BT->tag = 'R'; p = BT->biTree; p = p->rchild; } } }

<4>层次遍历：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。

//层次遍历 void LevelOrder(BiTree T){ BiTree p = T; //队列 queue<BiTree> queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()){ //对头元素出队 p = queue.front(); //访问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL){ queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL){ queue.push(p->rchild); } } }

总的代码实现

#include<iostream> #include<stack> #include<queue> using namespace std; //二叉树结点 typedef struct BiTNode{ //数据 char data; //左右孩子指针 struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //按先序序列创建二叉树 int CreateBiTree(BiTree *T){ char data; //按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树 scanf("%c",&data); if(data == '#'){ *T = NULL; } else{ *T = (BiTree)malloc(sizeof(BiTNode)); //生成根结点 *T->data = data; //构造左子树 CreateBiTree(&(*T)->lchild); //构造右子树 CreateBiTree(&(*T)->rchild); } return 0; } //前序遍历 void PreOrder(BiTree T) { if(T==NULL) return; ptintf("%c",T->data); PreOrder(T->lchild)； PreOrder(T->rchild)； } //中序遍历 void InOrder(BiTree T) { if(T==NULL) return; InOrder(T->lchild)； ptintf("%c",T->data); InOrder(T->rchild)； } //后序遍历 void PostOrder(BiTree T) { if(T==NULL) return; PostOrder(T->lchild)； PostOrder(T->rchild)； ptintf("%c",T->data); } /* 先序遍历(非递归) 思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。 */ void PreOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //访问根节点 printf("%c ",p->data); //遍历左子树 p = p->lchild; } else{ //退栈 p = stack.top(); stack.pop(); //访问右子树 p = p->rchild; } }//while } /* 中序遍历(非递归) 思路：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。 先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。 */ void InOrder2(BiTree T){ stack<BiTree> stack; //p是遍历指针 BiTree p = T; //栈不空或者p不空时循环 while(p || !stack.empty()){ if(p != NULL){ //存入栈中 stack.push(p); //遍历左子树 p = p->lchild; } else{ //退栈，访问根节点 p = stack.top(); printf("%c ",p->data); stack.pop(); //访问右子树 p = p->rchild; } }//while } //后序遍历(非递归) typedef struct BiTNodePost{ BiTree biTree; char tag; }BiTNodePost,*BiTreePost; void PostOrder2(BiTree T){ stack<BiTreePost> stack; //p是遍历指针 BiTree p = T; BiTreePost BT; //栈不空或者p不空时循环 while(p != NULL || !stack.empty()){ //遍历左子树 while(p != NULL){ BT = (BiTreePost)malloc(sizeof(BiTNodePost)); BT->biTree = p; //访问过左子树 BT->tag = 'L'; stack.push(BT); p = p->lchild; } //左右子树访问完毕访问根节点 while(!stack.empty() && (stack.top())->tag == 'R'){ BT = stack.top(); //退栈 stack.pop(); printf("%c ",BT->biTree->data); } //遍历右子树 if(!stack.empty()){ BT = stack.top(); //访问过右子树 BT->tag = 'R'; p = BT->biTree; p = p->rchild; } }//while } //层次遍历 void LevelOrder(BiTree T){ BiTree p = T; //队列 queue<BiTree> queue; //根节点入队 queue.push(p); //队列不空循环 while(!queue.empty()){ //对头元素出队 p = queue.front(); //访问p指向的结点 printf("%c ",p->data); //退出队列 queue.pop(); //左子树不空，将左子树入队 if(p->lchild != NULL){ queue.push(p->lchild); } //右子树不空，将右子树入队 if(p->rchild != NULL){ queue.push(p->rchild); } } } int main() { BiTree T; CreateBiTree(T); printf("先序遍历：\n"); PreOrder(T); printf("\n"); printf("先序遍历(非递归)：\n"); PreOrder2(T); printf("\n"); printf("中序遍历：\n"); InOrder(T); printf("\n"); printf("中序遍历(非递归)：\n"); InOrder2(T); printf("\n"); printf("后序遍历：\n"); PostOrder(T); printf("\n"); printf("后序遍历(非递归)：\n"); PostOrder2(T); printf("\n"); printf("层次遍历：\n"); LevelOrder(T); printf("\n"); return 0; }

四、二叉树的查找

BiTree search_tree(BiTree t,datatype x){ if(!t) return NULL; if(t->data == x) return t; else { if(!search_tree(t->lchild,x)) return search_tree(t->rchild,x); } return t; }