本文目录一览：
请问C语言如何创建二叉树？？？？
创建二叉树的源程序如下：
#include cstdlib
#include stdio.h
typedef struct node
{ //树的结点
int data;
struct node* left;
struct node* right;
} Node;
typedef struct
{ //树根
Node* root；
} Tree;
void insert(Tree* tree, int value)//创建树
{
Node* node=(Node*)malloc(sizeof(Node));//创建一个节点
node-data = value;
node-left = NULL;
node-right = NULL;
if (tree-root == NULL)//判断树是不是空树
{
tree-root = node;
}
else
{//不是空树
Node* temp = tree-root;//从树根开始
while (temp != NULL)
{
if (value temp-data)//小于就进左儿子
{
if (temp-left == NULL)
{
temp-left = node;
return;
}
else
{//继续判断
temp = temp-left;
}
}
else {//否则进右儿子
if (temp-right == NULL)
{
temp-right = node;
return;
}
else {//继续判断
temp = temp-right;
}
}
}
}
return；
}
void inorder(Node* node)//树的中序遍历
{
if (node != NULL)
{
inorder(node-left);
printf("%d ",node-data);
inorder(node-right);
}
}
int main()
{
Tree tree;
tree.root = NULL;//创建一个空树
int n;
scanf("%d",n);
for (int i = 0; i n; i++)//输入n个数并创建这个树
{
int temp;
scanf("%d",temp);
insert(tree, temp);
}
inorder(tree.root);//中序遍历
getchar();
getchar();
return 0;
}
扩展资料：
简单二叉树定义范例：此树的顺序结构为：ABCDE
#include cstdlib
#include stdio.h
#include string
int main()
{
node* p = newnode;
node* p = head;
head = p;
string str;
cin str;
creat(p, str, 0)//默认根结点在str下标0的位置
return 0;
}
//p为树的根结点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置
void creat(node* p, string str, int r)
{
p-data = str[r];
if (str[r * 2 + 1] == '#' || r * 2 + 1 str.size() - 1)p-lch = NULL；
else
{
p-lch = newnode;
creat(p-lch, str, r * 2 + 1);
}
if (str[r * 2 + 2] == '#' || r * 2 + 2 str.size() - 1)p-rch = NULL;
else
{
p-rch = newnode;
creat(p-rch, str, r * 2 + 2);
}
}
二叉树的建立与遍历(C语言)
楼主你好~~~“ф”字符的源代码我忘记了，我这里有一个自己写过的遍历算法
#includeiostream.h
typedef struct btnode
{
char data;
struct btnode *Lchild,*Rchild;
}*bitreptr;
void Create(bitreptr p)
{
char n;
p=new btnode;
cinn;
if(n!='#')
{
p-data=n;
Create(p-Lchild);
Create(p-Rchild);
}
else
p=NULL;
}
void preorder(bitreptr p)
{
if(p)
{
coutp-data" ";
preorder(p-Lchild);
preorder(p-Rchild);
}
}
void midorder(bitreptr p)
{
if(p)
{
midorder(p-Lchild);
coutp-data" ";
midorder(p-Rchild);
}
}
void postorder(bitreptr p)
{
if(p)
{
postorder(p-Lchild);
postorder(p-Rchild);
coutp-data" ";
}
}
void change(bitreptr p)
{
bitreptr t,q;
if(p)
{
t=p-Lchild;
q=p-Rchild;
p-Lchild=q;
p-Rchild=t;
change(p-Lchild);
change(p-Rchild);
}
}
void main()
{
char i;
cout"请选择所需功能（'A'输出该二叉树序列，'B'输出交换后二叉树序列)"endl;
cini;
bitreptr p;
cout"输入数据：";
Create(p);
switch(i)
{
case 'A':
{
cout"前序:";
preorder(p);
coutendl;
cout"中序:";
midorder(p);
coutendl;
cout"后序:";
postorder(p);
coutendl;
}break;
case 'B':
{
change(p);
cout"交换二叉树前序:";
preorder(p);
coutendl;
cout"交换二叉树中序:";
midorder(p);
coutendl;
cout"交换二叉树后序:";
postorder(p);
coutendl;
}break;
}
}
这个算法输入时要以“#”代表空节点，及将[测试数据] “ABCффDEфGффFффф”改成“ABC##DE#G##F###”即可。另外我的算法包括了二叉树左右子树交换的代码“change(bitreptr p)”，只要楼主稍作修改就可以得到你想要的完美结果~
急求C语言写二叉树的遍历
BinaryTree.h:
/********************************************************************
created: 2006/07/04
filename: BinaryTree.h
author: 李创
purpose: 演示二叉树的算法
*********************************************************************/
#ifndef BinaryTree_H
#define BinaryTree_H
＃i nclude stdlib.h
＃i nclude stack
class BinaryTree
{
private:
typedef int Item;
typedef struct TreeNode
{
Item Node;
TreeNode* pRight;
TreeNode* pLeft;
TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
: Node(node)
, pRight(pright)
, pLeft(pleft)
{
}
}TreeNode, *PTreeNode;
public:
enum TraverseType
{
PREORDER = 0, // 前序
INORDER = 1, // 中序
POSTORDER = 2, // 后序
LEVELORDER = 3 // 层序
};
BinaryTree(Item Array[], int nLength);
~BinaryTree();
PTreeNode GetRoot()
{
return m_pRoot;
}
// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void Traverse(TraverseType traversetype, bool bRec = true);
private:
PTreeNode CreateTreeImpl(Item Array[], int nLength);
void DetroyTreeImpl(PTreeNode pTreenode);
void PreTraverseImpl(PTreeNode pTreenode); // 递归前序遍历树
void InTraverseImpl(PTreeNode pTreenode); // 递归中序遍历树
void PostTraverseImpl(PTreeNode pTreenode); // 递归后序遍历树
void NoRecPreTraverseImpl(PTreeNode pTreenode); // 非递归前序遍历树
void NoRecInTraverseImpl(PTreeNode pTreenode); // 非递归中序遍历树
void NoRecPostTraverseImpl(PTreeNode pTreenode); // 非递归后序遍历树
void LevelTraverseImpl(PTreeNode pTreenode);
PTreeNode m_pRoot; // 根结点
// 采用STL里面的stack作为模拟保存链表结点的stack容器
typedef std::stackBinaryTree::PTreeNode TreeNodeStack;
};
#endif
BinaryTree.cpp:
/********************************************************************
created: 2006/07/04
filename: BinaryTree.cpp
author: 李创
purpose: 演示二叉树的算法
*********************************************************************/
＃i nclude iostream
＃i nclude assert.h
＃i nclude queue
＃i nclude "BinaryTree.h"
BinaryTree::BinaryTree(Item Array[], int nLength)
: m_pRoot(NULL)
{
assert(NULL != Array);
assert(nLength 0);
m_pRoot = CreateTreeImpl(Array, nLength);
}
BinaryTree::~BinaryTree()
{
DetroyTreeImpl(m_pRoot);
}
// 按照中序递归创建树
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
int mid = nLength / 2;
PTreeNode p = new TreeNode(Array[mid]);
if (nLength 1)
{
p-pLeft = CreateTreeImpl(Array, nLength / 2);
p-pRight = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
}
return p;
}
void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
if (NULL != pTreenode-pLeft)
{
DetroyTreeImpl(pTreenode-pLeft);
}
if (NULL != pTreenode-pRight)
{
DetroyTreeImpl(pTreenode-pRight);
}
delete pTreenode;
pTreenode = NULL;
}
// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
switch (traversetype)
{
case PREORDER: // 前序
{
if (true == bRec)
{
std::cout "递归前序遍历树\n";
PreTraverseImpl(m_pRoot);
}
else
{
std::cout "非递归前序遍历树\n";
NoRecPreTraverseImpl(m_pRoot);
}
}
break;
case INORDER: // 中序
{
if (true == bRec)
{
std::cout "递归中序遍历树\n";
InTraverseImpl(m_pRoot);
}
else
{
std::cout "非递归中序遍历树\n";
NoRecInTraverseImpl(m_pRoot);
}
}
break;
case POSTORDER: // 后序
{
if (true == bRec)
{
std::cout "递归后序遍历树\n";
PostTraverseImpl(m_pRoot);
}
else
{
std::cout "非递归后序遍历树\n";
NoRecPostTraverseImpl(m_pRoot);
}
}
break;
case LEVELORDER: // 层序
{
std::cout "层序遍历树\n";
LevelTraverseImpl(m_pRoot);
}
}
std::cout std::endl;
}
// 递归前序遍历树
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
std::cout "Item = " pTreenode-Node std::endl;
PreTraverseImpl(pTreenode-pLeft);
PreTraverseImpl(pTreenode-pRight);
}
// 非递归前序遍历树
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);
while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
{
std::cout "Item = " pNode-Node std::endl; // 访问当前结点
NodeStack.push(pNode-pLeft); // 左子树根结点入栈
}
NodeStack.pop(); // 左子树根结点退
栈
if (!NodeStack.empty())
{
pNode = NodeStack.top();
NodeStack.pop(); // 当前结点退栈
NodeStack.push(pNode-pRight); // 当前结点的右子树根结点入栈
}
}
}
// 中序遍历树
// 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
if (NULL != pTreenode-pLeft)
{
InTraverseImpl(pTreenode-pLeft);
}
std::cout "Item = " pTreenode-Node std::endl;
if (NULL != pTreenode-pRight)
{
InTraverseImpl(pTreenode-pRight);
}
}
// 非递归中序遍历树
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
TreeNodeStack NodeStack;
PTreeNode pNode;
NodeStack.push(pTreenode);
while (!NodeStack.empty())
{
while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
{
NodeStack.push(pNode-pLeft);
}
NodeStack.pop();
if (!NodeStack.empty() NULL != (pNode = NodeStack.top()))
{
std::cout "Item = " pNode-Node std::endl;
NodeStack.pop();
NodeStack.push(pNode-pRight);
}
}
}
// 后序遍历树
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
if (NULL != pTreenode-pLeft)
{
PostTraverseImpl(pTreenode-pLeft);
}
if (NULL != pTreenode-pRight)
{
PostTraverseImpl(pTreenode-pRight);
}
std::cout "Item = " pTreenode-Node std::endl;
}
// 非递归后序遍历树
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
TreeNodeStack NodeStack;
PTreeNode pNode1, pNode2;
NodeStack.push(pTreenode);
pNode1 = pTreenode-pLeft;
bool bVisitRoot = false; // 标志位,是否访问过根结点
while (!NodeStack.empty())
{
while (NULL != pNode1) // 向左走到尽头
{
NodeStack.push(pNode1);
pNode1 = pNode1-pLeft;
}
pNode1 = NodeStack.top();
NodeStack.pop();
if (NULL == pNode1-pRight) // 如果没有右子树就是叶子结点
{
std::cout "Item = " pNode1-Node std::endl;
pNode2 = pNode1;
pNode1 = NodeStack.top();
if (pNode2 == pNode1-pRight) // 如果这个叶子结点是右子树
{
std::cout "Item = " pNode1-Node std::endl;
NodeStack.pop();
pNode1 = NULL;
}
else // 否则访问右子树
{
pNode1 = pNode1-pRight;
}
}
else // 访问右子树
{
if (pNode1 == pTreenode true == bVisitRoot) // 如果已经访问过右子树那么就退出
{
std::cout "Item = " pNode1-Node std::endl;
return;
}
else
{
if (pNode1 == pTreenode)
{
bVisitRoot = true;
}
NodeStack.push(pNode1);
pNode1 = pNode1-pRight;
}
}
}
}
// 按照树的层次从左到右访问树的结点
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
if (NULL == pTreenode)
return;
// 层序遍历用于保存结点的容器是队列
std::queuePTreeNode NodeQueue;
PTreeNode pNode;
NodeQueue.push(pTreenode);
while (!NodeQueue.empty())
{
pNode = NodeQueue.front();
NodeQueue.pop();
std::cout "Item = " pNode-Node std::endl;
if (NULL != pNode-pLeft)
{
NodeQueue.push(pNode-pLeft);
}
if (NULL != pNode-pRight)
{
NodeQueue.push(pNode-pRight);
}
}
}
main.cpp
/********************************************************************
created: 2006/07/04
filename: main.cpp
author: 李创
purpose: 测试二叉树的算法
*********************************************************************/
＃i nclude "BinaryTree.h"
＃i nclude stdio.h
＃i nclude stdlib.h
＃i nclude time.h
＃i nclude iostream
void DisplayArray(int array[], int length)
{
int i;
for (i = 0; i length; i++)
{
printf("array[%d] = %d\n", i, array[i]);
}
}
void CreateNewArray(int array[], int length)
{
for (int i = 0; i length; i++)
{
array[i] = rand() % 256 + i;
}
}
int main()
{
int array[10];
srand(time(NULL));
// 创建数组
CreateNewArray(array, 10);
DisplayArray(array, 10);
BinaryTree *pTree = new BinaryTree(array, 10);
// 测试前序遍历
pTree-Traverse(BinaryTree::PREORDER);
std::cout "root = " pTree-GetRoot()-Node std::endl;
std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;
std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;
pTree-Traverse(BinaryTree::PREORDER, false);
// 测试中序遍历
pTree-Traverse(BinaryTree::INORDER);
std::cout "root = " pTree-GetRoot()-Node std::endl;
std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;
std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;
pTree-Traverse(BinaryTree::INORDER, false);
// 测试后序遍历
pTree-Traverse(BinaryTree::POSTORDER);
std::cout "root = " pTree-GetRoot()-Node std::endl;
std::cout "root-left = " pTree-GetRoot()-pLeft-Node std::endl;
std::cout "root-right = " pTree-GetRoot()-pRight-Node std::endl;
pTree-Traverse(BinaryTree::POSTORDER, false);
// 测试层序遍历
pTree-Traverse(BinaryTree::LEVELORDER);
system("pause");
delete pTree;
return 0;
}
