二叉查找树：
struct binary_search_node//二叉查找树结点结构
{
int key;
binary_search_node *left;
binary_search_node *right;
binary_search_node *p;
binary_search_node(int k=0,binary_search_node *l=NULL,
binary_search_node *r=NULL,binary_search_node* pa=NULL)
{
key=k;
left=l;
right=r;
p=pa;
}
};
void inorder_tree_walk(binary_search_node *x)
//中序遍历，按顺序输出关键字，时间复杂度O(n)
{
if(x!=NULL)
{
inorder_tree_walk(x->left);
cout<<x->key<<" ";//如果这里用空格，再主程序中记得用endl清空缓存，否则无法显示
inorder_tree_walk(x->right);
}
}
void inorder_tree_walk_no_recurse(binary_search_node *x)
//非递归中序遍历，使用栈
{
stack<binary_search_node *> s;//存储结点指针！ 不是key
while(x!=NULL||!s.empty())
{
while(x!=NULL)
{
s.push(x);
x=x->left;
}//此时x为NULL
if(!s.empty())
{
x=s.top();
cout<<x->key<<" ";
s.pop();
x=x->right;
}
}
}
void inorder_tree_walk_no_recurse_no_stack(binary_search_node *x)
//非递归中序遍历，不使用栈
{
binary_search_node *pre;
while(x!=NULL)
{
if(x->left==NULL)//如果左儿子为空，直接输出，并向右遍历
{
cout<<x->key<<" ";
x=x->right;
}
else//如果左儿子不为空，找其前驱结点，即左子树的最右结点
{
pre=x->left;
while(pre->right!=NULL&&pre->right!=x)
pre=pre->right;
if(pre->right==NULL)
//如果前驱的右儿子为空，表明还没访问过左子树，将前驱的右儿子设为自己，并向左遍历
{
pre->right=x;
x=x->left;
}
else
//如果前驱的右儿子为自己，表明左子树已经访问过了，则将前驱的右儿子置空，输出结点，并向右遍历
{
pre->right=NULL;
cout<<x->key<<" ";
x=x->right;
}
}
}
}
binary_search_node* tree_search(binary_search_node *x,int k)
//在x为根的树中查找关键字k，返回包含k的结点的指针，没有则返回NULL，O(h)
{
if(x==NULL || k==x->key)
return x;
if(k<x->key)
return tree_search(x->left,k);
else
return tree_search(x->right,k);
}
binary_search_node* iteractive_tree_search(binary_search_node *x,int k)
//查找关键字k的非递归版本
{
while(x!=NULL && k!=x->key)
{
if(k<x->key)
x=x->left;
else
x=x->right;
}
return x;
}
binary_search_node* tree_minimum(binary_search_node *x)
//寻找最小结点 O(h)
{
while(x->left!=NULL)
x=x->left;
return x;
}
binary_search_node* tree_maximum(binary_search_node *x)
//寻找最大结点
{
while(x->right!=NULL)
x=x->right;
return x;
}
binary_search_node* tree_successor(binary_search_node *x)
//寻找后继结点，没有则返回NULL,O(h)
{
if(x->right!=NULL)//如果x的右子树非空，后继即右子树的最左结点
return tree_minimum(x->right);
binary_search_node* y=x->p;
//如果x的右子树为空，向上查找，直到遇到某个是其父结点的左儿子的结点为止
while(y!=NULL && x==y->right)
{
x=y;
y=y->p;
}
return y;
}
binary_search_node* tree_predecessor(binary_search_node *x)
//寻找前驱结点
{
if(x->left!=NULL)
return tree_maximum(x->left);
binary_search_node* y=x->p;
while(y!=NULL && x==y->left)
{
x=y;
y=y->p;
}
return y;
}
binary_search_node* tree_insert(binary_search_node *x,binary_search_node *z)
//将结点z插入树中，返回插入后的根结点，O(h)
{
binary_search_node *y=NULL;
binary_search_node *root=x;
while(x!=NULL)
{
y=x;//y始终指向x的父结点
if(z->key<x->key)
x=x->left;
else
x=x->right;
}
z->p=y;
if(y==NULL)//树为空的情况
root=z;
else if(z->key<y->key)
y->left=z;
else
y->right=z;
return root;
}
binary_search_node* tree_delete(binary_search_node *x,binary_search_node *z)
//从根为x的树中删除结点z，O(h)分三种情况
//(1)z没有子女 (2)z只有一个子女 (3)z有两个子女
{
binary_search_node *q,*y,*root;
root=x;
if(z->left==NULL || z->right==NULL)//1和2
y=z;
else//3
y=tree_successor(z);
if(y->left!=NULL)
q=y->left;
else
q=y->right;
if(q!=NULL)//2，3
q->p=y->p;
if(y->p==NULL)//1,2,3删除的是根结点的情况
root=q;
else if(y==y->p->left)//1,2,3
y->p->left=q;
else//1,2,3
y->p->right=q;
if(y!=z)//3,用z后继的内容替换z的内容
z->key=y->key;
return root;
}
已知树的前序和中序，求后序：
#include<stdio.h>
#include<string.h>
//二叉树结点的描述
typedef struct BinaryTreeNode
{
char data;
struct BinaryTreeNode *lchild, *rchild; //左右孩子
}BinaryTreeNode,*BinaryTree;
inline BinaryTreeNode* ConstructCore(char *startPreorder, char *endPreorder, char *startInorder, char *endInorder)
{
//前序遍历序列的第一个字符是根节点的值
char rootValue = startPreorder[0];
BinaryTreeNode* root = new BinaryTreeNode();
root->data = rootValue;
root->lchild = root->rchild = NULL;
if(startPreorder == endPreorder)
{
if(startInorder == endInorder && *startPreorder== *startInorder)
return root;
}
//在中序遍历中找到根节点的值
char *rootInorder = startInorder;
while(rootInorder <= endInorder && *rootInorder != rootValue)
rootInorder++;
int leftLength = rootInorder - startInorder;
char *leftPreorderEnd = startPreorder + leftLength;
if(leftLength > 0)
{
//构建左子树
root->lchild = ConstructCore(startPreorder+1, leftPreorderEnd, startInorder, rootInorder-1);
}
if(leftLength < endPreorder - startPreorder)
{
//构建右子树
root->rchild = ConstructCore(leftPreorderEnd+1, endPreorder, rootInorder+1, endInorder);
}
return root;
}
//分别在前序遍历和中序遍历的序列中确定左、右子树的子序列
inline BinaryTreeNode* Construct(char *preorder, char *inorder, int length)
{
if(preorder == NULL || inorder == NULL || length<=0)
return NULL;
return ConstructCore(preorder, preorder+length-1, inorder, inorder+length-1);
}
//后序遍历
inline void PostOrder(BinaryTreeNode *root)
{
if(root==NULL)
return ;
PostOrder(root->lchild); //递归调用，前序遍历左子树
PostOrder(root->rchild); //递归调用，前序遍历右子树
printf("%c", root->data); //输出数据
}
//释放二叉树
inline void DeleteBinaryTree(BinaryTree root)
{
if(root)
{
DeleteBinaryTree(root->lchild); //释放左子树
DeleteBinaryTree(root->rchild); //释放右子树
delete root; //释放根结点
}
}
int main(void)
{
int length;
char preorder[27],inorder[27];
while(scanf("%s",preorder)!=EOF)
{
scanf("%s",inorder);
length = strlen(preorder);
BinaryTreeNode* root = Construct(preorder, inorder, length);
PostOrder(root);
printf("\n");
DeleteBinaryTree(root);
}
return 0;
}