c語言求二叉樹的寬度
1. c語言 二叉樹
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int e;
struct Node *l, *r;
} Node;
Node *init() //先序遍歷構造二叉樹
{
char n;
Node *p;
scanf("%c", &n);
if (n=='0')
return NULL;
p = (Node*)malloc(sizeof(Node));
if (!p)
exit(0);
p->e = n-'0';
p->l = init();
p->r = init();
return p;
}
void DLR(Node *head) //先序遍歷二叉樹（遞歸演算法）
{
if (head)
{
printf("%d", head->e);
DLR(head->l);
DLR(head->r);
}
}
void destory(Node *head) //銷毀二叉樹
{
Node *l, *r;
if (!head)
return;
l = head->l;
r = head->r;
free(head);
destory(l);
destory(r);
}
int main()
{
Node *head = init();
DLR(head);
destory(head);
return 0;
}
2. 求一份 c語言 求二叉樹的寬度（後序遍歷）
二叉樹的寬度是如何定義的，你這不說一下？
3. 計算機c語言中 什麼是二叉樹
在計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（left subtree）和「右子樹」（right subtree）。二叉樹常被用作二叉查找樹和二叉堆或是二叉排序樹。
二叉樹的每個結點至多隻有二棵子樹(不存在度大於2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2的 i -1次方個結點；深度為k的二叉樹至多有2^(k) -1個結點；對任何一棵二叉樹T，如果其終端結點數(即葉子結點數)為n0，度為2的結點數為n2，則n0 = n2 + 1。
樹是由一個或多個結點組成的有限集合，其中：
⒈必有一個特定的稱為根(ROOT)的結點；二叉樹
⒉剩下的結點被分成n>=0個互不相交的集合T1、T2、......Tn，而且， 這些集合的每一個又都是樹。樹T1、T2、......Tn被稱作根的子樹(Subtree)。
樹的遞歸定義如下：（1）至少有一個結點（稱為根）（2）其它是互不相交的子樹
1.樹的度——也即是寬度，簡單地說，就是結點的分支數。以組成該樹各結點中最大的度作為該樹的度，如上圖的樹，其度為2;樹中度為零的結點稱為葉結點或終端結點。樹中度不為零的結點稱為分枝結點或非終端結點。除根結點外的分枝結點統稱為內部結點。
2.樹的深度——組成該樹各結點的最大層次。
3.森林——指若干棵互不相交的樹的集合，如上圖，去掉根結點A，其原來的二棵子樹T1、T2、T3的集合{T1,T2,T3}就為森林；
4.有序樹——指樹中同層結點從左到右有次序排列，它們之間的次序不能互換，這樣的樹稱為有序樹，否則稱為無序樹。
4. 求二叉樹的深度(深度優先)用棧
int BiTreeDepth( btnode * b)
{
struct
{
int lno;//保存結點的層數
btnode * p;
}Q[MAXSIZE];//建立隊列
int front,rear;
int lnum;
front=rear=0;
if(b!=NULL)
{
rear++;
Q[rear].p=b;
Q[rear].lno=1;
while(rear!=front)
{
front++;
b=Q[front].p;
lnum=Q[front].lno;
if(b->lchild!=NULL)
{
rear++;
Q[rear].p=b->lchild;
Q[rear].lno=lnum+1;
}
if(b->rchild!=NULL)
{
rear++;
Q[rear].p=b->rchild ;
Q[rear].lno=lnum+1;
}
}
}
return Q[rear].lno;
}
這是我的實驗程序，我的btnode相當於你的TNode，你可以自己修改一下哈。這段程序很有用的，它建立一個隊列，並且給每個樹的結點編上了層號，如果你把這個隊列進行出隊輸出，輸出的為樹按層次遍歷的序列。當然也可以用這個程序求二叉樹的寬度：
int btwidth(btnode *b)//求二叉樹的寬度
{
struct
{
int lno;//保存結點的層數
btnode * p;
}Q[MAXSIZE];//建立隊列
int front,rear;
int lnum,max,i,n;
front=rear=0;
if(b!=NULL)
{
rear++;
Q[rear].p=b;
Q[rear].lno=1;
while(rear!=front)
{
front++;
b=Q[front].p;
lnum=Q[front].lno;
if(b->lchild!=NULL)
{
rear++;
Q[rear].p=b->lchild;
Q[rear].lno=lnum+1;
}
if(b->rchild!=NULL)
{
rear++;
Q[rear].p=b->rchild ;
Q[rear].lno=lnum+1;
}
}
max=0;
lnum=1;
i=1;
while(i<=rear)//此時rear等於二叉樹結點的個數
{
n=0;
while(i<=rear&&Q[i].lno==lnum)
{
n++;
i++;
}
lnum=Q[i].lno;
if(n>max)//求結點數最多的一層結點的個數
max=n;
}
return max;
}
else
return 0;
}
希望對你有所幫助，相互討論，呵呵
至於用棧實現，我還在調試中，^_^
5. C語言二叉樹
在create_tree中，參數t只在一開始被bintree初始化，此時他們同時指向未初始化的內存。當執行到t=(tree * )malloc(sizeof(tree));時候，t被賦予了新的內存空間，注意，這里新分配的內存僅僅是分配給了t，與bintree沒有關系。每次進入create_tree後都為局部變數t分配內存，而你在函數退出之後無法進行內存回收，進而造成內存泄露。
正確的做法是，給create_tree傳遞一個指針類型的引用，tree *&t，這樣你在操作t的時候就像在操作bintree一樣，才能達到給bintree分配內存的目的。
最後別忘了寫一個釋放內存的方法：
void free_tree(tree *t)
{
if (t)
{
free_tree(t->lchild);
free_tree(t->rchild);
printf("\n%c has freed.", t->data);
free(t);
}
}
6. 用C語言編程 ：建立三層二叉樹，先根遍歷輸出，在線求高手
A
(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");
}
7. 二叉樹的C語言程序求教
typedef char DataType;//給char起個別名 DataType
//定義二叉樹的數據結構
typedef struct node{
DataType data;//二叉樹存儲的數據
struct node *lchild, *rchild;//二叉樹的左、右子樹的指針
}BinTNode;
typedef BinTNode *BinTree ; //自定義一個數據類型（二叉樹的指針類型）
#include <stdio.h>
#include <malloc.h>
//以前序遍歷構建二叉樹
void CreatBinTree(BinTree *T)
{
char ch;//定義臨時變數ch，用來接受數據
if ((ch=getchar())==' ')
*T=NULL;//如果輸入為空，則停止構建二叉樹
else{*T=(BinTNode *)malloc(sizeof(BinTNode));//為二叉樹分配內存空間
(*T)->data=ch;//把輸入的數據存入二叉樹
CreatBinTree(&(*T)->lchild);//構建左子樹（遞歸）
CreatBinTree(&(*T)->rchild);//構建左子樹（遞歸）
}
}
//求二叉樹的結點數
int Node(BinTree T)
{ int static nodes=0;//定義一個變數存儲二叉樹的結點數
if(T)//如果二叉樹不為空（是結點），執行此語句
{
Node(T->lchild);//看左子樹是不是個結點（遞歸）
nodes++;//結點數加1
Node(T->rchild);//看右子樹是不是個結點（遞歸）
}
return nodes;//返回結點數
}
//求二叉樹的葉子數
int Leaf(BinTree T)
{ int static leaves=0;//定義一個變數存儲二叉樹的葉子數
if(T)//如果二叉樹不為空，執行此語句
{
Leaf(T->lchild);//看左子樹是不是葉子（遞歸）
if(!(T->lchild||T->rchild))//如果二叉樹T的左、右結點都為空，則執行此語句（即是葉子）
leaves++;//葉子數加1
Leaf(T->rchild);//看右子樹是不是葉子（遞歸）
}
return leaves;//返回葉子數
}
#include <stdio.h>
void main()
{ BinTree root;
CreatBinTree(&root);//構建二叉樹
int nodes=Node(root);//求此二叉樹的結點數
int leaves=Leaf(root);//求此二叉樹的葉子數
printf("\nnodes=%d leaves=%d",nodes,leaves);
}
上面是我的理解，好久沒有寫過代碼了，如有錯誤，請指出。
8. c語言中二叉樹個數計算方法
遞歸……非空樹的總結點數=左子樹結點數+右子樹結點數+1（也就是根結點）。
偽代碼：
int
node_counter(TreeNode
*root)
{
if
(root==null)
return
0;
else
return
node_counter(root->left)
+
node_counter(root->right)
+
1;
}
9. C語言二叉樹的深度指什麼怎麼求
從根節點到葉子結點一次經過的結點形成樹的一條路徑，最長路徑的長度為樹的深度。根節點的深度為1。
解體思路：
1.如果根節點為空，則深度為0，返回0，遞歸的出口。
2.如果根節點不為空，那麼深度至少為1，然後我們求他們左右子樹的深度，
3.比較左右子樹深度值，返回較大的那一個
4.通過遞歸調用
#include<iostream>
#include<stdlib.h>
usingnamespacestd;
structBinaryTreeNode
{
intm_nValue;
BinaryTreeNode*m_pLeft;
BinaryTreeNode*m_pRight;
};
//創建二叉樹結點
BinaryTreeNode*CreateBinaryTreeNode(intvalue)
{
BinaryTreeNode*pNode=newBinaryTreeNode();
pNode->m_nValue=value;
pNode->m_pLeft=NULL;
pNode->m_pRight=NULL;
returnpNode;
}
//連接二叉樹結點
voidConnectTreeNodes(BinaryTreeNode*pParent,BinaryTreeNode*pLeft,BinaryTreeNode*pRight)
{
if(pParent!=NULL)
{
pParent->m_pLeft=pLeft;
pParent->m_pRight=pRight;
}
}
//求二叉樹深度
intTreeDepth(BinaryTreeNode*pRoot)//計算二叉樹深度
{
if(pRoot==NULL)//如果pRoot為NULL，則深度為0，這也是遞歸的返回條件
return0;
//如果pRoot不為NULL，那麼深度至少為1，所以left和right=1
intleft=1;
intright=1;
left+=TreeDepth(pRoot->m_pLeft);//求出左子樹的深度
right+=TreeDepth(pRoot->m_pRight);//求出右子樹深度
returnleft>right?left:right;//返回深度較大的那一個
}
voidmain()
{
//1
///
//23
///\
//456
///
//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);
intdepth=TreeDepth(pNode1);
cout<<depth<<endl;
system("pause");
}
出處：http://www.cnblogs.com/xwdreamer
10. 數據結構C語言求二叉樹寬度
void沒有返回a的值，主函數輸出的值就是你定義的a=0的值