c語言層序遍歷創建二叉樹,二叉樹的建立與遍歷完整代碼C語言

本文目錄一覽：

• 1、請問C語言如何創建二叉樹？？？？
• 2、二叉樹的建立與遍歷(C語言)
• 3、急求C語言寫二叉樹的遍歷

請問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;

}