erchashu.rar_二叉树 程序_二叉树的操作_二叉树的遍历_二叉树遍历

#include "Tree.h" #include<malloc.h> #include <iostream> using namespace std; /*******************************************/ /* 初始化构造一棵空的二叉树T */ /*******************************************/ int InitBiTree(BiTree &T) { T = new BiTNode; if( !T ) { cout<<"构造空二叉树时出错!!!"<<endl; return 0; } T->data =NULL; T->lchild =NULL; T->rchild =NULL; return 1; } /*******************************************/ /* 先序法创建二叉链表 */ /*******************************************/ void CreateBiTree( BiTree &T ) { char ch; cin >> ch; if( ch == '0' ) T = NULL; else { T = ( BiTNode* )malloc( sizeof( BiTNode ) ); //分配空间 T->data = ch; //生成根结点 CreateBiTree( T ->lchild ); //构建左子树 CreateBiTree( T ->rchild ); //构建右子树 } } /*******************************************/ /* 中序递归法遍历二叉树 */ /*******************************************/ void InOrderTraverse( BiTree T ) { if ( T ) { InOrderTraverse( T->lchild ); //中序遍历左子树 cout << "\t" << T->data; //访问根结点 InOrderTraverse( T->rchild ); //中序遍历右子树 } } /*******************************************/ /* 求一棵树的高度 */ /*******************************************/ int BiTreeDepth( BiTree T ) { int lh , rh ; if( NULL == T ) { return 0 ; } else { lh = BiTreeDepth( T->lchild ) ; //递归调用计算深度 rh = BiTreeDepth( T->rchild ) ; return ( lh > rh ? lh : rh ) + 1 ; } } /*******************************************/ /* 递归法求二叉树的叶子结点的数目 */ /*******************************************/ int BiTreeLeaves( BiTree T ) { if( T == NULL ) return 0; //若二叉树是空树，则返回0 else if( ( T->lchild == NULL) && ( T->rchild == NULL ) ) return 1; // 若二叉树的左孩子和右孩子为空，则返回1 else //若二叉树的左孩子或右孩子不为空 return BiTreeLeaves(T->lchild) + BiTreeLeaves(T->rchild); //递归求T的左,右孩子的叶子结点数目，并返回总的叶子结点数目 } /*******************************************/ /* 前序非递归遍历二叉树 */ /*******************************************/ void PreOrderTraverse( BiTree T ) //非递归法用到栈 { BiTree p = T; Stack s; s.top=0; cout << "输出前序遍历序列: " << endl; while( p || s.top > 0 ) { if( p ) { cout << "\t" << p->data; //访问根结点 s.data[s.top++] = p; //根指针进栈 p = p->lchild; //遍历左子树 } else //左子树为空就访问右子树 { p = s.data[--s.top]; //根指针退栈 p = p->rchild; //遍历右子树 } } cout << endl << endl; } /*******************************************/ /* 中序非递归遍历二叉树 */ /*******************************************/ void InOrderTraverse2( BiTree T ) { BiTree p = T; Stack s; s.top=0; cout << "输出中序遍历序列: " << endl; while( p || s.top > 0 ) { if( p ) { s.data[s.top++] = p; //根指针进栈 p = p ->lchild; //遍历左子树 } else { p = s.data[--s.top]; //根指针退栈 cout << "\t" << p->data; //访问根结点 p = p->rchild; //遍历右子树 } } cout << endl << endl; } /*******************************************/ /* 后序非递归遍历二叉树 */ /*******************************************/ void PostOrderTraverse( BiTree T ) { Stack s; s.top = -1; cout << "输出后序遍历序列: " << endl; while( T != NULL || s.top != -1 ) { while( T ) { s.top++; s.flag[s.top] = 0; s.data[s.top] = T; T = T->lchild; } while( s.top >= 0 && s.flag[s.top] == 1 ) { T = s.data[s.top]; cout << "\t" << T->data; s.top--; } if( s.top >= 0 ) { T = s.data[s.top]; s.flag[s.top] = 1; T = T->rchild; } else { T = NULL; } } cout << endl << endl; } /*******************************************/ /* 按照层次遍历二叉树 */ /*******************************************/ void LevelOrderTraverse( BiTree T ) //用到队列 { Queue q; q.data[0] = T; q.front = 0; q.rear = 1; cout << "输出层次遍历序列: " << endl; while( q.front < q.rear ) { if( q.data[q.front] ) { cout << "\t" << q.data[q.front]->data; q.data[q.rear++] = q.data[q.front]->lchild; q.data[q.rear++] = q.data[q.front]->rchild; q.front++; } else { q.front++; } } cout << endl << endl; }