(B C)
(D E) (F G)
以这课树为例
#include <stdio.h>
#include <stdlib.h>
typedef char Elem
typedef struct Node
{
Elem data
struct Node *pLchild
struct Node *pRchild
}BTreeNode, *BTree
BTree CreateBTree(BTree T, Elem *str)//创建二叉树
{
static int i = 0
if ('0' == str[i])
{
T = NULL
}
else
{
T = (BTree) malloc (sizeof(BTreeNode))
T->data = str[i++]
T->pLchild = CreateBTree(T->pLchild, str)
i++
T->pRchild = CreateBTree(T->pRchild, str)
}
return T
}
void PostTraverseBTree(BTree T)//后序
{
if (NULL != T)
{
PostTraverseBTree(T->pLchild)
PostTraverseBTree(T->pRchild)
printf("%c ", T->data)
}
}
void InTraverseBTree(BTree T)//中序
{
if (NULL != T)
{
InTraverseBTree(T->pLchild)
printf("%c ", T->data)
InTraverseBTree(T->pRchild)
}
}
void PreTraverseBTree(BTree T)//先序
{
if (NULL != T)
{
printf("%c ", T->data)
PreTraverseBTree(T->pLchild)
PreTraverseBTree(T->pRchild)
}
}
int main(void)
{
BTree T = NULL
Elem str[] = "ABD00E00CF00G00"
T = CreateBTree(T, str)
printf("\n\n")
printf("先序遍历:\n")
PreTraverseBTree(T)
printf("\n\n")
printf("中序遍历:\n")
InTraverseBTree(T)
printf("\n\n")
printf("后序遍历:\n")
PostTraverseBTree(T)
printf("\n\n")
}
从根节点到叶子结点一次经过的结点形成树的一条路径，最长路径的长度为树的深度。根节点的深度为1。
解体思路：
1.如果根节点为空，则深度为0，返回0，递归的出口。
2.如果根节点不为空，那么深度至少为1，然后我们求他们左右子树的深度，
3.比较左右子树深度值，返回较大的那一个
4.通过递归调用
#include<iostream>#include<stdlib.h>
using namespace std
struct BinaryTreeNode
{
int m_nValue
BinaryTreeNode* m_pLeft
BinaryTreeNode* m_pRight
}
//创建二叉树结点
BinaryTreeNode* CreateBinaryTreeNode(int value)
{
BinaryTreeNode* pNode=new BinaryTreeNode()
pNode->m_nValue=value
pNode->m_pLeft=NULL
pNode->m_pRight=NULL
return pNode
}
//连接二叉树结点
void ConnectTreeNodes(BinaryTreeNode* pParent,BinaryTreeNode* pLeft,BinaryTreeNode* pRight)
{
if(pParent!=NULL)
{
pParent->m_pLeft=pLeft
pParent->m_pRight=pRight
}
}
//求二叉树深度
int TreeDepth(BinaryTreeNode* pRoot)//计算二叉树深度
{
if(pRoot==NULL)//如果pRoot为NULL，则深度为0，这也是递归的返回条件
return 0
//如果pRoot不为NULL，那么深度至少为1，所以left和right=1
int left=1
int right=1
left+=TreeDepth(pRoot->m_pLeft)//求出左子树的深度
right+=TreeDepth(pRoot->m_pRight)//求出右子树深度
return left>right?left:right//返回深度较大的那一个
}
void main()
{
// 1
// / \
// 2 3
// /\ \
// 4 5 6
// /
// 7
//创建树结点
BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1)
BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2)
BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3)
BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4)
BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5)
BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6)
BinaryTreeNode* pNode7 = CreateBinaryTreeNode(7)
//连接树结点
ConnectTreeNodes(pNode1, pNode2, pNode3)
ConnectTreeNodes(pNode2, pNode4, pNode5)
ConnectTreeNodes(pNode3, NULL, pNode6)
ConnectTreeNodes(pNode5, pNode7, NULL )
int depth=TreeDepth(pNode1)
cout<<depth<<endl
system("pause")
}
出处：http://www.cnblogs.com/xwdreamer
int pp(char *a, char *b, int l){
int i
for (i=0i<li++)
{
if (b[i] == a[0])
break
}
if (l == i)
return 0
pp(a+1, b, i)
pp(a+i+1, b+i+1, l-i-1)
printf("%c", b[i])
return 0
}
int main()
{
char a[32]
char b[32]
int l
printf("请输入前序、中序遍历结果：")
scanf("%s %s", a, b)
l = strlen(b)
if (l != strlen(a))
return 1
printf("后序遍历结果是：")
pp(a, b, l)
printf("\n")
return 0
}
